剑指offer题解 - 栈

Posted on | Post modified: | In
Words count in article: 910

本系列为剑指offer刷题笔记，刷题平台为牛客网。

本文主要是栈相关题目题解总结。

[TOC]

5. 用两个栈实现队列

题目描述

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

解题思路

入栈时把数据压入stack1，
出栈时若stack2不为空，直接弹出，
若stack2为空，则将stack1的全部元素压入stack2，在弹出stack2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# -*- 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 self.stack2:
            return self.stack2.pop()
        else:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
            return self.stack2.pop()

if __name__ == '__main__':
    result = Solution()
    result.push(1)
    result.push(2)
    result.pop()
    result.push(4)
    result.pop()
    result.pop()

20 包含min函数的栈

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

解题思路

使用两个栈，一个为数据栈，一个为辅助栈。数据栈用于存储所有数据，辅助栈用于存储最小值。

举个例子：
入栈时：首先往空的数字栈里压入数字3，显然现在3是最小值，我们也把最小值压入辅助栈。接下来压入数字4，由于4大于之前的最小值，因此我们只要入数据栈，不压入辅助栈。
出栈时：当数据栈和辅助栈相同，辅助栈和数据栈的栈顶元素都要出栈，否则，仅数据栈的栈顶元素出栈。
获取栈顶元素时：直接返回数据栈的栈顶元素
栈最小元素：直接返回辅助栈的栈顶元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.dataStack = []
        self.minStack = []
    def push(self, node):
        # write code here
        self.dataStack.append(node)
        if len(self.minStack) <= 0 or node < self.minStack[-1]:
                self.minStack.append(node)

    def pop(self):
        # write code here
        val = self.dataStack.pop()
        if val == self.minStack[-1]:
            self.minStack.pop()
        return val

    def top(self):
        # write code here
        return self.dataStack[-1]

    def min(self):
        # write code here
        return self.minStack[-1]

if __name__ == '__main__':
    result = Solution()
    result.push(2)
    result.push(4)
    result.push(1)
    result.push(3)
    result.pop()
    result.top()
    result.min()

21 栈的压入、弹出序列

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

解题思路

借用一个辅助的栈，遍历压栈顺序，先讲第一个放入栈中，这里是1，然后判断栈顶元素是不是出栈顺序的第一个元素，这里是4，很显然1！=4，所以我们继续压栈，直到相等以后开始出栈，出栈一个元素，则将出栈顺序向后移动一位，直到不相等，这样循环等压栈顺序遍历完成，如果辅助栈还不为空，说明弹出序列不是该栈的弹出顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# -*- coding:utf-8 -*-
class Solution:
    def IsPopOrder(self, pushV, popV):
        # write code here
        stack = []
        for x in pushV:
            stack.append(x)
            while stack and stack[-1] == popV[0]:
                stack.pop()
                popV.pop(0)
        return False if stack else True

if __name__ == '__main__':
    # 入栈：1,2,3,4,5
    # 可能的出栈：4,5,3,2,1
    # 不能的出栈：4,3,5,1,2
    result = Solution().IsPopOrder([1,2,3,4,5],[4,3,5,1,2])
    print(result)

Donate comment here
------------The End------------
0%