欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

java用两个栈实现队列的push和pop

程序员文章站 2023-11-02 23:57:27
文章目录1.题目详情2.解题代码1.题目详情用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )示例 1:输入:[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”][[],[3],[],[]]输出:[null,null,3,-1]示例 2:输入:[“CQueue”,“dele...

1.题目描述

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

2.具体算法

class Solution
{
public:
    void push(int node) {
        stack1.push(node);//将node压入stack1中
    }

    int pop() {
        int ref;//定义ref为记录出栈的元素
        if(!stack2.empty())//记录stack2不为空时的情况
        {
            ref = stack2.top();
            stack2.pop();
        }
        else{
            if(!stack1.empty())//记录stack2为空,但是stack1不为空时的情况
            {
                while(!stack1.empty())
                {
                    int temp;
                    temp = stack1.top();
                    stack2.push(temp);
                    stack1.pop();
                }
                ref = stack2.top();
                stack2.pop();
            }
        }
        return ref;//返回pop出的元素值
    }

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

3.算法总结

  • 这个算法的操作很简单,但是重点是理解题目所要求的意思。用两个栈来实现队列,这个算法挺有趣的,而且在大大小小的面试和参考书上都有见过。它的push和pop操作都是指针对一个元素的出栈和入栈,不是将栈里面所有的元素都出栈和入栈,只要想清楚了这个问题,基本上就没问题了。
  • push操作:将元素压入stack1中,保存下来。
  • pop操作:分为两种情况:如果stack2是非空的,那么直接用stack2.pop()来使元素出栈;如果stack2是空的,那么只能将stack1中所有元素出栈,并按顺序压入stack2中,最后再用stack2.pop()来使栈顶元素出栈,以完成操作。

本文地址:https://blog.csdn.net/weixin_42534963/article/details/107354973