Leetcode的AC指南 —— 栈与队列：225.用队列实现栈

摘要：
**Leetcode的AC指南 —— 栈与队列：225.用队列实现栈 **。题目介绍：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

文章目录

  • 一、题目
  • 二、解析 （go语言版）
    • 1、两个队列实现栈
    • 2、一个队列实现栈
  • 三、其他语言版本
    • Java
    • C++
    • Python

一、题目

题目介绍：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

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

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

力扣题目链接

示例 1:

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示：
1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空

进阶：

  • 你能否仅用一个队列来实现栈

二、解析 （go语言版）

1、两个队列实现栈

  • 思路：
    • 根据栈先进后出和队列先进先出的特点，
      • 将后进栈的元素放入队列的头部，实现后进先出
      • 进栈的实现：
        • 将后进栈的元素压进队列2，
        • 然后在依次将队列1中的元素压入队列2内
        • 最后交换队列1指向队列2，队列2置空
      • 出栈：直接弹出队列1的头元素。
        在这里插入图片描述
  • 时间复杂度: pop为O(n)，其他为O(1)
  • 空间复杂度: O(n)

package main

type MyStack struct {
	que1 []int
	que2 []int
}
// 栈的初始化
func Constructor() MyStack {
	return MyStack{
		que1: make([]int, 0),
		que2: make([]int, 0),
	}
}

// 将队列1中的元素压入队列2，并交换队列1和队列2
func (this *MyStack) Move() {
	if len(this.que1) == 0 { 
		// 当队列1中的没有元素后，交换队列1为队列2，队列2为空
		this.que1, this.que2 = this.que2, this.que1
	} else {
		// 将队列1中的元素依次弹出压入队列2
		this.que2 = append(this.que2, this.que1[0])
		this.que1 = this.que1[1:]
		this.Move()
	}
}

// 进栈： 向栈中添加元素
func (this *MyStack) Push(x int) {
	// 将元素压入栈2
	this.que2 = append(this.que2, x)
	// 更新栈1和栈2的数据
	this.Move()
}

// 出栈： 将队列1中的头元素弹出
func (this *MyStack) Pop() int {
	val := this.que1[0]
	this.que1 = this.que1[1:]
	return val
}

// 获取栈顶元素的值
func (this *MyStack) Top() int {
	return this.que1[0]

}

// 判断栈是否为空
func (this *MyStack) Empty() bool {
	return len(this.que1) == 0
}

2、一个队列实现栈

  • 思路：
    • 将进栈的元素放在队列的队头位置
      • 实现：
        • 将新元素压入队列的队尾
        • 将队头元素依次出队，然后在重新入队
        • 直到新压入的元素成为队头
package main

type MyStack struct {
	que []int
}

func Constructor() MyStack {
	return MyStack{
		que: make([]int, 0),
	}
}

func (this *MyStack) Push(x int) {
	// 将进栈元素压入队列
	this.que = append(this.que, x)
	// 将该元素前面的元素依次出队，在重新进队，使后进栈的元素在队头
	for i := 0; i < len(this.que)-1; i++ {
		// 将队头元素出队列
		val := this.que[0]
		this.que = this.que[1:]
		// 将出队列的队头元素入队列
		this.que = append(this.que, val)
	}
}

func (this *MyStack) Pop() int {
	val := this.que[0]
	this.que = this.que[1:]
	return val
}

func (this *MyStack) Top() int {
	return this.que[0]
}

func (this *MyStack) Empty() bool {
	return len(this.que) == 0
}

三、其他语言版本

Java

class MyStack {

    Queue<Integer> queue1; // 和栈中保持一样元素的队列
    Queue<Integer> queue2; // 辅助队列

    /** Initialize your data structure here. */
    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queue2.offer(x); // 先放在辅助队列中
        while (!queue1.isEmpty()){
            queue2.offer(queue1.poll());
        }
        Queue<Integer> queueTemp;
        queueTemp = queue1;
        queue1 = queue2;
        queue2 = queueTemp; // 最后交换queue1和queue2，将元素都放到queue1中
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue1.poll(); // 因为queue1中的元素和栈中的保持一致，所以这个和下面两个的操作只看queue1即可
    }
    
    /** Get the top element. */
    public int top() {
        return queue1.peek();
    }
    
     /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue1.isEmpty();
    }
}

C++

class MyStack {
public:
    queue<int> que1;
    queue<int> que2; // 辅助队列，用来备份
    /** Initialize your data structure here. */
    MyStack() {

    }

    /** Push element x onto stack. */
    void push(int x) {
        que1.push(x);
    }

    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int size = que1.size();
        size--;
        while (size--) { // 将que1 导入que2，但要留下最后一个元素
            que2.push(que1.front());
            que1.pop();
        }

        int result = que1.front(); // 留下的最后一个元素就是要返回的值
        que1.pop();
        que1 = que2;            // 再将que2赋值给que1
        while (!que2.empty()) { // 清空que2
            que2.pop();
        }
        return result;
    }

    /** Get the top element. */
    int top() {
        return que1.back();
    }

    /** Returns whether the stack is empty. */
    bool empty() {
        return que1.empty();
    }
};

Python

from collections import deque

class MyStack:

    def __init__(self):
        """
        Python普通的Queue或SimpleQueue没有类似于peek的功能
        也无法用索引访问，在实现top的时候较为困难。

        用list可以，但是在使用pop(0)的时候时间复杂度为O(n)
        因此这里使用双向队列，我们保证只执行popleft()和append()，因为deque可以用索引访问，可以实现和peek相似的功能

        in - 存所有数据
        out - 仅在pop的时候会用到
        """
        self.queue_in = deque()
        self.queue_out = deque()

    def push(self, x: int) -> None:
        """
        直接append即可
        """
        self.queue_in.append(x)


    def pop(self) -> int:
        """
        1. 首先确认不空
        2. 因为队列的特殊性，FIFO，所以我们只有在pop()的时候才会使用queue_out
        3. 先把queue_in中的所有元素（除了最后一个），依次出列放进queue_out
        4. 交换in和out，此时out里只有一个元素
        5. 把out中的pop出来，即是原队列的最后一个
        
        tip：这不能像栈实现队列一样，因为另一个queue也是FIFO，如果执行pop()它不能像
        stack一样从另一个pop()，所以干脆in只用来存数据，pop()的时候两个进行交换
        """
        if self.empty():
            return None

        for i in range(len(self.queue_in) - 1):
            self.queue_out.append(self.queue_in.popleft())
        
        self.queue_in, self.queue_out = self.queue_out, self.queue_in    # 交换in和out，这也是为啥in只用来存
        return self.queue_out.popleft()

    def top(self) -> int:
        """
        写法一：
        1. 首先确认不空
        2. 我们仅有in会存放数据，所以返回第一个即可（这里实际上用到了栈）
        写法二：
        1. 首先确认不空
        2. 因为队列的特殊性，FIFO，所以我们只有在pop()的时候才会使用queue_out
        3. 先把queue_in中的所有元素（除了最后一个），依次出列放进queue_out
        4. 交换in和out，此时out里只有一个元素
        5. 把out中的pop出来，即是原队列的最后一个，并使用temp变量暂存
        6. 把temp追加到queue_in的末尾
        """
        # 写法一：
        # if self.empty():
        #     return None
        
        # return self.queue_in[-1]    # 这里实际上用到了栈，因为直接获取了queue_in的末尾元素

        # 写法二：
        if self.empty():
            return None

        for i in range(len(self.queue_in) - 1):
            self.queue_out.append(self.queue_in.popleft())
        
        self.queue_in, self.queue_out = self.queue_out, self.queue_in 
        temp = self.queue_out.popleft()   
        self.queue_in.append(temp)
        return temp


    def empty(self) -> bool:
        """
        因为只有in存了数据，只要判断in是不是有数即可
        """
        return len(self.queue_in) == 0

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/336931.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

web渗透安全学习笔记：2、HTML基础知识

web渗透安全学习笔记：2、HTML基础知识

目录 前言 HTML的标题 段落链接与插入图片 HTML元素 HTML属性 HTML头部 HTML与CSS HTML与JavaScript 表格与列表 HTML区块 布局 HTML表单 HTML与数据库 音频与视频 HTML事件 前言 HTML的标题 <!DOCTYPE html> <html> <head> <meta chars…
阅读更多...
Spring+SprinMVC+MyBatis注解方式简易模板

Spring+SprinMVC+MyBatis注解方式简易模板

SpringSprinMVCMyBatis注解方式简易模板代码Demo GitHub访问 ssm-tpl-anno 一、数据准备 创建数据库test&#xff0c;执行下方SQL创建表ssm-tpl-cfg /*Navicat Premium Data TransferSource Server : 127.0.0.1Source Server Type : MySQLSource Server Version :…
阅读更多...
HCIP-BGP实验3

HCIP-BGP实验3

实验步骤 配置IP地址 R1 [r1]int g0/0/0 [r1-GigabitEthernet0/0/0]ip add 12.1.1.1 24 [r1-GigabitEthernet0/0/0]int loopback0 [r1-LoopBack0]ip add 192.168.1.1 24 [r1-LoopBack0]int loopback1 [r1-LoopBack1]ip add 192.168.2.1 24 [r1-LoopBack1]int loopback3 [r1-…
阅读更多...
OCS2 入门教程（六）- Double Integrator

OCS2 入门教程（六）- Double Integrator

系列文章目录 前言 双积分器示例是我们最简单的问题。它模拟了一个沿 x 方向移动的一维点质量。模型是线性的&#xff0c;成本函数是二次函数。目标点通过参考管理器模块设置为二次成本。 一、查看文件结构 1.1 ocs2_double_integrator 文件夹 . ├── auto_generated ├─…
阅读更多...
LSTM时间序列预测

LSTM时间序列预测

本文借鉴了数学建模清风老师的课件与思路&#xff0c;可以点击查看链接查看清风老师视频讲解&#xff1a;【1】演示&#xff1a;基于LSTM深度学习网络预测时间序列&#xff08;MATLAB工具箱&#xff09;_哔哩哔哩_bilibili % Forecast of time series based on LSTM deep learn…
阅读更多...
Pyro —— Velocity Voxel Scale

Pyro —— Velocity Voxel Scale

Velocity Voxel Scale是H19.5引入的新参数&#xff0c;该参数可单独定义volume和速度体素&#xff1b;根据参数设置&#xff0c;可观察到模拟时间的显著变化&#xff1b; Velocity Voxel Scale对DOP和SOP均可用&#xff1b;对DOP设置&#xff0c;该参数在Smoke Object&#xf…
阅读更多...
Java安全 CC链1分析

Java安全 CC链1分析

Java安全之CC链1分析 什么是CC链环境搭建jdk下载idea配置创建项目 前置知识Transformer接口ConstantTransformer类invokerTransformer类ChainedTransformer类 构造CC链1CC链1核心demo1demo1分析 寻找如何触发CC链1核心TransformedMap类AbstractInputCheckedMapDecorator类readO…
阅读更多...
RT-Thread 瑞萨 智能家居网络开发：RA6M3 HMI Board 以太网+GUI技术实践

RT-Thread 瑞萨 智能家居网络开发：RA6M3 HMI Board 以太网+GUI技术实践

不用放大了&#xff0c; 我在包里找到张不小的…… 以太网HMI线下培训-环境准备 这是社群的文档&#xff1a;【腾讯文档】以太网线下培训&#xff08;HMI-Board&#xff09; https://docs.qq.com/doc/DY0FIWFVuTEpORlNn 先介绍周六的培训是啥&#xff0c;然后再介绍一下要准…
阅读更多...
赛车游戏简单单车C语言版

赛车游戏简单单车C语言版

#include<stdio.h> #include<easyx.h> #include<time.h>#define WIDTH 512 #define HEIGHT 768//定义一个汽车类 struct FCar {//坐标float x, y;// 汽车种类int type;//汽车速度float speed; };//定义全局变量 图片坐标 IMAGE BG_IMG; //背景图片坐标 float…
阅读更多...
[小程序]使用代码渲染页面

[小程序]使用代码渲染页面

一、条件渲染 1.单个控制 使用wx:if"{{条件}}"来判断是否需要渲染这段代码&#xff0c;同时可以结合wx:elif和wx:else来判断 <view wx:if"{{type0}}">0</view> <view wx:elif"{{type1}}">1</view> <view wx:else>…
阅读更多...
linux网络协议栈2--网络包接收发送流程

linux网络协议栈2--网络包接收发送流程

上文我们讲了报文格式&#xff0c;应该对数据传输格式有了一定了解&#xff0c;这篇文章主要讲述的是网络包接收和发送的流程&#xff0c;主要是大方面来介绍。 网络包接收流程 当网络数据帧通过网络传输到达网卡时&#xff0c;网卡会将网络数据帧通过DMA的方式放到环形缓冲区…
阅读更多...
nginx日志分割

nginx日志分割

日志切割是线上常见的操作&#xff0c;能够控制单个日志文件的大小&#xff0c;便于对日志进行管理 给nginx主进程发送一个重新打开的信号&#xff0c;让nginx重新生成新的日志文件 nginx -s reopen 这个命令等同于kill -USR1 cat nginx.pid 切割日志文件shell命令 #!/bin/bas…
阅读更多...
Flink处理函数（3）—— 窗口处理函数

Flink处理函数（3）—— 窗口处理函数

窗口处理函数包括&#xff1a;ProcessWindowFunction 和 ProcessAllWindowFunction 基础用法 stream.keyBy( t -> t.f0 ).window( TumblingEventTimeWindows.of(Time.seconds(10)) ).process(new MyProcessWindowFunction()) 这里的MyProcessWindowFunction就是ProcessWi…
阅读更多...
rk1126, 实现 yolov8 目标检测

rk1126, 实现 yolov8 目标检测

基于 RKNN 1126 实现 yolov8 目标检测 Ⓜ️ RKNN 模型转换 ONNX yolo export model./weights/yolov8s.pt formatonnx导出 RKNN 这里选择输出 concat 输入两个节点 onnx::Concat_425 和 onnx::Concat_426 from rknn.api import RKNNONNX_MODEL ./weights/yolov8s.onnxRKNN_MOD…
阅读更多...
C语言练习day8

C语言练习day8

变种水仙花 变种水仙花_牛客题霸_牛客网 题目&#xff1a; 思路&#xff1a;我们拿到题目的第一步可以先看一看题目给的例子&#xff0c;1461这个数被从中间拆成了两部分&#xff1a;1和461&#xff0c;14和61&#xff0c;146和1&#xff0c;不知道看到这大家有没有觉得很熟…
阅读更多...
Spring Boot整合Redis的高效数据缓存实践

Spring Boot整合Redis的高效数据缓存实践

引言 在现代Web应用开发中&#xff0c;数据缓存是提高系统性能和响应速度的关键。Redis作为一种高性能的缓存和数据存储解决方案&#xff0c;被广泛应用于各种场景。本文将研究如何使用Spring Boot整合Redis&#xff0c;通过这个强大的缓存工具提高应用的性能和可伸缩性。 整合…
阅读更多...
对#多种编程语言 性能的研究和思考 go/c++/rust java js ruby python

对#多种编程语言 性能的研究和思考 go/c++/rust java js ruby python

对#多种编程语言 性能的研究和思考 打算学习一下rust 借着这个契机 简单的写了计算圆周率代码的各种语言的版本 比较了一下性能 只比拼单线程简单计算能力 计算十亿次循环 不考虑多线程 go/c/rust java js ruby python 耗时秒数 1:1:1:22:3:250:450 注&#xff1a;能启用则启…
阅读更多...
Python 自动化测试：数据驱动

Python 自动化测试：数据驱动

软件质量。这种测试&#xff0c;在功能测试中非常耗费人力物力&#xff0c;但是在自动化中&#xff0c;却比较好实现&#xff0c;只要实现了测试操作步骤&#xff0c;然后将多组测试数据以数据驱动的形式注入&#xff0c;就可以实现了。 前面文章学习了参数化&#xff0c;当数…
阅读更多...
【机组】算术逻辑单元带进位运算实验的解密与实战

【机组】算术逻辑单元带进位运算实验的解密与实战

​&#x1f308;个人主页&#xff1a;Sarapines Programmer&#x1f525; 系列专栏&#xff1a;《机组 | 模块单元实验》⏰诗赋清音&#xff1a;云生高巅梦远游&#xff0c; 星光点缀碧海愁。 山川深邃情难晤&#xff0c; 剑气凌云志自修。 ​ 目录 &#x1f33a;一、 实验目…
阅读更多...
MySQL锁机制与优化实践

MySQL锁机制与优化实践

数据库乐观和悲观锁 乐观锁 比如在数据库中设置一个版本字段&#xff0c;每操作一次&#xff0c;都会将这行对应的版本号1&#xff0c;这样下次更新都会拿到最新的版本号更新&#xff0c;如果一个事务拿到了版本号但是更新前其他人已经将版本号升级了&#xff0c;那么当前事务…
阅读更多...
最新文章

Copyright @ 2022~2023