題目介紹

使用STL中的兩個隊列實現一個棧，實現棧的top、pop、push、clear等操作。

思路分析

思路和使用2個棧實現一個隊列是相通的，用一個隊列queue1容器用來 壓棧，出棧的時候判斷queue1.size()是否大于1，大于1的話隊尾元素是棧頂需要彈出，這時就用到了queue2，將queue1其他的元素倒騰到queue2中，queue1中剩下的那一個元素就是棧頂的元素了。下次再繼續出棧，如果queue1中沒有元素 就判斷queue2中的元素，queue2的隊尾為棧頂，將其他元素倒騰到queue1中。

代碼展示

/*使用STL，用兩個隊列來實現一個棧，完成棧的push，pop，top，clear */ #include <queue> #include <stack> #include <iostream> using namespace std;template<typename T> class MyStack { public:void clear(){if (queue1.size() > 0)queue1.swap(queue<T>());if (queue2.size() > 0)queue2.swap(queue<T>());}T top() //棧頂就是 隊列的最后一個元素，和pop函數十分類似{while (queue1.size() > 1)//queue1的隊尾元素是棧頂元素，將其余的倒騰到queue2中去{T front = queue1.front();queue1.pop();queue2.push(front);}if (queue1.size() == 1){T front = queue1.front();//queue1.pop();return front;}while (queue2.size() > 1)//queue1沒有元素，queue2有元素，queue2的隊尾為棧頂元素，將其余的倒騰到queue1中去{T front = queue2.front();queue2.pop();queue1.push(front);}if (queue2.size() == 1){T front = queue2.front();//queue2.pop();return front;}throw std::exception("queue is empty");}void push(T data) //壓棧{queue1.push(data);}T pop() //將棧頂元素彈出{while (queue1.size() > 1)//queue1的隊尾元素是棧頂元素，將其余的倒騰到queue2中去{T front = queue1.front();queue1.pop();queue2.push(front);}if (queue1.size() == 1){T front = queue1.front();queue1.pop();return front;}while (queue2.size() > 1)//queue1沒有元素，queue2有元素，queue2的隊尾為棧頂元素，將其余的倒騰到queue1中去{T front = queue2.front();queue2.pop();queue1.push(front);}if (queue2.size() == 1){T front = queue2.front();queue2.pop();return front;}throw std::exception("queue is empty");} private:queue<T> queue1; //用來壓棧queue<T> queue2; //輔助容器 };int main(int argc, char *argv[]) {MyStack<int> stack;stack.push(1);stack.push(2);stack.push(3);int top = stack.top();//3cout << "top = " << top << endl; //3int n1 = stack.pop();int n2 = stack.pop();top = stack.top();cout << "top = " << top << endl; //1int n3 = stack.pop();cout << n1 << " "<< n2 << " " << n3 << endl; //入棧 1 2 3 ->出棧 3 2 1stack.clear();stack.push(100);stack.push(200);stack.push(300);n1 = stack.pop();n2 = stack.pop();n3 = stack.pop();cout << n1 << " " << n2 << " " << n3 << endl; //入棧 100 200 300 ->出棧 300 200 100return 0; }

運行測試

總結

以上是生活随笔為你收集整理的C/C++面试题—使用STL两个队列实现一个栈的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。