定义栈的存储结构,完成入栈、出栈、取栈顶、判断栈是否为空等基本操作的实现
时间: 2024-10-18 08:19:33 浏览: 45
栈是一种线性的数据结构,它的存储结构通常采用数组或链表的形式。在数组实现的栈中,栈顶元素位于数组的最后一个位置;而在链表实现的栈中,新元素总是添加到链表的头部。
栈的主要操作包括:
1. **入栈(Push)**:将一个元素添加到栈顶,如果使用数组,就是将元素放到数组的最后一位置;如果用链表,则是将元素链接到链表头,并更新链表头指针。
2. **出栈(Pop)**:移除并返回栈顶元素,同时更新栈的数据结构,如果是数组,将数组长度减一并将末尾元素移到前一位;对于链表,删除头节点并将其值保存。
3. **取栈顶(Top 或 Peek)**:查看但不删除栈顶元素,对数组来说,它是当前数组最后一个元素的引用;链表则是访问头节点的值。
4. **判断栈是否为空(Is Empty 或 isEmpty)**:检查栈是否还有元素,数组中可以通过比较栈顶索引和数组长度;链表中则检查头节点是否存在。
以下是使用Python举例实现一个基于列表的简单栈:
```python
class Stack:
def __init__(self):
self.items = []
# 入栈
def push(self, item):
self.items.append(item)
# 出栈
def pop(self):
if not self.is_empty():
return self.items.pop()
else:
raise Exception("Stack is empty")
# 取栈顶
def top(self):
if not self.is_empty():
return self.items[-1]
else:
raise Exception("Stack is empty")
# 判断栈是否为空
def is_empty(self):
return len(self.items) == 0
# 使用示例
s = Stack()
s.push(1)
s.push(2)
print(s.top()) # 输出:2
print(s.pop()) # 输出:2
```
阅读全文