232. 用棧實現(xiàn)隊列
題目鏈接：
https://leetcode.cn/problems/implement-queue-using-stacks/
思路：
準(zhǔn)備兩個棧，一個作為入棧，一個作為出棧。
入棧只存放新增的元素
出棧負(fù)責(zé)彈窗隊首元素。
push操作：把所有的元素的放在入棧中，在棧頂添加元素
pop操作：把所有元素放在出棧中，在棧頂彈出元素。
empty操作：當(dāng)兩個棧都為空時，返回true，否則返回false
代碼：
class MyQueue {
private:
stack<int> startin;
stack<int> startout;
public:
? ? MyQueue() {
? ? }
? ? void push(int x) {
? ? ? while(!startout.empty())
? ? ? {
? ? ? ? ? int val = startout.top();
? ? ? ? ? startout.pop();
? ? ? ? ? startin.push(val);
? ? ? }
? ? ? ? startin.push(x);?
? ? }
? ? int pop() {
? ? ? ? while(!startin.empty())
? ? ? ? {
? ? ? ? ? ? int val = startin.top();
? ? ? ? ? ? startin.pop();
? ? ? ? ? ? startout.push(val);
? ? ? ? }
? ? ? ? if(startout.empty())
? ? ? ? ? ? return -1;
? ? ? ? int top = startout.top();
? ? ? ? startout.pop();
? ? ? ? return top;
? ? }
? ? int peek() {
? ? ? ? int val = pop();
? ? ? ? startout.push(val);
? ? ? ? return val;
? ? }
? ? bool empty() {
? ? ? ? if(!startin.empty()||!startout.empty())
? ? ? ? ? ? return false;
? ? ? ? else
? ? ? ? ? ? return true;
? ? }
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
225. 用隊列實現(xiàn)棧
題目鏈接：
https://leetcode.cn/problems/implement-stack-using-queues/
思路：和用棧實現(xiàn)隊列不通，這題隊列2是作為隊列1的備份使用。
優(yōu)化：可以用一個隊列實現(xiàn)棧。要彈出棧頂元素，只要把隊列首元素放到隊尾，取到最后一個即可。
class MyStack {
queue<int> qin;
queue<int> qout;
int size;
public:
? ? MyStack() {
? ? ? ? size = 0;
? ? }
? ? void push(int x) {
? ? ? ? qin.push(x);
? ? ? ? cout<<"size:"<<size<<endl;
? ? ? ? size++;
? ? }
? ? int pop() {
? ? ? ? cout<<"in pop"<<endl;
? ? ? ? int new_size = size;
? ? ? ? new_size--;
? ? ? ? while(new_size!=0)
? ? ? ? {
? ? ? ? ? ? int front = qin.front();
? ? ? ? ? ? cout<<"front:"<<front<<endl;
? ? ? ? ? ? qout.push(front);
? ? ? ? ? ? qin.pop();
? ? ? ? ? ? new_size--;
? ? ? ? }
? ? ? ? int top = qin.front();
? ? ? ? qin.pop();
? ? ? ? while(!qout.empty())
? ? ? ? {
? ? ? ? ? ? int front = qout.front();
? ? ? ? ? ? qin.push(front);
? ? ? ? ? ? qout.pop();
? ? ? ? }
? ? ? ? size--;
? ? ? ? cout<<"size:"<<size<<endl;
? ? ? ? return top;
? ? }
? ? int top() {
? ? ? ? cout<<"int top"<<endl;
? ? ? ? int new_size = size;
? ? ? ? new_size--;
? ? ? ? while(new_size!=0)
? ? ? ? {
? ? ? ? ? ? int front = qin.front();
? ? ? ? ? ? cout<<"front:"<<front<<endl;
? ? ? ? ? ? qout.push(front);
? ? ? ? ? ? qin.pop();
? ? ? ? ? ? new_size--;
? ? ? ? }
? ? ? ? int top = qin.front();
? ? ? ? qin.pop();
? ? ? ? cout<<"top:"<<top<<endl;
? ? ? ? // qin.pop();
? ? ? ? qout.push(top);
? ? ? ? cout<<"====reset===="<<endl;
? ? ? ? while(!qout.empty())
? ? ? ? {
? ? ? ? ? ? int front = qout.front();
? ? ? ? ? ? cout<<"front:"<<front<<endl;
? ? ? ? ? ? qin.push(front);
? ? ? ? ? ? qout.pop();
? ? ? ? }
? ? ? ? cout<<"qin.size"<<qin.size()<<endl;
? ? ? ? cout<<"qin.front"<<qin.front()<<endl;
? ? ? ? cout<<"qin.back"<<qin.back()<<endl;
? ? ? ? return top;
? ? }
? ? bool empty() {
? ? ? ? if(qin.empty())
? ? ? ? ? ? return true;
? ? ? ? else
? ? ? ? ? ? return false;
? ? }
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/
優(yōu)化版本：
class MyStack {
public:
? ? queue<int> queue1;
? ? queue<int> queue2;
? ? MyStack() {
? ? }
? ? void push(int x) {
? ? ? ? queue1.push(x);
? ? }
? ? int pop() {
? ? ? ? int size = queue1.size();
? ? ? ? size--;
? ? ? ? while(size>0)
? ? ? ? {
? ? ? ? ? ? queue1.push(queue1.front());
? ? ? ? ? ? queue1.pop();
? ? ? ? ? ? size--;
? ? ? ? }
? ? ? ? int top = queue1.front();
? ? ? ? queue1.pop();
? ? ? ? return? top;
? ? }
? ? int top() {
? ? ? ? int top = pop();
? ? ? ? queue1.push(top);
? ? ? ? return top;
? ? }
? ? bool empty() {
? ? ? ? if(queue1.empty())
? ? ? ? ? ? return true;
? ? ? ? else
? ? ? ? ? ? return false;
? ? }
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/
