剑指Offer（五）：用两个栈实现队列

2017年11月23日10:41:11 4 11,557 °C
摘要

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

剑指Offer（五）：用两个栈实现队列

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台：牛客网

书籍下载：共享资源

二、题目

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

1、思路

创建两个栈stack1和stack2，使用两个“先进后出”的栈实现一个“先进先出”的队列。

我们通过一个具体的例子分析往该队列插入和删除元素的过程。首先插入一个元素a，不妨先把它插入到stack1，此时stack1中的元素有{a}，stack2为空。再压入两个元素b和c，还是插入到stack1中，此时stack1的元素有{a,b,c}，其中c位于栈顶，而stack2仍然是空的。

这个时候我们试着从队列中删除一个元素。按照先入先出的规则，由于a比b、c先插入队列中，最先删除的元素应该是a。元素a存储在stack1中，但并不在栈顶，因此不能直接进行删除操作。注意stack2我们一直没有使用过，现在是让stack2发挥作用的时候了。如果我们把stack1中的元素逐个弹出压入stack2，元素在stack2中的顺序正好和原来在stack1中的顺序相反。因此经过3次弹出stack1和要入stack2操作之后，stack1为空，而stack2中的元素是{c,b,a}，这个时候就可以弹出stack2的栈顶a了。此时的stack1为空，而stack2的元素为{b,a}，其中b在栈顶。

因此我们的思路是：当stack2中不为空时，在stack2中的栈顶元素是最先进入队列的元素，可以弹出。如果stack2为空时，我们把stack1中的元素逐个弹出并压入stack2。由于先进入队列的元素被压倒stack1的栈底，经过弹出和压入之后就处于stack2的栈顶，有可以直接弹出。如果有新元素d插入，我们直接把它压入stack1即可。

流程示意图：

剑指Offer（五）：用两个栈实现队列

2、代码

C++:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }
 
    int pop() {
        if(stack2.empty()){
            while(stack1.size() > 0){
                int data = stack1.top();
                stack1.pop();
                stack2.push(data);
            }
        }
        int pop_element = stack2.top();
        stack2.pop();
        return pop_element;
    }
 
private:
    stack<int> stack1;
    stack<int> stack2;
};

Python2.7：

对于python来讲，栈就是用list实现的。

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        # write code here
        self.stack1.append(node)
    def pop(self):
        # return xx
        if len(self.stack2) == 0:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

weinxin
微信公众号
分享技术，乐享生活：微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论：4   其中：访客  4   博主  0

    • avatar Song 来自天朝的朋友 谷歌浏览器 Windows 10 辽宁省沈阳市 东北大学四舍(女生) 2
      回复 2018年7月21日 下午7:56  沙发

      华哥还是强啊

      • avatar Lucas 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_0 江苏省苏州市 电信 2
        回复 2019年3月3日 下午6:37  板凳

        博主请问为什么c++必须要一个临时值存pop出的2量不可以这样写stack2.push(stack1.pop());呢

          • avatar Lucas 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_0 江苏省苏州市 电信 2
            回复 2019年3月3日 下午6:44  1层

            @Lucas 解决了pop返回的是void

          • avatar John 来自天朝的朋友 谷歌浏览器 Windows 10 新疆乌鲁木齐市 电信 0
            回复 2021年12月31日 下午12:12  地板

            def deleteHead(self):
            “””
            :rtype: int/
            “””
            if self.stack2:
            return self.stack2.pop()
            while self.stack1:
            self.stack2.append(self.stack1.pop())
            return -1 if not self.stack2 else self.stack2.pop()