C++数据结构--队列

一.什么是队列队列Queue是一种遵循先进先出FIFO, First In First Out原则的数据结构。队列通常有两种实现方式顺序队列环形队列与链式队列各有优劣。但同时从底层来看队列并不是一种新的数据结构环形队列的底层依靠数组链式栈的底层依靠链表。注意C中的容器适配器queue底层默认是deque双向队列是一个顺序队列但是我们也可以将其设置成一个链式栈二.环形队列及其代码实现原理基于固定大小的数组实现通过维护两个指针/索引front队头和rear队尾核心思想通过取模运算%使得当rear加到·队尾时通过取模运算能够将其回到队内存开始的地方存储由此实现了类似于环的结构rear (rear 1) % capcap是数组的容量front (front 1) % cap实际上的实现过程中为了区分队空与满我们需要空出一个存储空间当front rear表示队空(rear 1) % 容量 front表示队满;优点极高的空间利用率操作效率极高内存友好且稳定缺点容量固定无法动态扩展存在少量空间浪费代码实现如下图class Queue//环形队列 { public: Queue(int cap 10) :m_cap(cap) ,m_front(0) ,m_rear(0) ,m_size(0) { pQue new int[cap]; } ~Queue() { delete[]pQue; pQue nullptr; } public: void push(int val)//入队 { if ((m_rear 1) % m_cap m_front) { expend(2 * m_rear); } pQue[m_rear] val; m_rear (m_rear 1) % m_cap; m_size; } void pop()//出队 { if (m_rear m_front) throw Queue is empty; m_front (m_front 1) % m_cap; m_size--; } int front() const//获取队头元素 { if (m_rear m_front) throw Queue is empty; return pQue[m_front]; } int back() const//获取队尾元素 { if (m_rear m_front) throw Queue is empty; return pQue[(m_rear-1m_cap)%m_cap]; } bool empty() const//判断是否为空 { return m_front m_rear; } int size() const//获取元素个数 { return m_size; } void show()const//打印 { int p m_front; while (p ! m_rear) { cout pQue[p] ; p (p 1) % m_cap; } cout endl; } private: void expend(int val)//扩容 { int p m_front; int* q new int(val); int i 0; while (p ! m_rear) { q[i] pQue[p]; p (p 1) % m_cap; i; } delete[] pQue; pQue q; m_cap val; m_front 0; m_rear i; } private: int* pQue; int m_cap; int m_front; int m_rear; int m_size; };三.链式栈及其代码实现原理基于双向循环链表实现需要定义一个头节点入队操作相于当尾插出队操作相当于头删。优点操作效率极高动态扩容支持双向遍历缺点空间开销大缓存友好性差代码实现如下图class LinkQueue { public: LinkQueue() { head new Node(); head-next head; head-pre head; } ~LinkQueue() { Node* p head-next; while (p!head ) { head-next p-next; p-next-pre head; delete p; p head-next; } delete head; head nullptr; } public: void push(int val)//入队 { Node* node new Node(val); Node* p head-pre; p-next node; node-pre p; node-next head; head-pre node; m_size; } void pop()//出队 { if (head-next head) throw Queue is empty; Node* p head-next; head-next head-next-next; delete p; head-next-next-pre head; m_size--; } int front() const//获取队头元素 { if (head-next head) throw Queue is empty; return head-next-data; } int back() const//获取队尾元素 { if (head-next head) throw Queue is empty; return head-pre-data; } bool empty() const//判断队列是否为空 { return head-next head; } void show()const//打印 { Node* p head-next; while (p-next ! head) { cout p-data ; p p-next; } cout endl; } int size() const//获取队列元素个数 { return m_size; } private: struct Node { Node(int val0) :data(val) ,next(nullptr) ,pre(nullptr) { } int data; Node* next; Node* pre; }; Node* head; int m_size; };四.典型问题1. 用队列实现栈class MyStack { public: MyStack() { } void push(int x) { q1.push(x); while(!q2.empty()) { q1.push(q2.front()); q2.pop(); } queueint q3; q2q1; q1q3; } int pop() { int valq2.front(); q2.pop(); return val; } int top() { return q2.front(); } bool empty() { return q2.empty(); } private: queueint q1; queueint q2; };2.用栈实现队列class MyQueue { public: MyQueue() { } void push(int x) { s1.push(x); } int pop() { if(s2.empty()) { while(!s1.empty()) { s2.push(s1.top()); s1.pop(); } } int vals2.top(); s2.pop(); return val; } int peek() { if(s2.empty()) { while(!s1.empty()) { s2.push(s1.top()); s1.pop(); } } return s2.top(); } bool empty() { return s1.empty()s2.empty(); } private: stackint s1; stackint s2; };