棧的特點：FILO(First In Last Out) 僅能從棧頂插入，刪除元素。 最基本的接口包括push() —— 從棧頂壓入元素 ,pop()——從棧頂彈出元素 隊列的特點：FIFO(First In First Out) 僅能從隊頭刪除元素，從隊尾插入元素。 最基本的接口包括enque()——從隊尾插入元素, deque()——從隊頭刪除元素 1.用兩個棧實現隊列 思路： 新入隊列的元素壓入stack1中，當元素出隊列時，若stack2為空，則將stack1的全部元素依次彈出，壓入stack2中，這樣stack2的棧頂元素即為隊頭元素。 [cpp] template<typename T> class MyQueue { public: T front(); T back(); void enque(const T& ele); void deque(); private: void move(std::stack<T>& from, std::stack<T>& to); private: std::stack<T> stack1; std::stack<T> stack2; }; template<typename T> void MyQueue<T>::move(std::stack<T>& from, std::stack<T>& to) { if (to.empty()) { while (!from.empty()) { to.push(from.top()); from.pop(); } } } template<typename T> T MyQueue<T>::front() { T ele; move(stack1, stack2); if (!stack2.empty()) { ele = stack2.top(); } return ele; } template<typename T> T MyQueue<T>::back() { T ele; move(stack2, stack1); if (!stack1.empty()) { ele = stack1.top(); } return ele; } template<typename T> void MyQueue<T>::enque(const T& ele) { stack1.push(ele); } template<typename T> void MyQueue<T>::deque() { move(stack1, stack2); if (!stack2.empty()) { stack2.pop(); } } 2.用兩個隊列實現棧 思路： 新元素入棧時，若兩個隊列都為空，向任意一個隊列隊尾插入元素，否則向其中一個非空隊列插入元素。棧彈出元素時，將非空隊列的元素依次刪除， 插入另一個空隊列，只留下隊尾元素(此即棧頂元素)，彈出棧頂即從隊列中刪除此元素。 [cpp] template<typename T> class MyStack { public: T top(); void push(const T& ele); void pop(); private: std::queue<T> queue1; std::queue<T> queue2; }; template<typename T> T MyStack<T>::top() { T ele; if (queue1.empty() && !queue2.empty()) { ele = queue2.back(); } else if (!queue1.empty() && queue2.empty()) { ele = queue1.back(); } return ele; } template<typename T> void MyStack<T>::push(const T& ele) { if (queue1.empty()) { queue2.push(ele); } else if (queue2.empty()) { queue1.push(ele); } } template<typename T> void MyStack<T>::pop() { if (queue1.empty()) { while(queue2.size() > 1) { queue1.push(queue2.front()); queue2.pop(); } if (!queue2.empty()) { queue2.pop(); } } else if (queue2.empty()) { www.2cto.com while(queue1.size() > 1) { queue2.push(queue1.front()); queue1.pop(); } if (!queue1.empty()) { queue1.pop(); } } }
