题目描述1：栈和队列—用两个栈实现队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
Python测试：
// An highlighted block
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, node):
# write code here
self.stack1.append(node)
def pop(self):
# return xx
if self.stack2:
return self.stack2.pop()
elif not self.stack1:
return None
else:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
def getQueue(self):
return self.stack1
q = Solution()
q.push(1)
q.push(2)
q.push(3)
print(q.getQueue())
print(q.pop())
print(q.pop())
print(q.pop())
https://blog.csdn.net/su_bao/article/details/82346476
相关知识点回顾：
https://blog.csdn.net/cherrydreamsover/article/details/80466781
题目描述2：栈和队列—用两个队列实现栈
使用两个队列数据结构实现一个栈，要求实现栈的出栈和进栈操作。
Python测试：
// An highlighted block
class StackWithTwoQueues(object):
def __init__(self):
self._queue1 = []
self._queue2 = []
def push(self, x):
if len(self._queue1) == 0:
self._queue1.append(x)
elif len(self._queue2) == 0:
self._queue2.append(x)
if len(self._queue2) == 1 and len(self._queue1) >= 1:
while self._queue1:
self._queue2.append(self._queue1.pop(0))
elif len(self._queue1) == 1 and len(self._queue2) > 1:
while self._queue2:
self._queue1.append(self._queue2.pop(0))
def pop(self):
if self._queue1:
return self._queue1.pop(0)
elif self._queue2:
return self._queue2.pop(0)
else:
return None
def getStack(self):
print("queue1", self._queue1)
print("queue2", self._queue2)
sta = StackWithTwoQueues()
sta.push(1)
sta.getStack()
sta.push(2)
sta.getStack()
sta.push(3)
sta.getStack()
sta.push(4)
sta.getStack()
print(sta.pop())
sta.getStack()
print(sta.pop())
sta.getStack()
print(sta.pop())
sta.getStack()
https://blog.csdn.net/su_bao/article/details/82347567
相关知识点回顾：
append用法：
pop()函数
1、描述
pop() 函数用于移除列表中的一个元素（默认最后一个元素），并且返回该元素的值。
语法
pop()方法语法：
list.pop(obj=list[-1])
2、参数
obj – 可选参数，要移除列表元素的对象。
3、返回值
该方法返回从列表中移除的元素对象。
4、实例
以下实例展示了 pop()函数的使用方法：
// An highlighted block
#!/usr/bin/python
aList = [123, 'xyz', 'zara', 'abc'];
print "A List : ", aList.pop();
print "B List : ", aList.pop(2);
以上实例输出结果如下：
A List : abc
B List : zara
原文：https://blog.csdn.net/qq_36357820/article/details/77527081
https://blog.csdn.net/qq_27871973/article/details/82797258
题目描述3：滑动窗口的最大值
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
Python测试：
// An highlighted block
class Solution:
def maxInWindows(self, num, size):
# write code here
# 存放可能是最大值的下标
maxqueue = []
# 存放窗口中最大值
maxlist = []
n = len(num)
# 参数检验
if n == 0 or size == 0 or size > n:
return maxlist
for i in range(n):
# 判断队首下标对应的元素是否已经滑出窗口
if len(maxqueue) > 0 and i - size >= maxqueue[0]:
# print("len(maxqueue): ", len(maxqueue))
# print("maxqueue[0]: ", maxqueue[0])
maxqueue.pop(0)
# print("maxqueue: ", maxqueue.pop(0))
while len(maxqueue) > 0 and num[i] > num[maxqueue[-1]]:
# print("num[i]: ", num[i])
# print("num[maxqueue[-1]]: ", num[maxqueue[-1]])
maxqueue.pop()
maxqueue.append(i)
if i >= size - 1:
# print("maxlist1: ", maxlist)
maxlist.append(num[maxqueue[0]])
# print("maxlist2: ", maxlist)
return maxlist
if __name__ == "__main__":
nums = [2,3,4,2,6,2,5,1]
k = 3
s = Solution()
aa =s.maxInWindows(nums, k)
print("aa: ", aa)
相关知识点总结：
定义：栈 (Stack)是一种后进先出(last in first off，LIFO)的数据结构，而队列(Queue)则是一种先进先出 (fisrt in first out，FIFO)的结构，如下图：
我们可以使用数组来存储栈中的元素Push的时候，直接添加一个元素S[N]到数组中，Pop的时候直接返回S[N-1].
Queue是一种先进先出的数据结构，和Stack一样，他也有链表和数组两种实现，理解了Stack的实现后，Queue的实现就比较简单了。
同样地，现在再来看如何使用数组来实现Queue，首先我们使用数组来保存数据，并定义变量head和tail来记录Queue的首尾元素。
总结：
用两个栈实现队列：
https://blog.csdn.net/qq_38441207/article/details/88641068
滑动窗口的最大值：
https://blog.csdn.net/qq_38441207/article/details/88849362