数据结构系列文章 |
---|
数据结构图文解析之:数组、单链表、双链表介绍及C++模板实现 |
数据结构图文解析之:栈的简介及C++模板实现 |
数据结构图文解析之:队列详解与C++模板实现 |
数据结构图文解析之:树的简介及二叉排序树C++模板实现. |
数据结构图文解析之:AVL树详解及C++模板实现 |
数据结构图文解析之:二叉堆详解及C++模板实现 |
数据结构图文解析之:哈夫曼树与哈夫曼编码详解及C++模板实现 |
队列(Queue)与栈一样,是一种线性存储结构,它具有如下特点:
队列的相关概念:
例如我们有一个存储整型元素的队列,我们依次入队:{1,2,3}
添加元素时,元素只能从队尾一端进入队列,也即是2只能跟在1后面,3只能跟在2后面。 如果队列中的元素要出队:
元素只能从队首出队列,出队列的顺序为:1、2、3,与入队时的顺序一致,这就是所谓的“先进先出”。
队列通常提供的操作:
队列与栈一样是一种线性结构,因此以常见的线性表如数组、链表作为底层的数据结构。 本文中,我们以数组、链表为底层数据结构构建队列。
以数组作为底层数据结构时,一般讲队列实现为循环队列。这是因为队列在顺序存储上的不足:每次从数组头部删除元素(出队)后,需要将头部以后的所有元素往前移动一个位置,这是一个时间复杂度为O(n)的操作:
可能有人说,把队首标志往后移动不就不用移动元素了吗?的确,但那样会造成数组空间的“流失”。 我们希望队列的插入与删除操作都是O(1)的时间复杂度,同时不会造成数组空间的浪费,我们应该使用循环队列。 所谓的循环队列,可以把数组看出一个首尾相连的圆环,删除元素时将队首标志往后移动,添加元素时若数组尾部已经没有空间,则考虑数组头部的空间是否空闲,如果是,则在数组头部进行插入。
那么我们如何判断队列是空队列还是已满呢?
template <typename T> class LoopQueue { public: LoopQueue(int c = 10); ~LoopQueue(); public: bool isEmpty(); //队列的判空 int size(); //队列的大小 bool push(T t); //入队列 bool pop(); //出队列 T front(); //队首元素 private: int capacity; int begin; int end; T* queue; };
队列的操作非常简单,这里不再多说
template<typename T> LoopQueue<T>::LoopQueue(int c = 10) : capacity(c), begin(0), end(0), queue(nullptr) { queue = new T[capacity]; }; template<typename T> LoopQueue<T>::~LoopQueue() { delete[]queue; } template <typename T> bool LoopQueue<T>::isEmpty() { if (begin == end) return true; return false; }; template<typename T> int LoopQueue<T>::size() { return (end-begin+capacity)%capacity; //计算队列长度 }; template<typename T> bool LoopQueue<T>::push(T t) { if (end + 1 % capacity == begin) //判断队列是否已满 { return false; } queue[end] = t; end = (end + 1) % capacity; return true; }; template <typename T> bool LoopQueue<T>::pop() { if (end == begin) //判断队列是否为空 { return false; } begin = (begin + 1) % capacity; return true; }; template <typename T> T LoopQueue<T>::front() { if (end == begin) { return false; } return queue[begin]; };
int main() { LoopQueue<string> queue(6); queue.push("one"); queue.push("two"); queue.push("three"); queue.push("four"); queue.push("five"); cout << "队列长度" << queue.size() << endl; while (!queue.isEmpty()) { cout << queue.front() << endl; queue.pop(); } getchar(); return 0; }
测试结果:
队列长度5 one two three four five
链队列是基于链表实现的队列,它不存在数组的O(n)的元素移动问题或空间浪费问题。我们所要确定的就是链表哪头做队首,哪头做队尾。 显然我们应该以链表头部为队首,链表尾部为队尾。存储一个指向队尾的指针,方便从链表尾插入元素;使用带头节点的链表,方便从链表头删除元素。
template<typename T> struct Node { Node(T t) :value(t), next(nullptr){} Node() = default; T value; Node<T> * next; };
链队列提供的接口与循环队列一致
template<typename T> class LinkQueue { public: LinkQueue(); ~LinkQueue(); bool isEmpty(); int size(); bool pop(); void push(T t); T front(); private: Node<T>* phead; Node<T>* pend; int count; };
template<typename T> LinkQueue<T>::LinkQueue() :phead(nullptr),pend(nullptr),count(0) { phead = new Node<T>(); pend = phead; count = 0; }; template <typename T> LinkQueue<T>::~LinkQueue() { while (phead->next != nullptr) { Node<T> * pnode = phead; phead = phead->next; } }; template <typename T> bool LinkQueue<T>:: isEmpty() { return count==0; }; template <typename T> int LinkQueue<T>::size() { return count; }; //在队尾插入 template <typename T> void LinkQueue<T>::push(T t) { Node<T>* pnode = new Node<T>(t); pend->next = pnode; pend = pnode; count++; }; //在队首弹出 template <typename T> bool LinkQueue<T>::pop() { if (count == 0) return false; Node<T>* pnode = phead->next; phead->next = phead->next->next; delete pnode; count--; return true; }; //获取队首元素 template<typename T> T LinkQueue<T>::front() { return phead->next->value; };
int _tmain(int argc, _TCHAR* argv[]) { LinkQueue<string> lqueue; lqueue.push("one"); lqueue.push("two"); lqueue.push("three"); lqueue.push("four"); lqueue.push("five"); cout << "队列的大小" << lqueue.size() << endl; while (!lqueue.isEmpty()) { cout << lqueue.front() << endl; lqueue.pop(); } getchar(); return 0; }
运行结果:
队列的大小5 one two three four five
循环队列:https://github.com/huanzheWu/Data-Structure/blob/master/LoopQueue/LoopQueue/LoopQueue.h 链队列:https://github.com/huanzheWu/Data-Structure/blob/master/LinkQueue/LinkQueue/LinkQueue.h
原创文章,转载请注明出处:http://www.cnblogs.com/QG-whz/p/5171123.html#_label3_0
本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。
我来说两句