堆栈-526互联

递归函数：直接或间接调用自己的函数就叫递归函数

递归与迭代的区别：

递归使用的是选择结构

迭代使用的是循环结构

栈的应用

1、将中缀表达式转化为后缀表达式

2、将后缀表达式转化为中缀表达式

撤销、回退都是通过栈来实现的

栈不允许有遍历行为，但是可以求empty()和size()

队列也不允许有遍历行为

堆栈LIFO

队列FIFO

题目：

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

class MyQueue {
public:

    stack<int> stin;
    stack<int> stout; 

    MyQueue() {

    }
    
    void push(int x) {
        stin.push(x);
    }
    
    int pop() {
        //前提stout为空
        if(stout.empty())
        {
            while(!stin.empty())//将stin中的数全部移入stout
            {
                stout.push(stin.top());
                stin.pop();
            }

        }
            int result=stout.top();//先移入stout中再在stin中移除
            stout.pop();
            return result;


    }
    
    int peek() {
        int result=this->pop();//直接利用pop()函数
        stout.push(result);//注意要在stout中
        return result;
    }
    
    bool empty() {
        if(stin.empty() && stout.empty())
        {
            return true;
        }

        return false;

    }
};