作者：b01453901 | 来源：互联网 | 2024-12-16 16:01
本章探讨了使用固定数组实现栈和队列的基本方法，以及如何通过这些基本结构来实现更复杂的操作，如获取栈中的最小值。此外，还介绍了如何利用栈来模拟队列的行为，反之亦然。
使用固定数组实现栈与队列
栈和队列是两种基本的数据结构，它们可以通过固定大小的数组来高效地实现。对于栈而言，主要通过维护一个指向栈顶位置的索引来完成元素的入栈和出栈操作。当需要添加新元素时，将其放置在当前栈顶索引处，随后索引加一；移除元素时，索引减一即可。
栈的实现代码示例：
class Stack(object):
def __init__(self, capacity=10):
self.top = -1 # top初始化为-1，表示空栈
self.capacity = capacity
self.array = [None] * self.capacity
def push(self, item):
if self.top self.top += 1
self.array[self.top] = item
else:
raise Exception('Stack Overflow')
def pop(self):
if self.top >= 0:
item = self.array[self.top]
self.top -= 1
return item
else:
raise Exception('Stack Underflow')
对于队列，我们同样可以使用固定大小的数组来实现，但需要维护两个指针，分别指向队列的头部和尾部。入队时，在尾部添加元素并移动尾部指针；出队时，从头部移除元素并移动头部指针。
队列的实现代码示例：
class Queue(object):
def __init__(self, capacity=10):
self.frOnt= 0 # 队首指针
self.rear = 0 # 队尾指针
self.capacity = capacity
self.array = [None] * self.capacity
def enqueue(self, item):
if (self.rear + 1) % self.capacity != self.front:
self.array[self.rear] = item
self.rear = (self.rear + 1) % self.capacity
else:
raise Exception('Queue Overflow')
def dequeue(self):
if self.front != self.rear:
item = self.array[self.front]
self.frOnt= (self.front + 1) % self.capacity
return item
else:
raise Exception('Queue Underflow')
实现支持获取最小值的栈
为了实现一个能够快速获取最小值的栈，我们可以采用双栈策略。其中一个栈用于存储所有元素，另一个栈则用于跟踪当前最小值。每当有新元素加入主栈时，如果该元素小于或等于辅助栈的栈顶元素（即当前最小值），则同时将其压入辅助栈。这样，辅助栈的栈顶始终代表主栈中的最小值。
支持获取最小值的栈实现代码示例：
class MinStack(object):
def __init__(self):
self.main_stack = []
self.min_stack = []
def push(self, x):
self.main_stack.append(x)
if not self.min_stack or x <= self.min_stack[-1]:
self.min_stack.append(x)
def pop(self):
if self.main_stack:
if self.main_stack[-1] == self.min_stack[-1]:
self.min_stack.pop()
return self.main_stack.pop()
else:
raise Exception('Stack is empty')
def top(self):
if self.main_stack:
return self.main_stack[-1]
else:
raise Exception('Stack is empty')
def getMin(self):
if self.min_stack:
return self.min_stack[-1]
else:
raise Exception('Stack is empty')
使用栈和队列互相实现
除了直接实现栈和队列外，我们还可以探索如何使用一种数据结构来模拟另一种。例如，使用两个栈可以实现一个队列的功能，反之，使用两个队列也可以实现一个栈的功能。
使用两个栈实现队列：
class QueueUsingStacks(object):
def __init__(self):
self.in_stack = []
self.out_stack = []
def enqueue(self, item):
self.in_stack.append(item)
def dequeue(self):
if not self.out_stack:
while self.in_stack:
self.out_stack.append(self.in_stack.pop())
if self.out_stack:
return self.out_stack.pop()
else:
raise Exception('Queue is empty')
使用两个队列实现栈：
class StackUsingQueues(object):
def __init__(self):
self.queue1 = []
self.queue2 = []
def push(self, item):
self.queue1.append(item)
def pop(self):
if not self.queue1 and not self.queue2:
raise Exception('Stack is empty')
while len(self.queue1) > 1:
self.queue2.append(self.queue1.pop(0))
last_element = self.queue1.pop(0)
# Swap the names of queue1 and queue2 for the next operation
self.queue1, self.queue2 = self.queue2, self.queue1
return last_element
京公网安备 11010802041100号