【數據結構】棧面試題--兩個棧實現一個隊列
來源：程序員人生 發布時間：2016-12-12 15:49:05 閱讀次數：3590次
首先我們必須清楚，棧先進后出，隊列先進先出。這道他們各自的特點以后，我們用兩個棧來實現1個隊列。
下邊給出圖片：
下邊給出代碼：
template<typename T>
class Queue
{
public:
void Push(const T& x)
{
if (!_s2.empty())
{
while (!_s2.empty())
{
_s1.push(_s2.top());
_s2.pop();
}
}
_s1.push(x);
}
void Pop()
{
if (_s1.empty() && _s2.empty())//s1,s2均為空
{
return;
}
if (!_s2.empty())//s2不為空
{
_s2.pop();
}
if (!_s1.empty() && _s2.empty())//s1不為空
{
//while(!_s1.empty())
while (_s1.size() != 1)
{
_s2.push(_s1.top());//可以少push1次
_s1.pop();
}
_s1.pop();
}
}
void Display()
{
while (!_s2.empty())
{
cout << _s2.top() << " ";
_s2.pop();
}
while (!_s1.empty())
{
_s2.push(_s1.top());
_s1.pop();
}
while (!_s2.empty())
{
cout << _s2.top() << " ";
_s2.pop();
}
}
int Size()
{
return _s1.size() + _s2.size();
}
public:
stack<T> _s1;
stack<T> _s2;
};
void test()
{
Queue<int> q;
cout << q.Size() << endl;
q.Push(2);
q.Push(3);
q.Push(1);
q.Pop();
q.Push(4);
q.Push(5);
q.Pop();
cout << q.Size() << endl;
q.Display();
}
int main()
{
test();
system("pause");
return 0;
}
以上代碼的實現方法是圖片右下角的解決方案所述（即就是：push時，如果棧2不為空，將棧2的元素push進棧1，
然后，直接將新的元素push進棧1；如果棧2為空，直接push進棧1 pop時，當棧2不為空，直接從棧2pop；當棧
2為空，將棧1的元素push進棧2（可以少push1次），彈出棧頂元素）
下邊再給出另外1種實現辦法（即就是1次pop以后，棧2的元素都push進棧1，具體思路圖片中并沒有提出）：
看下邊的代碼（僅僅給出pop和push函數，其他的函數都同上）
void Push(const T& x)
{
_s1.push(x);
}
void Pop()
{
if (_s1.empty() && _s2.empty())//s1,s2均為空
{
return;
}
if (!_s2.empty())//s2不為空
{
_s2.pop();
}
else if (!_s1.empty() && _s2.empty())//s1不為空
{
//while(!_s1.empty())
while (_s1.size() != 1)
{
_s2.push(_s1.top());//可以少push1次
_s1.pop();
}
_s1.pop();
}
while (!_s2.empty())
{
_s1.push(_s2.top());
_s2.pop();
}
}
上邊代碼就實現了每次pop完以后，都將棧2中的剩余元素push進棧1，這類方法可能較第1種方法麻煩1點，但是都
可以實現。
如果以上敘述有問題，可以提出~~~
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
