使用两个栈实现一个队列,基于两个栈的PUSH、POP、Empty、Full操作实现队列的出队、入队、判断队满、判断队空操作。
时间: 2024-09-18 17:18:05 浏览: 18
使用两个栈来实现一个队列是一种常见的数据结构问题解决策略,通常这两个栈被称为“第一进制栈”和“第二出制栈”。这里我们假设队列采用先进先出(FIFO)原则。
1. **入队(enqueue)**:
- 当队列未满(即第一个栈`S1`未满)时,将元素直接压入`S1`。
2. **出队(dequeue)**:
- 如果队列不为空:
- 否则,从`S2`弹出一个元素,这代表该元素已经在`S1`中入队过一次,现在可以从`S2`移除并返回。
3. **队满(isFull)**:
- 判断`S1`是否已满,如果`S1`的容量已达到上限则队满。
4. **队空(isEmpty)**:
- 判定`S1`和`S2`是否都为空,若两者均为空,则队列为空。
以下是伪代码描述:
```python
class QueueUsingStacks:
def __init__(self):
self.S1 = Stack()
self.S2 = Stack()
def enqueue(self, item):
if not self.isFull():
self.S1.push(item)
def dequeue(self):
if not self.isEmpty():
while not self.S2.isEmpty(): # 将 S1 的所有元素移到 S2
self.S2.push(self.S1.pop())
return self.S2.pop() # 返回 S2 的顶部元素
def isFull(self):
return len(self.S1) == self.capacity # 假设栈容量为 capacity
def isEmpty(self):
return len(self.S1) == 0 and len(self.S2) == 0
```