实现栈,入栈,出栈,读栈中元素
时间: 2024-10-15 10:19:23 浏览: 7
实现栈(Stack),一种数据结构,通常采用“先进后出”(Last In First Out,LIFO)的原则。你可以手动创建一个基于数组或链表的数据结构来模拟栈的行为:
1. **数组实现** (如果数组大小固定):
- **入栈(Push)**: 将新元素添加到数组的末尾。
```python
def push(arr, item):
if len(arr) == capacity:
print("Stack is full")
else:
arr.append(item)
```
- **出栈(Pop)**: 删除并返回数组顶部的元素。如果没有元素,抛出异常。
```python
def pop(arr):
if len(arr) == 0:
print("Stack is empty")
else:
return arr.pop()
```
- **读栈顶元素(Peek)**: 返回但不删除顶部元素,同样处理空栈情况。
```python
def peek(arr):
if len(arr) == 0:
print("Stack is empty")
else:
return arr[-1]
```
2. **链表实现** (动态扩容):
- **入栈(Push)**: 新节点作为当前头结点,然后将头指针向前移动。
```python
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
def push(head, item):
new_node = Node(item)
new_node.next = head
head = new_node
```
- **出栈(Pop)**: 删除头节点并返回其值,同时更新头节点。
```python
def pop(head):
if not head:
print("Stack is empty")
else:
popped_value = head.data
head = head.next
return popped_value
```
- **读栈顶元素(Peek)**: 类似于`pop`操作,但不真的移除节点。
阅读全文