用栈实现队列

一、思路分析

        队列遵循“先进先出”的原则，栈遵循“后进先出”的原则，基于队列和栈的特点，可以通过两个栈实现队列的功能。

        将栈分为存储栈和改变栈，存储栈负责“入队”的相关操作，将需要入队的元素通过栈的push（）函数存入存储栈。当需要出队时，首先要判断改变栈是否为空，若为空则将存储栈中的元素全部push（）到改变栈中，实现了位序颠倒，此时改变栈中的出栈次序已成为我们所需要的出队次序，当改变栈不为空时，则先要将改变栈中的元素进行出栈，此时的出栈操作等同于我们所要实现的出队操作。

        实现上述操作还要判断所涉及的栈是否为空，只有当两个栈同时为空时，我们所设计的队列才为空。

二、图形描述

        进行出队时，若改变栈为空，则将存储栈中的元素全部压入改变栈中，此时改变栈中则是我们想要的出队顺序。

        若改变栈不为空，则无须对存储栈进行操作，直接继续将改变栈中的元素出栈实现出队操作即可，重复直至改变栈为空。

 

 三、代码展示

#include <iostream>
#include <stack>

using namespace std;

class MyQueue {
    stack <int> storage;    //存储入队元素
    stack <int> change;     //将入队元素存入其中实现次序颠倒

public:
    MyQueue() {

    }
    

    //入队操作时，只需要正常调用入栈函数即可
    void push(int x) {
        storage.push(x);
    }
    

    //出栈操作时，要首先判断改变栈是否为空
    int pop() {
        //改变栈为空则将存储栈中的元素全部压入改变栈中
        //改变栈不为空则跳过压入操作继续对改变栈的元素进行操作直至为空
        if(change.empty()){
            while(!storage.empty()){
                change.push(storage.top());
                storage.pop();
            }
        }
        int flag = change.top();
        change.pop();
        return flag;
    }
    
    int peek() {
        if(change.empty()){
            while(!storage.empty()){
                change.push(storage.top());
                storage.pop();
            }
        }
        return change.top();

    }
    
    //当且仅当两个栈同时为空时，设计的队列为空
    bool empty() {
        if(storage.empty() && change.empty()){
            return true;
        }else{
            return false;
        }
    }
};