问题描述：用数组结构实现大小固定的栈 如：给定长度为6的数组，形成一个长度为6的栈。限制长度，如果长度超过6给用户报错
1、方法 设置一个指针index指向数组“0号”位，加入元素，index++；弹出元素，index–；
2、python实现
class ArrayStack: ''' 问题一： 数组结构实现栈 ''' def __init__(self, initsize): self.initsize = initsize ''' 定义栈的结构 ''' if self.initsize < 0: print('The init size is less than 0') self.arr = [0 for i in range(self.initsize)] self.index = 0 #def ArrayStack(self): def peek(self): ''' 返回栈顶元素函数 ''' if self.index == 0: return 0 return self.arr[self.index - 1] def push(self, num): ''' 添加元素函数： 可以让用户往栈中不断添加元素 ''' if self.index == self.initsize: print("It's wrong!") self.arr[self.index] = num self.index += 1 def pop(self): ''' 弹出元素函数: 允许用户将栈中的元素弹出 ''' if self.index == 0: print("It's wrong!") #self.arr[index] = 0 #这个可以不加，因为弹出操作其实只需要让指针变量改变位置就行，因为再添加push的时候会覆盖原先的值的 self.index -= 1 return self.arr[self.index] stacktmp = ArrayStack(3) stacktmp.push(2) print(stacktmp.arr) print(stacktmp.pop())1、问题描述 用数组结构实现大小固定的队列 方法：
三个指针变量。指针变量start用来弹出数据，用户想要弹出数据时，弹出的是start指的值；指针变量end用来添加数据，用户想要添加数据时，添加的位置是end所指向的位置；指针变量index用来判断队列中的大小，也就是队列当前的大小，它要小于等于initsize当 size = initsize时，不可以再添加元素进入队列2、python实现
class ArrayQueue: ''' 问题二： 数组结构实现队列 ''' def __init__(self, initsize): self.initsize = initsize ''' 定义队列的结构 ''' if self.initsize < 0: print('The init size is less than 0') self.arr = [0 for i in range(self.initsize)] self.index = 0 #判断队列所含元素个数指针变量 self.start = 0 #弹出元素指针变量 self.end = 0 #添加元素指针变量 def peek(self): ''' 返回队顶元素函数 ''' if self.index == 0: return 0 return self.arr[self.start] def push(self, num): ''' 添加元素函数： 可以让用户往队列中不断添加元素 ''' if self.index == self.initsize: print("It's wrong!") self.index += 1 self.arr[self.end] = num self.end = 0 if (self.end == self.initsize - 1) else self.end + 1 def pop(self): ''' 弹出元素函数: 允许用户将队列中的元素弹出 ''' if self.index == 0: print("It's wrong!") self.index -= 1 tmp = self.start #因为stat的值要减一了，所以引入一个临时变量，用来储存减一前的值 self.start = 0 if (self.start == self.initsize - 1) else self.start + 1 return self.arr[tmp] queuetmp = ArrayQueue(3) queuetmp.push(2) queuetmp.push(5) queuetmp.push(9) print(queuetmp.arr) print(queuetmp.pop()) queuetmp.push(0) print(queuetmp.arr)1、问题描述 实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返 回栈中最小元素的操作。 【要求】 1．pop、push、getMin操作的时间复杂度都是O(1)。 2．设计的栈类型可以使用现成的栈结构。
方法： 利用两个栈实现；一个叫做data栈用来存储用户添加的数据；一个叫做min栈，用来存储最小值
2、python实现
class ArrayStack: ''' 问题三： 实现特殊栈，但是先要定义一个具有基本功能的栈，然后在定义一个特殊的栈 （其中这个特殊栈的属性是普通栈的对象！！！） ''' def __init__(self, initsize): self.initsize = initsize ''' 定义栈的结构 ''' if self.initsize < 0: print('The init size is less than 0') self.arr = [0 for i in range(self.initsize)] self.index = 0 #def ArrayStack(self): def isEmpty(self): ''' 判断栈是否为空 ''' return not self.index def peek(self): ''' 返回栈顶元素函数 ''' if self.index == 0: return 0 return self.arr[self.index - 1] def push(self, num): ''' 添加元素函数： 可以让用户往栈中不断添加元素 ''' if self.index == self.initsize: print("It's wrong!") self.arr[self.index] = num self.index += 1 def pop(self): ''' 弹出元素函数: 允许用户将栈中的元素弹出 ''' if self.index == 0: print("It's wrong!") #self.arr[index] = 0 #这个可以不加，因为弹出操作其实只需要让指针变量改变位置就行，因为再添加push的时候会覆盖原先的值的 self.index -= 1 return self.arr[self.index] class Mystack: ''' 问题三： 实现特殊的栈，返回栈中最小的元素，并且要求时间复杂度O(1) ''' def __init__(self, initsize): self.stackData = ArrayStack(initsize) self.stackMin = ArrayStack(initsize) def push(self, newNum): ''' 添加元素函数： 可以让用户往栈中不断添加元素 ''' if self.stackMin.isEmpty(): #如果min栈为空，那么必须往其中添加元素 self.stackMin.push(newNum) if newNum >= self.stackMin.peek(): self.stackMin.push(self.stackMin.peek()) else: self.stackMin.push(newNum) self.stackData.push(newNum) def pop(self): ''' 弹出元素函数: 允许用户将栈中的元素弹出 ''' if self.stackData.isEmpty(): print("It's wrong!") self.stackMin.pop() return self.stackData.pop() def getMin(self): ''' 获取最小值函数： 得到栈的最小元素 ''' if self.stackMin.isEmpty(): print("It's wrong!") return self.stackMin.peek() stacktmp = Mystack(4) #限制长度 stacktmp.push(2) print(stacktmp.getMin()) stacktmp.push(4) print(stacktmp.getMin()) stacktmp.push(1) print(stacktmp.getMin()) print(stacktmp.pop()) print(stacktmp.getMin())1、问题描述 如何仅用队列结构实现栈结构？ 队列：先进先出；栈：先进后出
方法: 利用两个队列结构，一个data队列结构用来接收用户输入的数据，一个help队列- 存取除了队顶以外的所有元素，然后将data队列仅剩的一个队顶输出；
2、python实现
class ArrayQueue: ''' 问题四： 通过队列结构实现栈，因此我们需要先定义队列结构 ''' def __init__(self, initsize): self.initsize = initsize ''' 定义队列的结构 ''' if self.initsize < 0: print('The init size is less than 0') self.arr = [0 for i in range(self.initsize)] self.index = 0 #判断队列所含元素个数指针变量 self.start = 0 #弹出元素指针变量 self.end = 0 #添加元素指针变量 def isEmpty(self): ''' 判断队列是否为空 ''' return not self.index def peek(self): ''' 返回队顶元素函数 ''' if self.index == 0: return 0 return self.arr[self.start] def push(self, num): ''' 添加元素函数： 可以让用户往队列中不断添加元素 ''' if self.index == self.initsize: print("It's wrong!") self.index += 1 self.arr[self.end] = num self.end = 0 if (self.end == self.initsize - 1) else self.end + 1 def pop(self): ''' 弹出元素函数: 允许用户将队列中的元素弹出 ''' if self.index == 0: print("It's wrong!") self.index -= 1 tmp = self.start #因为stat的值要减一了，所以引入一个临时变量，用来储存减一前的值 self.start = 0 if (self.start == self.initsize - 1) else self.start + 1 return self.arr[tmp] class TwoQueueStack: ''' 通过两个队列实现栈结构 其中的属性是 队列对象 ''' def __init__(self, initsize): self.dataQueue = ArrayQueue(initsize) self.helpQueue = ArrayQueue(initsize) def push(self, newNum): ''' 用户添加元素，只存储在data队列中 ''' self.dataQueue.push(newNum) def peek(self): ''' 返回 “栈”结构的栈顶 （其实是队列的队尾元素） ''' if self.dataQueue.isEmpty(): print("队列中没有元素！") while self.dataQueue.index > 1: self.helpQueue.push(self.dataQueue.pop()) res = self.dataQueue.pop() self.helpQueue.push(res) #这里加这句的目的是因为这个函数只是想获取“栈顶”元素，不想改变data队列，不然再获取别的元素可能会出问题，因此再把获取的添加进去，然后help、data队列互换。保证pop的时候数据不变 self.swap() return res def pop(self): ''' ''' if self.dataQueue.isEmpty(): print("队列中没有元素！") while self.dataQueue.index > 1: self.helpQueue.push(self.dataQueue.pop()) res = self.dataQueue.pop() self.swap() return res def swap(self): ''' 每次取出要弹出去的result以后，将help队列和data队列互换 保证每次help队列开始时都是空队列 ''' self.dataQueue, self.helpQueue = self.helpQueue, self.dataQueue tmpStack = TwoQueueStack(3) tmpStack.push(3) tmpStack.push(4) tmpStack.push(5) print(tmpStack.peek()) print(tmpStack.pop()) print(tmpStack.pop())1、问题描述 如何仅用栈结构实现队列结构？
方法： 用两个栈结构实现；一个栈结构叫做push，用来接收用户的输入数据；一个栈结构叫做pop，只负责弹出用户数据；push“倒入”pop，即可实现数据顺序反过来了。
两个原则：
push倒入数据进入pop时，必须一次性全部倒完如果pop中有数据，则push不准倒入数据进pop2、python实现
class ArrayStack: ''' 问题五： 通过栈结构实现队列结构， 因此先要定义栈结构 ''' def __init__(self, initsize): self.initsize = initsize ''' 定义栈的结构 ''' if self.initsize < 0: print('The init size is less than 0') self.arr = [0 for i in range(self.initsize)] self.index = 0 #def ArrayStack(self): def isEmpty(self): ''' 判断栈是否为空 ''' return not self.index def peek(self): ''' 返回栈顶元素函数 ''' if self.index == 0: return 0 return self.arr[self.index - 1] def push(self, num): ''' 添加元素函数： 可以让用户往栈中不断添加元素 ''' if self.index == self.initsize: print("It's wrong!") self.arr[self.index] = num self.index += 1 def pop(self): ''' 弹出元素函数: 允许用户将栈中的元素弹出 ''' if self.index == 0: print("It's wrong!") #self.arr[index] = 0 #这个可以不加，因为弹出操作其实只需要让指针变量改变位置就行，因为再添加push的时候会覆盖原先的值的 self.index -= 1 return self.arr[self.index] class TwoStackQueue: ''' 通过两个栈结构实现队列结构 其中的属性是 栈对象 ''' def __init__(self, initsize): self.pushStack = ArrayStack(initsize) self.popStack = ArrayStack(initsize) def push(self, newNum): ''' 接受用户的输入 ''' self.pushStack.push(newNum) def peek(self): ''' 获取“队顶”函数 ''' if self.popStack.isEmpty() and self.pushStack.isEmpty(): print("Queue is empty!") self.pourIn() return self.popStack.peek() def pop(self): ''' “队列”弹出操作 ''' if self.popStack.isEmpty() and self.pushStack.isEmpty(): print("Queue is empty!") self.pourIn() return self.popStack.pop() def pourIn(self): ''' 将push栈的元素全部倒入pop栈 ''' if not self.popStack.isEmpty(): return #while not self.pushStack.isEmpty() and self.popStack.isEmpty(): #这样写结果不对。 原因：这块是个循环，希望一直跑下去的。你多加一个and在循环肯定让他可循环次数减少了，这不像条件语句一样。因此注意 while not self.pushStack.isEmpty(): print(1) self.popStack.push(self.pushStack.pop()) tmpQueue = TwoStackQueue(3) tmpQueue.push(3) tmpQueue.push(4) tmpQueue.push(5) print(tmpQueue.peek()) print(tmpQueue.pop()) print(tmpQueue.pop())