用两个栈实现队列

原题链接 用两个栈实现队列

题目描述
用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。


首先总结一下队列(queue)以及栈(stack)的特性,在总结之前给大家推荐一下不错的C++中文在线手册:英文版:cppreference.com ,如果读起来费劲可以去:中文翻译:cppreference.com

  • queue:std::queue类是容器适配器,它给予程序员队列的功能--尤其是FIFO(现先进先出)数据结构。queue在底层容器尾端推入元素,从首端弹出元素。要实现的两个操作:
    1. push向队列尾部插入元素;
    2. pop删除第一个元素(题主曾经吃过的亏啊。划重点:C++中pop()无返回值,题目要求是有返回值的。
  • stack:std::stack类是容器适配器,它给与程序员栈的功能--特别是FILO(先进后出)数据结构。栈从被称作栈顶的容器尾部推弹元素。主要的成员函数:
    1. top():用来访问栈顶元素;
    2. empty():用来检查底层的容器是否为空;
    3. push:用来向栈顶插入元素;
    4. pop():用来删除栈顶的元素;
    5. size():用来返回容纳的元素数。

解题思路:堆栈的特性是先进后出,队列是的特性是先进先出。分别标记两个栈为S1和S2,push操作就是往S1的入栈操作,pop操作要返回S1栈底的元素,首先要判断S2是否为空,若为空,则要先将S1的元素从栈顶到栈底全部压入S2中,然后再返回S2的栈顶元素;若S2不为空,则直接返回S2的栈顶元素。(还有一个异常判断,当S1和S2都为空时,应抛出异常)

具体代码如下:

#include<iostream>
#include<stack>
#include<vector>

using namespace std;

class Solution {
public:
    void push(int Node) {
        stack1.push(Node);
    }

    int pop() {
        if(stack1.empty() && stack2.empty()) {
            throw "INPUT Valid";
        }
        else if (stack2.empty()) {
            while (!stack1.empty()) {
                int tem = stack1.top();
                stack1.pop();
                stack2.push(tem);   
            }
        }
        int res = stack2.top();
        stack2.pop();
        return res;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

void main() {
    Solution s;
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);

    s.pop();
    s.push(5);
    s.pop();
    s.pop();
    s.pop();
    s.pop();
    s.pop();
    
    system("pause");
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容