# lintcode刷题——python（栈）

xiaoxiao2021-02-28  9

#### 带最小值操作的栈

##### 注意事项

class MinStack(object): def __init__(self): # do some intialize if necessary self.stack=[] def push(self, number): # write yout code here self.stack.append(number) def pop(self): # pop and return the top item in stack if self.stack!=[]: length=len(self.stack) topItem=self.stack[length-1] self.stack.pop(length-1) return topItem def min(self): # return the minimum number in stack if self.stack!=[]: return min(self.stack)

#### 用栈实现队列

pop和top方法都应该返回第一个元素的值。

class MyQueue: def __init__(self): self.stack1 = [] self.stack2 = [] def push(self, element): # write your code here self.stack1.append(element) def top(self): # write your code here # return the top element if self.stack1!=[]: return self.stack1[0] def pop(self): # write your code here # pop and return the top element if self.stack1!=[]: topItem=self.stack1[0] self.stack1.pop(0) return topItem

#### 有效的括号序列

class Solution: # @param {string} s A string # @return {boolean} whether the string is a valid parentheses def isValidParentheses(self, s): # Write your code here # 用一个栈来实现，栈最外面的元素（某个左括号）期待它对应的右括号，如果出现了匹配的右括号，则将其出栈， # 如果来的是其他的左括号，则将其压栈，如果来的是不对应的右括号，直接GG，肯定不是合法括号序列。字符串遍历完了，最终看是不是空栈。 stack=[] if s =="": return True while s!="": currentChar=s[0] s = s[1:] if currentChar=="(" or currentChar=="{" or currentChar=="[": stack.append(currentChar) elif currentChar ==")" or currentChar=="}" or currentChar=="]": lengthStack=len(stack) if lengthStack==0: return False else: if currentChar==")" and stack[lengthStack-1]=="(": stack.pop(lengthStack-1) elif currentChar=="]" and stack[lengthStack-1]=="[": stack.pop(lengthStack - 1) elif currentChar=="}" and stack[lengthStack-1]=="{": stack.pop(lengthStack - 1) else: return False if stack==[]: return True else: return False