荐 Leetcode_栈与队列

225. 用队列实现栈

---

链接：https://leetcode-cn.com/problems/implement-stack-using-queues/solution/225-yong-dui-lie-shi-xian-zhan-by-liucx-3/

使用队列实现栈的下列操作：

push(x) – 元素 x 入栈
pop() – 移除栈顶元素
top() – 获取栈顶元素
empty() – 返回栈是否为空

解题思路

栈：洗盘子，脏盘子放最上面（尾部进），洗盘子也从最上面开始（尾部出），简称后进先出LIFO（last in first out)
队列：排队打饭先来后到，先排的（尾部进），先打到饭（头部出），简称先进先出FIFO（first in first out)

栈的顶：最先插入的元素
队的顶：最后插入的元素

deque()是双端队列，与list不同的在于deque可以对首尾进行删除操作（pop与leftpop）
因为使用队列实现栈，所以只能使用leftpop删除头

用栈表示队列：T232

代码

class MyStack(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.stack1 = deque()
        self.stack2 = deque()

    def push(self, x):
        """
        Push element x onto stack.
        :type x: int
        :rtype: None
        """
        self.stack1.append(x)

    def pop(self):
        """
        Removes the element on top of the stack and returns that element.
        :rtype: int
        """
        while len(self.stack1) > 1:
            self.stack2.append(self.stack1.popleft())
        tmp = self.stack1.popleft()
        self.stack1,self.stack2 = self.stack2,self.stack1
        return tmp


    def top(self):
        """
        Get the top element.
        :rtype: int
        """
        while len(self.stack1) > 0:
            tmp = self.stack1.popleft()
            self.stack2.append(tmp)
        self.stack1,self.stack2 = self.stack2,self.stack1
        return tmp


    def empty(self):
        """
        Returns whether the stack is empty.
        :rtype: bool
        """
        if len(self.stack1) == 0 and len(self.stack2) == 0:
            return True
        else:
            return False




# 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()

232. 用栈实现队列

---

链接：https://leetcode-cn.com/problems/implement-queue-using-stacks/solution/232-yong-zhan-shi-xian-dui-lie-by-liucx-3/

使用栈实现队列的下列操作：

push(x) – 将一个元素放入队列的尾部。
pop() – 从队列首部移除元素。
peek() – 返回队列首部的元素。
empty() – 返回队列是否为空。

解题思路

栈：洗盘子，脏盘子放最上面（尾部进），洗盘子也从最上面开始（尾部出），简称后进先出LIFO（last in first out)
队列：排队打饭先来后到，先排的（尾部进），先打到饭（头部出），简称先进先出FIFO（first in first out)

栈的顶：最先插入的元素
队的顶：最后插入的元素
pop() 函数用于移除列表中的一个元素（默认最后一个元素），并且返回该元素的值。
因为使用栈表示队列，所以只能用pop移除最后端元素。

用队列实现栈：T225

代码

class MyQueue(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.queue1 = []
        self.queue2 = []


    def push(self, x):
        """
        Push element x to the back of queue.
        :type x: int
        :rtype: None
        """
        self.queue1.append(x)


    def pop(self):
        """
        Removes the element from in front of queue and returns that element.
        :rtype: int
        """
        if self.queue2 == []:
            while len(self.queue1) != 0:
                self.queue2.append(self.queue1.pop())
        return self.queue2.pop()



    def peek(self):
        """
        Get the front element.
        :rtype: int
        """
        if self.queue2 == []:
            while len(self.queue1) != 0:
                self.queue2.append(self.queue1.pop())
        return  self.queue2[-1]


    def empty(self):
        """
        Returns whether the queue is empty.
        :rtype: bool
        """
        if self.queue1 == [] and self.queue2 == []:
            return True
        else:
            return False



# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

155. 最小栈

---

链接：https://leetcode-cn.com/problems/min-stack

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素

解题思路

• 在入栈操作时，加入一个辅助栈用来存放最小值。
• 在出栈操作是，需要把辅助栈的最后一位也删除掉
• 时间复杂度：O(1)，每步的操作都只有O(1)的复杂度
• 空间复杂度：O(N),一共插入n个元素入栈。

代码

class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.minstack = [float('inf')]


    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        self.stack.append(x)
        self.minstack.append(min(x,self.minstack[-1]))


    def pop(self):
        """
        :rtype: None
        """
        self.stack.pop()
        self.minstack.pop()
         
    def top(self):
        return self.stack[-1]

    def getMin(self):
        """
        :rtype: 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()

20. 有效的括号

---

链接：https://leetcode-cn.com/problems/valid-parentheses

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。

1. 左，右括号必须匹配。"[)" False
2. 左括号必须以正确的顺序闭合。"[(]" False
3. 空字符串是有效字符串。

解题思路

• 判断字符串是否有效的策略是本题难点：
  1. 最内层的括号一定是匹配的，匹配可删除，不匹配直接False
  2. 删掉最内层后，倒数第二层括号也是匹配的，不匹配输出False。依次内推。
  3. 最内层也就是最后的输入，最先进行计算，Last input First output（LIFO),使用栈进行处理。
• 时间复杂度：O(n),一次只对一个字符进行push或pop操作，一共n个
• 空间复杂度：O(n)，最对可能要使用len(s)=n的长度

代码

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        mapping = {"]":"[" , ")":"(","}":"{" } #用字典对括号进行匹配
        stack = []
        for x in s:
            if x not in mapping: #左括号则push
                stack.append(x)
            else: #右括号
                if not stack: # 如“]”,False
                    return False
                if mapping[x] == stack[-1]: #最顶层括号匹配了
                    stack.pop()
                else:
                    return False
        return not stack # not stack:stack为空输出True，否则False

739. 每日温度

---

链接：https://leetcode-cn.com/problems/daily-temperatures/

列表T保存n天的每日气温，输出列表result，保存比每日温度出现下一次更高温的间隔天数。没有输出0。

example:

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

解题思路

• 单调栈或队列的使用：最左或最右与当前数字相比较的题目。
• 用stack保存天数，即temperatures的下标。reslut作为结果保存间隔天数。
• 当前温度T[i]小于前一个温度T[stack[-1]]时，当前天数i入栈
• 当前温度T[i]大于前一个温度T[stack[-1]]时，stack[-1]出栈，输出需要等待的天数i-tmp_index,结果保存在result[tmp_index]。
  • 用while循环，因为要与stack栈中入栈过的都进行对比。
• 时间复杂度:O(n)，遍历n个天数
• 空间复杂度:O(n),栈最多用n个空间，result最多用n个空间

代码

class Solution(object):
    def dailyTemperatures(self, T):
        stack = []
        result = [0]*len(T)
        for i in range(len(T)):
            while stack and T[i]>T[stack[-1]]:
                tmp_index = stack.pop()
                result[tmp_index] = i - tmp_index
            stack.append(i)
        return result

503. 下一个更大元素 II

---

链接：https://leetcode-cn.com/problems/next-greater-element-ii/

一个循环数组，输出下一个比当前数字大的数字。

example:

输入: [1,2,1]
输出: [2,-1,2]

解题思路

• 本题同T739,多了一个循环，再遍历一次数组即可。
• 时间复杂度：O(2n),最长两次遍历
• 空间复杂度：O(n)

代码

class Solution(object):
    def nextGreaterElements(self, nums):
        n = len(nums)
        stack = []
        result = [-1]*n
        if not nums:
            return []
        for i in range(n):
            while stack and nums[i]>nums[stack[-1]]:
                last_index = stack.pop()
                result[last_index] = nums[i]
            stack.append(i)
        
        for i in range(n):
            while nums[i]>nums[stack[-1]]:
                last_index = stack.pop()
                result[last_index] = nums[i]
        return result

循环数组的第二种表达方式

• 用i%n取余来遍历两遍数组。
• 时空复杂度没区别，只是代码简化了

代码

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        stack = []
        result = [-1]*n
        for i in range(n*2):
            while stack and nums[i%n]>nums[stack[-1]]:
                last_index = stack.pop()
                result[last_index] = nums[i%n]
            stack.append(i%n)
        return result

本文地址：https://blog.csdn.net/weixin_43427585/article/details/107347855