使用C++的隊列STL實作一個棧的資料結構
實作以下四個函數:
1.push(x) : 将元素x壓入棧中
2.pop() : 彈出(移除)棧頂元素
3.top() : 傳回棧頂元素
4.empty() : 判斷棧是否是空
隊列的資料結構為先入先出,棧的資料結構為先入後出;
即隊列的元素順序與棧中元素的順序是相反的,是以隻需要保證後面插入的元素是在前面的元素之前能夠被彈出即可。
轉換成棧之後的存儲形态,彈出隊列頭部的元素即類似與彈出棧頂元素
這裡插入元素時維護一個臨時隊列,即可将原先隊列中的元素順序做一個逆置調整。
實作算法如下(文末有測試代碼):
void push(int x) {
queue<int> tmp_queue;
tmp_queue.push(x);
/*對所有原隊列的元素做順序調整*/
while (!data.empty())
{
tmp_queue.push(data.front());
data.pop();
}
/*将調整後的順序放入原隊列,此時該隊列元素順序已經為棧存儲的元素順序*/
while (!tmp_queue.empty())
{
data.push(tmp_queue.front());
tmp_queue.pop();
}
}
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
class My_stack {
private:
queue<int> data;
public:
void push(int x) {
queue<int> tmp_queue;
tmp_queue.push(x);
while (!data.empty())
{
tmp_queue.push(data.front());
data.pop();
}
while (!tmp_queue.empty())
{
data.push(tmp_queue.front());
tmp_queue.pop();
}
}
/*彈出元素,即彈出隊列頭部元素*/
int pop() {
int x = data.front();
data.pop();
return x;
}
/*此時隊列中的元素已經和棧存儲的元素同步了,直接傳回對頭元素*/
int top() {
return data.front();
}
bool empty(){
return data.empty();
}
};
int main() {
My_stack s;
cout << "construct the stack " << endl;
int tmp;
for (int i = 0;i < 5; ++i) {
cin >> tmp;
s.push(tmp);
}
cout << "top " << s.top() << endl;
cout << "pop " << s.pop() << endl;
cout << "top " << s.top() << endl;
s.push(10);
cout << "top after push '10' " << s.top() << endl;
return 0;
}
construct the stack
1 3 4 5 2
top 2
pop 2
top 5
top after push '10' 10