首页 > 其他分享 >07_用队列实现栈

07_用队列实现栈

时间:2023-10-09 22:00:12浏览次数:46  
标签:元素 07 queue1 队列 queue2 栈顶 实现 int

用队列实现栈

【题目】请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(pushtoppopempty)。对应于leetcode 225题

实现 MyStack 类:

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的,返回 true ;否则,返回 false

注意:

  • 你只能使用队列的基本操作 —— 也就是 push to backpeek/pop from frontsizeis empty 这些操作。
  • 你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。

image-20231009211821309

【思路】

为了满足栈的特性。即最后入栈的元素最先出栈,在使用队列实现栈时,应满足队列前端的元素是最后入栈的元素。可以使用两个队列实现栈的操作,其中queue1用于存储栈内的元素,queue2作为入栈操作的辅助队列。

入栈操作时,首先将元素入队到queue2,然后将queue1的全部元素依次出队并入队到queue2,此时queue2的前端的元素即为新入栈的元素,再将queue1和queue2互换,则queue1的元素即为栈内的元素,queue1的前端和后端分别对应栈顶和栈底。

由于每次入栈操作都确保 queue1的前端元素为栈顶元素,因此出栈操作和获得栈顶元素操作都可以简单实现。出栈操作只需要移除 queue1的前端元素并返回即可,获得栈顶元素操作只需要获得 queue1的前端元素并返回即可(不移除元素)。

由于queue1用于存储栈内的元素,判断栈是否为空时,只需要判断 queue1是否为空即可。

实现代码如下:

class MyStack {

    // 定义两个栈
    Queue<Integer> queue1;  //存放栈中的全部元素
    Queue<Integer> queue2;  //辅助临时栈

    public MyStack() {
        this.queue1 = new LinkedList<Integer>();
        this.queue2 = new LinkedList<Integer>();
    }
    // 入栈操作,需要使用到queue2作为临时栈
    // 画出队列结构,很容易明白下述代码
    public void push(int x) {
        queue2.offer(x);  // 将元素存放到临时栈queue2
        while(!queue1.isEmpty()) {
            queue2.offer(queue1.poll());  // 将queue1中的所有元素出栈压入到queue2中
        }
        Queue<Integer> temp = queue1;
            queue1 = queue2;
            queue2 = temp;
    }
    
    public int pop() {
        return queue1.poll();
    }
    
    public int top() {
        return queue1.peek();
    }
    
    public boolean empty() {
        return queue1.isEmpty();
    }
}

标签:元素,07,queue1,队列,queue2,栈顶,实现,int
From: https://www.cnblogs.com/codingbao/p/17753280.html

相关文章

  • 实现进度条
    通过CSS过渡效果(transition)可以设置宽度的动画过渡。<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metaname="viewport"content="width=device-width,initial-scale=1.0"><t......
  • JS实现红包分配(每个人至少1分钱)
    要实现红包分配,保证每个人至少分到1分钱,可以使用以下算法:将红包总金额以及要分配的人数作为输入参数。首先,生成一个(人数-1)范围内的随机数,表示第一个人分到的金额。确保至少会有一个人分到1分钱。然后,将剩余金额(总金额减去第一个人分到的金额)作为新的红包总金额。依次......
  • jquery 轮播图,实现方式为:显示隐藏的方式
    <!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><title>Title</title><style>.box{width:380px;height:260px;position:......
  • dfa 最小化的一个丐版实现
    https://shanlunjiajian.github.io/2023/05/21/dfa-tech/好像是叫moore算法,一个vector代表一个等价类,col是所属等价类,这个是初始的时候accept状态放在一个等价类里,reject状态放在一个等价类里,其余状态放在一个等价类里。对每种出边检查同一等价类的此类出边是否指向了不......
  • v-model 原理、v-model 应用于组件 实现组件通信
    原理:v-model本质上是一个语法糖。例如应用在输入框上,就是value属性和input事件的合写(如果应用于复选框,就是checked属性和change事件的合写,下拉菜单是value属性和change事件的合写)作用:提供数据的双向绑定     ①数据变,视图跟着变  :value   ......
  • canvas实现睡眠波
    成果产品借鉴(抄袭)了华为运动健康App上对用户睡眠数据的展示,要我们也实现这种效果。App开发的同事虽然做出了一点样子,但是有点小丑,担子落到了web的头上(虽然笔者实现的效果也没有华为的好,但是还看的过去)分析与实现图形图形有点折线图和柱状图结合的意思,但是两者都不是,作为w......
  • 231007校内赛
    T1karma题解首先从贪心的思路出发把所有零多的字符串放在前面,但如下一组数据便可以卡掉201100接着我们可以来思考对于贪心的更改多举几组不同的可以卡掉的样例后可以发现如下规律先将所有字符串按\(0\)的数量排一遍序对于每一个字符串的\(0\)和\(1\)的数量我......
  • 实现签到(下)
        ......
  • 模板中实现数据绑定:
    ①内容绑定:<text>{{表达式}}</text>②属性绑定:<anyv-bind:属性名="表达式"/><any:属性名="表达式"/>③样式绑定:<any:style="{属性名:表达式}":class="{类名:表达式}"/>④事件绑定:<anyv-on:click="处理方法"/><......
  • k8s中,如何通过kubeconfig实现权限的隔离、用户的隔离?
    1、需求及背景说明 在k8s环境,如果想要实现不同的用户,可以有操作不同的命名空间的权限,对命名空间中的不同的对象有不同的操作的权限,该如何实现呢? 有什么样的使用的场景呢? 简单来说,虽然都是通过kubectl来对k8s集群进行管理的操作,但是不同的人员,通过不同的kube-config,就可......