使用队列实现栈的下列操作:
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()
使用栈实现队列的下列操作:
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()
链接:https://leetcode-cn.com/problems/min-stack
设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素
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()
链接:https://leetcode-cn.com/problems/valid-parentheses
给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串,判断字符串是否有效。
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
链接: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]。
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
链接:https://leetcode-cn.com/problems/next-greater-element-ii/
一个循环数组,输出下一个比当前数字大的数字。
example:
输入: [1,2,1]
输出: [2,-1,2]
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
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
如对本文有疑问, 点击进行留言回复!!
android用Popup弹出窗(PopupWindow的使用方式)
ionic3 打包 Could not get resource ‘https://jcenter.bintray.com/com/google/zxing/core/3.2.1/core-3.2.1
NullPointerException: Attempt to invoke virtual method ‘android.content.res.XmlResourceParser androi
网友评论