首页 > 编程语言 >代码随想录算法训练营第10天 | 队列和栈基础知识、225用队列实现栈、用栈实现队列

代码随想录算法训练营第10天 | 队列和栈基础知识、225用队列实现栈、用栈实现队列

时间:2024-06-13 10:23:27浏览次数:25  
标签:10 return 队列 self 随想录 pop queue stack

232用栈实现队列
https://leetcode.cn/problems/implement-queue-using-stacks/
用栈实现队列代码随想录
https://programmercarl.com/0232.用栈实现队列.html#其他语言版本
225用队列实现栈
https://leetcode.cn/problems/implement-stack-using-queues/description/
用队列实现栈代码随想录
https://programmercarl.com/0225.用队列实现栈.html#其他语言版本

基础知识

python实现队列和栈分别使用:
栈使用列表

##
a = []
a.append(1)##push
a.pop()##pop
len(a)!=0##empty

队列使用collections.deque(其实是双向队列)

##
b = collections.deque()
b.append(2)##进队列
b.popleft()##出队列

232用栈实现队列

题目

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty):

实现 MyQueue 类:

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空,返回 true ;否则,返回 false

题解:

  • 重点在pop;
  • 合理利用两个栈;pop时,将新元素缓存在另一个栈内;
  • 一个用于进
  • 一个用于出

题解代码:

class MyQueue:

    def __init__(self):
        self.stack_in = collections.deque()
        self.stack_out = collections.deque()

    def push(self, x: int) -> None:
        self.stack_in.append(x)

    def pop(self) -> int:
        if self.empty():
            return None

        if self.stack_out:
            return self.stack_out.pop()
        for i in range(len(self.stack_in)):
            node = self.stack_in.pop()
            self.stack_out.append(node)
        node_i = self.stack_out.pop()
        return node_i


    def peek(self) -> int:
        node_1 = self.pop()
        self.stack_out.append(node_1)
        return node_1

    def empty(self) -> bool:
        if len(self.stack_in)==0 and len(self.stack_out)==0:
            return True
        else:
            return False

225用队列实现栈

题目

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。

实现 MyStack 类:

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

题解

  • 重点在pop上;top其实=先pop再push;
  • push和empty都正常;
  • 一个队列就可以实现pop;每次都把队列顺序重新排一遍,最后一个就会先弹出;

题解代码

class MyStack:

    def __init__(self):
        self.queue = collections.deque()

    def push(self, x: int) -> None:
        self.queue.append(x)


    def pop(self) -> int:
###方法一:两个队列
        if self.empty():
            return None
        for i in range(len(self.queue_1)-1):
            node_i = self.queue_1.popleft()
            self.queue_2.append(node_i)
        node = self.queue_1.popleft()
        self.queue_1,self.queue_2 = self.queue_2,self.queue_1
        return node
###方法二:一个队列
        if self.empty():
            return None
        for i in range(len(self.queue)-1):
            self.queue.append(self.queue.popleft())
        return self.queue.popleft()


    def top(self) -> int:
        tmp = self.pop()
        self.push(tmp)
        return tmp


    def empty(self) -> bool:
        if self.queue:
            return False
        else:
            return True

标签:10,return,队列,self,随想录,pop,queue,stack
From: https://www.cnblogs.com/P201821440041/p/18245321

相关文章

  • AP5101C高压线性LED恒流驱动芯片 6-100V 2A LED灯电源驱动
    产品描述AP5101C是一款高压线性LED恒流芯片,简单、内置功率管,适用于6-100V输入的高精度降压LED恒流驱动芯片。电流2.0A。AP5101C可实现内置MOS做2.0A,外置MOS可做3.0A的。AP5101C内置温度保护功能,温度保护点为130度,温度达到130度时,输出电流慢慢减小,达到保护芯片电......
  • 10.C语言for循环和跳出循环的知识点
    C语言for循环、continue和break知识点3.13for循环3.14for的一些用法3.15continue和break的作用3.16嵌套的规律3.17—作业3.13for循环概述和while的对比#include<stdio.h>intmain(){ intdata; //for(条件附初值;判断临界点;条件改变)//判断、执行循......
  • ab压测 ab会模拟10个并发用户向网站发送总共100个HTTP GET请求
    ab-n100-c10https://yiyan.baidu.com/-n100:指定总共要发送的请求数,这里是100个请求。-c10:指定并发用户数,即同时有多少个用户(或连接)在发送请求,这里是10个并发用户。https://www.163.com/:要测试的HTTPS服务器的URL。执行这个命令后,ab会模拟10个并发用户向https://w......
  • 1000平方米气膜体育馆建设费用大概是多少—轻空间
    气膜体育馆作为一种新型的建筑形式,以其快速施工、低成本和多功能的特点,正逐渐成为体育场馆建设的热门选择。那么,建设一座1000平方米的气膜体育馆需要多少费用呢?虽然具体金额会因地区和具体要求而有所不同,但我们可以通过分析主要成本构成来了解大致的投资比例。 一、基础建设......
  • 谷歌工程师指责OpenAI阻碍AGI研究进展:推迟了5到10年
    Google母公司Alphabet的一位软件工程师表示,OpenAI阻碍了人工通用智能(AGI)的发展5到10年。在最近的一次播客访谈中,Google软件工程师弗朗索瓦·乔莱特(FrançoisChollet)表达了他对AGI研究现状的担忧。这段对话被发布在了他的YouTube频道上。他表示,OpenAI“凭一己之力改变了......
  • zzulioj1042答案c语言
    ​(方法一:使用函数体)#include<stdio.h>#include<math.h>intt;//t输入这里的t是一个全局变量doubleturn(doublem,doublen,doublea,doublesum,doubleflag);intmain(){doublem,n,a,sum=0,flag=1;//m分子,n分母,a项数,sum和,flag变换符号scanf("%d",......
  • 代码随想录算法训练营第第36天 | 452. 用最少数量的箭引爆气球、435. 无重叠区间、763
    今天的三道题目,都算是重叠区间问题,大家可以好好感受一下。都属于那种看起来好复杂,但一看贪心解法,惊呼:这么巧妙!这种题还是属于那种,做过了也就会了,没做过就很难想出来。不过大家把如下三题做了之后,重叠区间基本上差不多了用最少数量的箭引爆气球https://programmercarl.co......
  • 代码随想录 算法训练营d7 哈希表 Leetcode454 四数相加2 Leetcode383 赎金信 Leetcode
    Leetcode454四数相加2 题目链接简单理解四个数组的数构成元组 相加为0思想:参考力扣第一题两数之和 才用哈希表解决问题通过将ab数组之和存储到哈希表中,并记录次数再通过计算-(c+d)去匹配哈希表如果存在那么count+=次数即可classSolution{publicintfour......
  • 代码随想录算法训练营第八天 | 344.反转字符串 541.反转字符串Ⅱ 卡玛网:54.替换数字
    344.反转字符串题目:编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组s的形式给出。不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用O(1)的额外空间解决这一问题。解题:思路:双指针,秒了点击查看代码classSolution:defreverseString......
  • Visual Studio 2022 v17.10 发布
    VisualStudio2022版本17.9 现已发布,带来了IDE各个领域的一系列性能增强。一些显着的改进包括:更快的WindowsFormsdesigner加载、更快的Razor着色、更快的解决方案加载以及减少的DLL开销。WindowsFormsdesigner加载速度此前有反馈称,在针对.NETC......