题目来自剑指Offer
题目:
思路:设置两个栈,一个用来接收数据InStack,一个用来输出数据OutStack。
队列空:两个栈都为空,则队列空
队列满:接收数据的InStack栈满了,而且输出数据的OutStack栈中有数据,则满。
入队:
检测接收数据的InStack栈,是否为满。
不满,则直接入InStack栈。满了,检测输出数据的OutStack是否有数据。
如果OutStack栈中有数据,则表示队列满。如果没数据,则把InStack栈中的数据全部导入OutStack栈中。
注意:
(1)这样可能表示队满,会存在空间浪费。
(2)在把InStack栈中的数据全部导入OutStack栈中时,相当于元素先从栈InStack出栈,入栈到OutStack中。
出队列:
检测输出数据的OutStack栈,是否为空。
不空,则直接出OutStack栈。空了,则检测接收数据的InStack是否有数据。
如果InStack栈没数据,则表示队列为空,没有数据要出。
如果InStack栈中有数据,则表示还有数据可以出,则把InStack中的数据全出栈,之后再压入OutStack栈。之后再从OutStack出栈。
代码:
#include <iostream> #include <assert.h> using namespace std; const int SIZE = 5; class Queue { public: Queue(); void AppendTail(int nData); int RemoveHead(); bool IsEmpty(); bool IsFull(); private: int nTopIn; int nTopOut; int nArrInStack[SIZE]; int nArrOutStack[SIZE]; private: void MoveInToOut(); }; Queue::Queue() { nTopIn = 0; nTopOut = 0; } /* 入队列: 判断第一个栈是否有满: 第一个栈没有满,往第一个栈中插入新元素。 第一个栈已满,检测第二个栈是否有元素: 第二个栈已有元素,表示队列已满,报错,结束。 第二个栈没有元素,未满: 把第一个栈中元素移动到第二个栈中 往第一个栈中插入新元素。 */ void Queue::AppendTail(int nData) { assert(nTopIn > -1 && nTopOut > -1); if (nTopIn >= 0 && nTopIn < SIZE) { nArrInStack[nTopIn++] = nData; return; } if (nTopOut == 0) { MoveInToOut(); nArrInStack[nTopIn++] = nData; } else { cout<<"队列已满!"<<endl; assert(nTopOut != 0);//报错 } } /* (1)判断第二个栈是否有元素: 第二个栈有元素,则直接出栈。 第二个栈没有元素,则去第一个栈看看有没有元素: 第一个栈有元素,全部压入第二个栈中,之后出栈。 第一个栈没有元素,表示栈空。报错 */ int Queue::RemoveHead() { assert(nTopIn > -1 && nTopOut > -1); if (nTopOut > 0) { return nArrOutStack[--nTopOut]; } if (nTopIn > 0) { MoveInToOut(); return nArrOutStack[--nTopOut]; } else { cout<<"栈为空!"<<endl; assert(nTopIn == 0); return -1; } } bool Queue::IsEmpty() { if (nTopIn == 0 && nTopOut == 0) { return true; } else { return false; } } bool Queue::IsFull() { if (nTopIn == SIZE && nTopOut > 0) { return true; } else { return false; } } void Queue::MoveInToOut() { assert(nTopOut == 0); for (int i = 0;i < nTopIn;i++) { nArrOutStack[nTopIn - 1 - i] = nArrInStack[i]; } nTopOut = nTopIn; nTopIn = 0; } int main() { Queue q; for (int i = 0;i < 10;i++) { q.AppendTail(i); } cout<<"出队列序列: "; for (int i = 0;i < 3;i++) { cout<<q.RemoveHead()<<" "; } cout<<endl; if (!q.IsFull()) { q.AppendTail(1); } else { cout<<"队列已满!"<<endl; } system("pause"); return 1; }