chapter6-stack-and-queue-algorithm

Posted on | In | | Visitors: ℃
Words count in article: 1.4k | Reading time ≈ 6

chapter6-stack-and-queue-algorithm

栈和队列算法

[TOC]

1. 用栈实现队列

Leetcode / 力扣

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class MyQueue:
    # 栈：先进后出 队列：先进先出
    # 一个(队列的形式)等价于(值压入一个栈，然后在压入一个栈)
    # 注意点，在于输出值时和判断为空的时候，如何进行处理
    # 1.因为要两个栈进行实现队列，所以判断队列是否为空，就需要判断两个栈是否为空
    # 输出时，如果第二个栈没有值了，就需要判断第一个栈是否有值，如果有就需要去把值压入第一个栈中。
    # 代码逻辑如下：
    def __init__( self ):
        """
        Initialize your data structure here.
        """
        self.stack1 = []
        self.stack2 = []

    # 直接压入
    def push( self, x: int ) -> None:
        """
        Push element x to the back of queue.
        """
        self.stack1.append(x)

    # stack1的输出到stack2，然后从stack2中输出
    def pop( self ) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        self.stack1TOstack2()
        return self.stack2.pop()

    def stack1TOstack2(self):
        if not self.stack2:
            while(self.stack1):
                self.stack2.append(self.stack1.pop())

    def peek( self ) -> int:
        """
        Get the front element.
        """
        self.stack1TOstack2()
        return  self.stack2[-1]

    def empty( self ) -> bool:
        """
        Returns whether the queue is empty.
        """
        if not self.stack1 and not self.stack2:
            return True

# Your MyQueue object will be instantiated and called as such:
# x = 1
# obj = MyQueue()
# obj.push(x)
# param_3 = obj.peek()
# param_2 = obj.pop()
# param_4 = obj.empty()
2. 用队列实现栈

Leetcode / 力扣

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
36
37
38
39
40
41
42
43
44
45
46
47
import queue
class MyStack:
    # 栈：先进后出 队列：先进先出
    # 由于队列先进先出的。如果我出一个数，然后再进，他就算后进了
    # 因此代码逻辑如下：
    def __init__( self ):
        """
        Initialize your data structure here.
        """
        self.q = queue.Queue()


    def push( self, x: int ) -> None:
        """
        Push element x onto stack.
        """
        self.q.put(x)
        qsize = self.q.qsize()
        for i in range(qsize):
            self.q.put(self.q.get())

    def pop( self ) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        return self.q.get()

    def top( self ) -> int:
        """
        Get the top element.
        """
        v = self.q.get()
        self.q.put(v)
        return v

    def empty( self ) -> bool:
        """
        Returns whether the stack is empty.
        """
        return self.q.empty()

# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()
3. 最小值栈

Leetcode / 力扣

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
36
37
38
39
40
class MinStack:
    # 建立两个栈
    # 其中一个栈保存当前存储的数据
    # 其中一个栈保存截止当前的最小值
    # 注意点：
    # 1. 当抛出一个数后，记得更新当前的最小值
    # 2. 压栈和出栈，两个栈都需要同步执行
    def __init__( self ):
        """
        initialize your data structure here.
        """
        self.dataStack = []
        self.minStack = []
        self.minv = float('inf')

    def push( self, x: int ) -> None:
        self.minv = min(x,self.minv)
        self.dataStack.append(x)
        self.minStack.append(self.minv)

    def pop( self ) -> None:
        self.dataStack.pop()
        self.minStack.pop()
        if not self.minStack:
            self.minv = float('inf')
        else:
            self.minv = self.minStack[-1]

    def top( self ) -> int:
        return  self.dataStack[-1]

    def getMin( self ) -> int:
        return self.minStack[-1]

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
4. 用栈实现括号匹配

Leetcode / 力扣

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
def isValid():
    # 首先，这道题符合贪婪算法
    # 在这里用栈进行构建
    # 代码逻辑如下：因为够简单，我也不知道怎么讲
    # 一把suo？
    s = "()[]{}"
    s1 = "([{"
    s2 = ")]}"
    stack = []
    for c in s:
        if c in s1:
            stack.append(c)
        else:
            if not stack:
                return False
            cc= stack.pop()
            b1 = (cc == s1[0] and c != s2[0])
            b2 = (cc == s1[1] and c != s2[1])
            b3 = (cc == s1[2] and c != s2[2])
            if b1 or b2 or b3:
                return False
    print(stack)
    if not stack:
        return True
    return False
isValid()
数组中元素与下一个比它大的元素之间的距离

Leetcode / 力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 739. 每日温度
def dailyTemperatures():
    # 理解题目-"‘你需要再等待多久温度才会升高超过该日’的‘天数’" 下标是天数
    # 意为就是从第一天开始遍历，在当前天下，其比当前天温度高，切且最近天的距离。
    # 比如第一天index=0，t=73，他最近比他高的温度是74，也就是第二天index=1
    # 因此从本体难点就在于，如何去找到，比当前温度高，且最近的天
    # 所以需要使用一种数据结构栈
    # 栈-先进后出，那么栈顶总是保留当前的温度的index，并且我们需要从右遍历到左
    # 这样就能够保证每次当前温度，是最近比他大的温度进行比较，才能够算出正确的天数距离

    T = [73, 74, 75, 71, 69, 72, 76, 73]
    ts,res = [], [0]*len(T)

    t1, n = T[0], len(T)
    for curIndex in range(n-1,-1,-1):
        while(ts and T[curIndex] >= T[ts[-1]]):
            ts.pop()
        if ts:
            res[curIndex] = ts[-1] - curIndex
        ts.append(curIndex)

    print(res)
    return res
dailyTemperatures()
5. 循环数组中比当前元素大的下一个元素

Leetcode / 力扣

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
def nextGreaterElements():
    nums = [1,1,2,1]
    # 又题意可知
    # 难点解析：
    # 1. 因为是循环数组，如何去遍历当前数后面的位置
    # 2. 如何去保留没有找到最近比他的数
    # 3. 理解什么是最近，如果当前下表为i，如果所有数都满足比他大，那么i+1是最近，而i-1是最远的一个。
    # 因此遍历2*Len(nums)长度能够很好的满足历史值的要求
    # 依据就近原则，栈的结构能够很好的满足，此题要求-后进先出
    # 后进先出，能够保证栈顶的元素是当前与遍历值最近的值，并且能够很好的保留历史不满足要求的值
    # 即代码逻辑如下：
    # 其中，我们遍历2*Len(nums)长度的值，能够解决循环数组特点，遍历历史值

    nl = len(nums)
    dstack, res = [], [-1]*(nl)
    for n in range(0,2*nl):
        num = nums[n%nl]
        while(dstack and num > nums[dstack[-1]]):
            res[dstack.pop()] = num
        if n < nl:
            dstack.append(n)
    print(res)
    return res



nextGreaterElements()