面試題目

STL兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列。

要求：只能使用棧的pop(),top()和push()，以及測(cè)試棧是否為空 empty()四個(gè)操作. 來(lái)實(shí)現(xiàn)隊(duì)列的clear(), push(),pop(),back(),front()等操作。

思路解析

用一個(gè)棧用作隊(duì)列的容器，另一個(gè)棧用作臨時(shí)容器，由于隊(duì)列 具有先進(jìn)先出的特性，而我們的棧 只有一端可以進(jìn)出，那么我們?cè)谧龀鲫?duì)，也就是 要將一個(gè)棧的棧底元素 出隊(duì)，所以要用到另一個(gè)棧作為輔助容器。

代碼展示

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <stack> using namespace std; template<class T> class MyQueue {//對(duì)外接口 public://清空隊(duì)列void clear(){while (!stack1.empty())stack1.pop();while (!stack2.empty())stack2.pop();}//入隊(duì)void push(T data) {stack1.push(data); //stack1用來(lái) 入隊(duì)}//出隊(duì)T pop(){if (stack2.size() == 0) //stack2用來(lái) 出隊(duì)，將stack1元素倒騰到stack2{while (stack1.size() > 0){T top = stack1.top();stack1.pop();stack2.push(top);}}if (stack2.size() == 0)throw std::exception("queue is empty");T top = stack2.top();stack2.pop();return top;}//隊(duì)尾T back() //入隊(duì)的，最后一個(gè)元素{if (stack1.size() > 0) //stack1中有數(shù)據(jù)，棧頂為最后入隊(duì)的元素return stack1.top();while(stack2.size() > 0) //stack1中沒(méi)有數(shù)據(jù)，stack2中有元素，棧底為入隊(duì)的最后一個(gè)元素，將stack2中的數(shù)據(jù)倒騰到stack1{T top = stack2.top();stack2.pop();stack1.push(top);}if (stack1.size() == 0)throw std::exception("queue is empty");return stack1.top();}//隊(duì)頭T front() //出隊(duì)的，第一個(gè)元素，{if (stack2.size() == 0) //stack2用來(lái) 出隊(duì)，將stack1元素倒騰到stack2{while (stack1.size() > 0){T top = stack1.top();stack1.pop();stack2.push(top);}}if (stack2.size() == 0)throw std::exception("queue is empty");return stack2.top();} private:stack<T> stack1; stack<T> stack2; }; /* STL兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列。要求：只能使用棧的pop(),top()和push()，以及測(cè)試棧是否為空 empty()四個(gè)操作. 來(lái)實(shí)現(xiàn)隊(duì)列的clear(), push(),pop(),back(),front()等操作。 */ int main(int argc, char *argv[]) {MyQueue<int> que;que.push(1);que.push(2);que.push(3);// 出隊(duì)<- 1 2 3 <-入隊(duì)cout << que.front() << endl;//1cout << que.back() << endl; //3cout << que.pop() << endl;//1cout << que.pop() << endl;//2cout << que.pop() << endl;//3que.clear();return EXIT_SUCCESS; }

運(yùn)行結(jié)果

總結(jié)

以上是生活随笔為你收集整理的记一道面试题：STL两个栈实现一个队列。的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。