算法训练营第10天|栈与队列基础知识总结 LeetCode 232.用栈实现队列 225.用队列实现栈

栈与队列基础知识总结 

首先要明白栈和队列不同的地方在于，栈是先入后出的结构，队列是先入先出的结构。

栈的基本操作

栈的定义：
 

stack<int>s;

入栈元素：

int x;
s.push(x);

出栈元素：

s.pop();

返回栈顶元素：

s.top();

判断栈是否为空：

s.empty();

队列的基本操作：

队列和栈的基本操作相同，有一点不同的是队列可以返回队尾元素：

queue<int>que;
int x=0;
que.push(x);
int a = que.back();//返回队尾元素

LeetCode 232.用栈实现队列

题目链接：

232. 用栈实现队列 - 力扣（LeetCode）

解题思路：

采用两个栈，一个进行元素的出队，一个作为元素的入队。

注意的是pop（）操作，当stout为空时，将stin所有元素导入stout中，进行出队操作。

peek（）操作和pop（）操作相似，可直接调用pop（），之后再把出队的元素插入回去。

代码：

class MyQueue {
public:
    stack<int>stin;
    stack<int>stout;
    MyQueue() {

    }
    
    void push(int x) {
        stin.push(x);
    }
    
    int pop() {
        if(stout.empty()){
            while(!stin.empty()){
                int tmp = stin.top();
                stin.pop();
                stout.push(tmp);
            }
        }
        int a = stout.top();
        stout.pop();
        return a;
    }
    
    int peek() {
        int a = this->pop();
        stout.push(a);
        return a;
    }
    
    bool empty() {
        return stin.empty()&&stout.empty();
    }
};

LeetCode 225. 用队列实现栈

题目链接：

225. 用队列实现栈 - 力扣（LeetCode）

解题思路：

主要难点是pop操作，首先记录quein的元素个数为n个，之后将n-1个传递给popout，将最后一个记录并弹出，之后返回记录的值，并将quein和queout两个队列交换。

代码：

class MyStack {
public:
    queue<int>quein;
    queue<int>queout;
    MyStack() {

    }
    
    void push(int x) {
        quein.push(x);
    }
    
    int pop() {
        int n = quein.size();
        while(--n){
            int a = quein.front();
            quein.pop();
            queout.push(a);
        }
        int a = quein.front();
        quein.pop();
        queue<int>tmp = quein;
        quein=queout;
        queout = tmp;
        return a;
    }
    
    int top() {
        if(!quein.empty()){
            return quein.back();
        }
        else{
            return queout.back();
        }
    }
    
    bool empty() {
        return quein.empty()&&queout.empty();
    }
};