在C++中,标准库提供了三种顺序容器适配器:queue(FIFO队列)、priority_queue(优先级队列)、stack(栈) 。
种类 | 默认顺序容器 | 可用顺序容器 | 说明 |
queue | deque | list、deque | 基础容器需要提供能使用push_front |
stack | deque | vector、list、deque | |
priority_queue | vector | vector、deque | 基础容器需要提供随机访问的能力 |
可以使用顺序容器,初始化适配器。
如:deque<int> deq;
stack<int> sta(deq);
stack的操作有size()、empty()、top()、push()、pop();queue的操作有size()、empty()、push()、pop()、back()、front();priority_queue的操作有size()、empty()、push()、pop()、top();
用两个栈实现队列的功能
#include <stack> #include <exception> template<typename T> class CQueue { public: CQueue(void); ~CQueue(void); // 在队列末尾添加一个结点queue.push(x)将x接到队列的末尾 void appendTail(const T& node); // 删除队列的头结点queue.pop();弹出不会返回元素的值 T deleteHead(); int GetSize();//queue.size();得到队列的大小 T GetFront();//queue.front();得到队列的最早被压入队列的元素。 bool IsEmpty();//queue.empty();判断队列为空 T GetBack();//queue.back();最后被压入队列的元素。 private: stack<T> StackCurrent; stack<T> StackAssist; }; template <typename T> T CQueue<T>::GetBack() { //if(CQueue<T>::IsEmpty()) //throw new exception("The queue is empty."); if (!StackCurrent.empty()) { return StackCurrent.top(); } else { while (StackAssist.size() > 0) { T temp = StackAssist.top(); StackAssist.pop(); StackCurrent.push(temp); } return StackCurrent.top(); } } template <typename T> bool CQueue<T>::IsEmpty() { return StackCurrent.empty()||StackAssist.empty(); } template <typename T> int CQueue<T>::GetSize() { int temp = StackCurrent.size()+StackAssist.size(); return temp; } template <typename T> T CQueue<T>::GetFront() { if(StackAssist.empty() && StackCurrent.empty()) throw new exception("The queue is empty."); if (!StackAssist.empty()) { T temp = StackAssist.top(); return temp; } else { while (StackCurrent.size() > 0) { T temp = StackCurrent.top(); StackCurrent.pop(); StackAssist.push(temp); } T temp = StackAssist.top(); return temp; } } template <typename T> CQueue<T>::CQueue(void) { } template <typename T> CQueue<T>::~CQueue(void) { } template<typename T>void CQueue<T>::appendTail(const T& node) { StackCurrent.push(node); } template<typename T>T CQueue<T>::deleteHead() { if(StackAssist.size() <= 0) { while (StackCurrent.size() > 0) { T temp = StackCurrent.top(); StackCurrent.pop(); StackAssist.push(temp); } } if (StackAssist.size() == 0) { throw new exception("The queue is empty."); } else { T temp = StackAssist.top(); StackAssist.pop(); return temp; } }
用两个队列实现栈
1 #include <queue> 2 template<typename T> class CStack 3 { 4 public: 5 CStack(); 6 ~CStack(); 7 bool IsEmpty(); 8 int GetSize(); 9 T GetTop(); 10 T DeleHead();//删除栈顶元素 11 void AddHead(const T &node);//在栈顶加入元素 12 private: 13 queue<T> queueAssit; 14 queue<T> queueCurrent; 15 }; 16 template<typename T>void CStack<T>::AddHead(const T &node) 17 { 18 queueAssit.push(node); 19 } 20 template<typename T>T CStack<T>::DeleHead() 21 { 22 if (!queueAssit.empty()) 23 { 24 while (queueAssit.size() > 1) 25 { 26 T temp = queueAssit.front(); 27 queueAssit.pop(); 28 queueCurrent.push(temp); 29 } 30 T temp = queueAssit.front(); 31 queueAssit.pop(); 32 return temp;///返回删除的元素 33 } 34 else 35 { 36 while (queueCurrent.size() > 1) 37 { 38 T temp = queueCurrent.front(); 39 queueCurrent.pop(); 40 queueAssit.push(temp); 41 } 42 T temp = queueCurrent.front(); 43 queueCurrent.pop(); 44 return temp;///返回删除的元素 45 } 46 } 47 template<typename T>T CStack<T>::GetTop() 48 { 49 if (!queueAssit.empty()) 50 { 51 52 while (queueAssit.size() > 1) 53 { 54 T temp = queueAssit.front(); 55 queueAssit.pop(); 56 queueCurrent.push(temp); 57 } 58 T temp = queueAssit.front(); 59 return temp;///返回删除的元素 60 } 61 else 62 { 63 while (queueCurrent.size() > 1) 64 { 65 T temp = queueCurrent.front(); 66 queueCurrent.pop(); 67 queueAssit.push(temp); 68 } 69 T temp = queueCurrent.front(); 70 return temp;///返回删除的元素 71 } 72 } 73 template<typename T> CStack<T>::CStack() 74 { 75 ; 76 } 77 template<typename T> CStack<T>::~CStack() 78 { 79 ; 80 } 81 template<typename T> bool CStack<T>::IsEmpty() 82 { 83 return queueCurrent.empty()||queueAssit.empty(); 84 } 85 template<typename T> int CStack<T>::GetSize() 86 { 87 return queueCurrent.size()+queueAssit.size(); 88 }