东莞市盛裕绒艺玩具有限公司

东莞市盛裕绒艺玩具有限公司

同乐城备用

13954919431
新闻资讯
联系方式
全国服务热线: 13954919431

咨询热线:15288205895
联系人:黄国强
地址:沙河百沙路新飞达电子科技发展中心

数据结构与算法(4) -- list、queue以及stack

来源:同乐城备用   发布时间:2019-10-29   点击量:294

今天主要给大家介绍几种数据结构,这几种数据结构在实现原理上较为类似,我习惯称之为类list的容器。具体有list、stack以及queue。

list的节点Node

首先介绍下node,也就是组成list的节点。从面向对象的角度来说节点也是就一个类,list里面包含了node对象的实例,以及操作/管理这些实例的方法。先给出一个粗糙的node的C++代码如下代码块所示。可以看出除了保有当前节点的信息,其还有指向前一个节点和后一个节点的指针。如果单独使用当然另外还需要相应的构造函数。如果是使用node组成其他的如list数据结构,也可以不需要node自己的构造函数,而完全交由list分配空间和数据,这部分可以参考《STL源码剖析》。好吧,扯得有点远了,为了讲述的简单,后面的代码都将采取简易的实现方式,如有不妥欢迎私信。

template<typename T>struct Node{ typedef void * void_pointer; void_pointer prev; void_pointer next; T data; Node(T data){ this->data = data; prev = nullptr; next = nullptr; }};

Node构成的数据结构有哪些

说完了node,那么由node(或其变体)作为基本单元的数据结构有哪些呢?当然首先有list(链表),其次stack(栈)以及queue(队列)也是哈。list是双向链接的,头和尾都可以插入和删除node,当然中间插入删除也是可以的。而stack则是先进后出的队列,啥意思呢,也就是说:插入和删除都是针对最顶层的node的;queue则不同,它是先进先出的,和我们日常排队买东西是一样的原理。接下来分别介绍。

list

先来个图感性认识一下:

其实看了图之后也就无需多言了哈,不就是node一个链接一个么。嘿,简单!!!

stack

那stack呢,更加简单啦。只要将双向的链表换成单向的链表就可以实现了哈。在表的前端插入来实施push操作,通过删除表的前端元素来完成pop操作。top操作知识考察表前端元素并返回它的值。(当然stack也可以用基于vector来实现)。

queue

先进先出,其实现可以基于链表。但是也可以基于deque/vector。与stack一样若基于已有的结构,其实现是较为简单的,这里不详细叙述。

实现一个list

其实从stl的源码可以看出,要真正实现一个list并不像看上去那么简单。考虑到内存分配以及构造的细节,还是比较麻烦的。这里我们主要是为了掌握list的基本结构,对其主要操作做一个了解。所以不必写那么复杂的实现(哈哈,太复杂的我也写不好,还是建议阅读源码哈)。

list的迭代器

迭代器是后需几乎所有操作的基础。那么怎么组织这个迭代器呢,或者换句换说,迭代器在哪里定义呢?我们可以这么组织我们的代码:

using namespace std;template <typename Object>class List{ private: struct Node { ... }; public: class const_iterator { public: ... protected: Node *current; ... friend class List<Object>; }; class iterator : public const_iterator { public: ... friend class List<Object>; }; public: List( ) { init( ); } ~List( ) //其他方法: ... ... private: int theSize; Node *head; Node *tail; void init( ) { theSize = 0; head = new Node; tail = new Node; head->next = tail; tail->prev = head; }};

稍微分析一下,首先list由node一个链接一个构成,所以需要一个node类。另外不希望第三方类使用,所以是私有的。在看迭代器,迭代器是为了方便遍历list或者指代list的当前位置的。所以其本质是一个指针,而且是指向node的指针,所以可以看到const_iterator类有个指针的定义:**Node *current;**。因为有时候通过迭代器只是想单纯访问数据而已,而有时候是希望能够改变node节点的数据。所以就有了const_iterator以及iterator两套哈。我不打算在这里给出迭代器的实现细节,这部分内容有很多教材的源码都是不错的,STL源码可能复杂些不建议。推荐《数据结构与算法分析--C++语言描述(第四版)》,请参考我的GitHub。但是还是有几个细节需要提一下:

迭代器的类要是list的友元。迭代器在某种意义上就是某种智能指针,所以重载*以及->(或者++, --)操作是必须的。为了后续操作的方便,在list中==以及!=通常也少不了。通常需要head(表示第一个元素的前一个位置)以及tail(最后一个元素的最后一个位置)。这是为了在遍历的时候可以用迭代器!=head以及tail来判断是否到达边界。

几个list重要操作的原理与实现

现在假设我们已经有了一个功能完整的迭代器,那么接下来的操作基于迭代器就好了。

删除

先给出图和代码:

iterator erase( iterator itr ) { Node *p = itr.current; iterator retVal( p->next ); p->prev->next = p->next; p->next->prev = p->prev; delete p; --theSize; return retVal; } iterator erase( iterator from, iterator to ) { for( iterator itr = from; itr != to; ) itr = erase( itr ); return to; }

直观上看我们只要删除1和2号线,增加3和4号线就可以了。代码就是上面的代码哈,很简单。但是,经常容易犯得错误是:忘记先保存删除节点的位置。那么在1与2号线删除之后就再也无法释放其资源了哈,这就是第一行代码 Node *p = itr.current; 的用意。第二行代码 iterator retVal( p->next ); 是为了删除之后仍然能够得到有效的迭代器。

插入

插入操作也是类型的,只不过这里用了一个较为看上去复杂的操作 p->prev = p->prev->next = new Node{ x, p->prev, p } 。记住,c++赋值语句,是从右往左执行的。结合图,也就不难理解这句话了。

// Insert x before itr. iterator insert( iterator itr, const Object & x ) { Node *p = itr.current; ++theSize; return iterator( p->prev = p->prev->next = new Node{ x, p->prev, p } ); } // Insert x before itr. iterator insert( iterator itr, Object && x ) { Node *p = itr.current; ++theSize; return iterator( p->prev = p->prev->next = new Node{ std::move( x ), p->prev, p } ); }

其他--stl/java

stl里list的实现实际上稍有出入,主要体现在内存分配与构造。实在是能力有限,在这里不敢瞎说。推荐大家阅读侯捷老师的《STL源码剖析》。另外java里的迭代器需要实现Iterator接口就好了。

关于queue与stack的基于node的实现就不赘述了。另外dequeue也可基于node实现,但是stl里是基于分段连续线性空间实现的,如果有可能会在后续的博客中详细讲述。

最后给一个我之前写的dequeue-java版本作为结束。

import java.util.Iterator;import java.util.NoSuchElementException;public class Deque<Item> implements Iterable<Item> { private Node first = null; private Node last = null; private int size = 0; public Deque() { } private class Node{ Item item; Node next; Node previous; } public boolean isEmpty() { return first==null && last==null; } public int size() { return size; } public void addFirst(Item item) { if(item==null) throw new IllegalArgumentException(); if(0==size) { //if size==0, let first and last point to item first = new Node(); first.item = item; last = first; }else { Node oldfirst = first; first = new Node(); first.item = item; first.next = oldfirst; oldfirst.previous = first; } size++; } public void addLast(Item item) { if(item==null) throw new IllegalArgumentException(); if(0==size) { //if size==0, let first and last point to item last = new Node(); last.item = item; first = last; }else { Node oldlast = last; last = new Node(); last.item = item; last.previous = oldlast; oldlast.next = last; } size++; } public Item removeFirst() { if(size==0) throw new NoSuchElementException(); Item itemtem = first.item; if(size==1) { first = null; last = null; }else { Node oldfirst = first; first = oldfirst.next; first.previous = null; oldfirst.next = null; oldfirst.item = null; } size--; return itemtem; } public Item removeLast() { if(size==0) throw new NoSuchElementException(); Item itemtem = last.item; if(size==1) { itemtem = last.item; first = null; last = null; }else { Node oldlast = last; last = oldlast.previous; last.next = null; oldlast.previous = null; oldlast.item = null; } size--; return itemtem; } private class DequeIterator implements Iterator<Item>{ private Node current = first; @Override public boolean hasNext() { return current != null; } @Override public Item next() { if(!hasNext()) throw new NoSuchElementException(); Item itemtem = current.item; current = current.next; return itemtem; } public void remove() { throw new UnsupportedOperationException(); } } public Iterator<Item> iterator(){ return new DequeIterator(); } public static void main(String[] args) { // TODO Auto-generated method stub Deque<Integer> deque = new Deque<Integer>(); deque.addFirst(1); deque.addFirst(2); deque.addFirst(3); deque.addLast(4); deque.addLast(5); deque.addLast(6); deque.removeFirst(); deque.removeLast(); deque.removeFirst(); deque.removeLast(); deque.removeFirst(); deque.removeLast(); for (Integer integer : deque) { System.out.println(integer); } }}

See you next time. Happy Coding!!!我的github

相关产品

COPYRIGHTS©2017 同乐城备用 ALL RIGHTS RESERVED 备案号:294