本站消息

站长简介


前每日优鲜python全栈开发工程师,自媒体达人,逗比程序猿,钱少话少特宅,我的公众号:想吃麻辣香锅

  python大神匠心打造,零基础python开发工程师视频教程全套,基础+进阶+项目实战,包含课件和源码

  出租广告位,需要合作请联系站长



+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2020-06(17)

2020-07(32)

2020-08(44)

2020-09(61)

2020-10(63)

【菜鸡刷题-牛客网NC76】两个栈形成一个队列 || python

发布于2021-01-27 16:38     阅读(915)     评论(0)     点赞(2)     收藏(2)


0

1

2

3

4

5

6




@author=yhr | 原创不易 | 转载请标明来源!|



题目描述

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

class Solution:
    def push(self, node):
        # write code here

    def pop(self):
        # return xx

思路图解

  • 重点一: 栈 、FILO 先进 后出
  • 重点二: 队列、 FIFO 先进 先出

在草稿纸上可以画出如下图:
简单的两个栈:

在这里插入图片描述

由上图,可以得到一个结论:

PUSH 统统PUSH到Stack1
POP 统统由Stack2 POP

一个小问题: Stack2 a. 为空时,b.不为空时,该怎么办?
请看下图 :)


例题: PUSH1 – PUSH2 – POP – PUSH3 – POP – POP在这里插入图片描述
可以看到上图的第三步, 需要POP的时候,Stack2为空,此时把Stack1所有的值,倒入Stack2,再由Stack2 POP。

继续。。。
在这里插入图片描述
可以看到上图的第5步, 需要POP的时候,Stack2不为空

这里很重要!此时直接从Stack2 pop。

不能从Stack1导入数据到Stack2!!

在往栈2压完一批元素后,栈1进了新的元素想往栈2压的时候,
栈2必须把上一批的元素清空了才行!!

大家可以思考一下:

为什么Stack2不为空的时候,不能从Stack1里导入数据进来?
提示关键词: 乱序,覆盖

在这里插入图片描述


上代码

初始化: 栈1 & 栈2

class Solution:
    def __init__(self):
        self.Stack1 = []
        self.Stack2 = []

PUSH – 直接压入栈1

# -*- coding:utf-8 -*-
    def push(self, node):
        '''
		 push操作就直接往stack1中push, 
		'''
        self.Stack1.insert(0, node)
   

POP – 两种情况:a. 栈2为0 , b. 栈2不为0

    def pop(self):
        '''
        pop操作需要分类一下:
        如果stack2为空,那么需要将stack1中数据转移到stack2中, 再对stack2进行pop,
        如果stack2不为空,直接pop就ok。
        
        在往栈2压完一批元素后,栈1进了新的元素想往栈2压的时候,
        栈2必须把上一批的元素清空了才行!!
        '''
        if len(self.Stack2) > 0:
            pass
        else:
            length = len(self.Stack1)
            for _ in range(length):
                self.Stack2.insert(0, self.Stack1.pop(0))
        result = self.Stack2.pop(0)
        return result
    

原文链接:https://blog.csdn.net/Aka_Happy/article/details/113179391




0

1

2

3

4

5

6

7

8

9



所属网站分类: 技术文章 > 博客

作者:精灵

链接:https://www.pythonheidong.com/blog/article/796864/fa48276f338b2e2da084/

来源:python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

2 0
收藏该文
已收藏

评论内容:(最多支持255个字符)