队列和栈
队列的基本操作
1.队列：先进先出，与栈操作不同，push操作为在队头加入元素，而pop操作是从队尾弹出一个元素。
栈和队列的基本操作都是时间复杂度为O(1)的操作
队列可以理解为一条直线，操作在两端执行，而栈理解为一条射线，只在一端操作。
案例一：编写一个类,只能用两个栈结构实现队列,支持队列的基本操作(push，pop)。（逻辑）
给定一个操作序列ope及它的长度n，其中元素为正数代表push操作，为0代表pop操作，保证操作序列合法且一定含pop操作，请返回pop的结果序列。
测试样例：
[1,2,3,0,4,0],6
返回：[1,2]
mycode
class TwoStack:
def twoStack(self, ope, n):
# write code here
stack1 = []
stack2 = []
result = []
for i in ope:
if i == 0:
if not stack2:
while stack1:
stack2.append(stack1.pop())
result.append(stack2.pop())
else:
stack1.append(i)
return result注意事项：
- 如果将1栈的数据倒入二栈，必须一次性倒空
- 如果2栈有数的话不能向2栈中加入数
案例二：实现一个栈的逆序，但是只能用递归函数和这个栈本身的pop操作来实现，而不能自己申请另外的数据结构。（递归）
给定一个整数数组A即为给定的栈，同时给定它的大小n，请返回逆序后的栈。
测试样例：
[4,3,2,1],4返回：[1,2,3,4]
思路
首先分析只能在本身的基础上实现，所以空间复杂度为O（1），可以通过两个递归函数来实现，辅助函数为取出栈底元素，并返回，栈底以上的元素不变。
def pop_zhandi(self,A):
result = A.pop()
if not A:
return result
else:
last = self.pop_zhandi(A)
A.append(result)
return last其次通过主函数的递归函数，选择最后出栈的函数重新压入到栈中。倒序压入，最后便可以形成栈的逆序。
class StackReverse:
def reverseStack(self, A, n):
# write code here
if not A:
return
a = self.pop_zhandi(A)
self.reverseStack(A,n-1)
A.append(a)
return A
def pop_zhandi(self,A):
result = A.pop()
if not A:
return result
else:
last = self.pop_zhandi(A)
A.append(result)
return last
京公网安备 11010502036488号