牛客网---栈与队列（python实现）

喜欢ヅ旅行 2022-10-23 12:42 194阅读 0赞

### 冲呀 ###

*   *   *  一：使用两个栈实现一个队列（栈）：
         *  二: 使用两个队列实现一个栈（队列）：
         *  三：括号序列（栈）：
         *  四：设计getMin功能的栈（栈）：
         *  五： 中缀表达式转换成后缀表达式(逆波兰式)：
         *  六：表达式求值：

### 一：使用两个栈实现一个队列（栈）： ###

思想：**push的时候正常， pop的时候，我们先把栈1的元素全部pop到栈2中， 然后栈2中pop出顶端的元素，最后再把栈2剩余的元素pop到栈1中去。**

class Solution:
        def __init__(self):
            self.stack1 = []
            self.stack2 = []
            
        def push(self, node):
            self.stack1.append(node)
            
        def pop(self):
            while(self.stack1):
                self.stack2.append(self.stack1.pop())
            res = self.stack2.pop()
            while(self.stack2):
                self.stack1.append(self.stack2.pop())
            return res

### 二: 使用两个队列实现一个栈（队列）： ###

思想： **入队列的时候，直接入队列1；出队列的时候，一直pop(0)到队列2中,直到队列1中只有一个。然后交换队列1和队列2。**

class Stock:
        def __init__(self):
            self.queueA=[]
            self.queueB=[]
        def push(self, node):
            self.queueA.append(node)
        def pop(self):
            if len(self.queueA)==0:
                return None
            while len(self.queueA)!=1:
                self.queueB.append(self.queueA.pop(0))
            self.queueA,self.queueB=self.queueB,self.queueA #交换是为了下一次的pop
            return self.queueB.pop()

### 三：括号序列（栈）： ###

思想： **使用一个字典存储左右括号（根据右括号能够查询到左括号）， 然后遍历字符串。如果这个栈存在元素，或者字符在字典中，然后判断栈的顶端是不是等于字典中的那个值，如果是则栈顶出栈。如果不是则直接returnFalse。如果栈是空的，或者在字典中查询不到（也就是左括号），则进行入栈。最终如果栈中还有元素则返回False,如果不存在了则返回True。**

class Solution:
        def isValid(self , s ):
            my_dict = {
        ')': '(', ']':'[', '}':'{'}
            stack = list()
            for i in s:
                if stack and i in my_dict:
                    if stack[-1] == my_dict[i]:
                        stack.pop()
                    else:
                        return False
                else:
                    stack.append(i)
            return not stack

### 四：设计getMin功能的栈（栈）： ###

实现一个特殊功能的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。

思路： 使用两个栈来实现： stack\_min 和my\_satck两个栈， my\_satck正常进栈和出栈， 而stack\_min用来保存与my\_satck中对应位置的最小值。

过程：**开始的时候两个分别进栈一个元素，当再次进栈的时候，my\_satck正常进栈，而stack\_min要看看这个元素是否小于栈顶的元素，如果小于栈顶元素则进栈，如果大于栈顶元素则说明最小的还是栈顶的元素，则栈顶元素再次进栈。对于出栈的时候，两个栈同时出栈即可。**

class Solution:
        def __init__(self):
            self.my_stack = [] # 正常栈
            self.stack_min = []   # 最小栈
            
        def push(self, num):
            # 如果是第一次入栈则直接赋值
            if len(self.my_stack) == 0:
                self.my_stack.append(num)
                self.stack_min.append(num)
            else:
                self.my_stack.append(num) # 正常栈入栈
                if self.stack_min[-1] > num: # 如果最小栈栈顶元素比增加这个大，需要增加新元素
                    self.stack_min.append(num)
                else: # 如果不是则，将栈顶元素重复加入
                    self.stack_min.append(self.stack_min[-1])
        
        def pop(self):
            num = self.my_stack.pop()
            self.stack_min.pop()
            return num
        
        def get_Min(self):
            return self.stack_min[-1]
        
        def getMinStack(self , op ):
            # 遍历二维数组
            res = []
            for i in op:
                if i[0] == 1:
                    self.push(i[1])
                if i[0] == 2:
                    self.pop()
                if i[0] == 3:
                    res.append(self.get_Min())
            return res

### 五： 中缀表达式转换成后缀表达式(逆波兰式)： ###

如果遇到数字，直接将该数字输出到后缀表达式  
如果遇到左括号，入栈；  
如果遇到右括号，不断输出栈顶元素，直至遇到左括号（左括号出栈，但不输出）；  
如果遇到其他运算符，不断去除所有运算优先级大于等于当前运算符的运算符，输出。最后，新的符号入栈；  
把栈中剩下的符号依次输出，表达式转换结束。

### 六：表达式求值： ###

请写一个整数计算器，支持加减乘三种运算和括号。

思路： 先将中缀表达式转换成后缀表达式，然后根据后缀表达式进行计算。