使用链表实现栈的代码,具备push和pop两个函数,并说明数链表栈的特点
时间: 2024-10-20 16:09:13 浏览: 25
链表-使用Python基于链表实现栈数据结构.zip
链表栈是一种基于链式数据结构实现的栈数据结构,它利用链表节点作为存储元素的容器,特点是动态分配空间、插入和删除操作效率较高,不需要预先设定固定大小。
下面是一个简单的链表栈的Python实现,包括`push`(入栈)和`pop`(出栈)两个基本操作:
```python
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.top = None
def push(self, item):
new_node = Node(item)
if not self.top:
self.top = new_node
else:
new_node.next = self.top
self.top = new_node
def pop(self):
if not self.is_empty():
popped_data = self.top.data
self.top = self.top.next
return popped_data
else:
return "Stack is empty"
def is_empty(self):
return self.top is None
# 示例
stack = Stack()
stack.push(1)
stack.push(2)
print(stack.pop()) # 输出:2
```
链表栈的主要特点:
1. **动态容量**:链表栈可以根据需要自动增长,无需预设最大容量。
2. **灵活性**:可以轻松地处理大量数据,因为它可以在内存允许的情况下添加新元素。
3. **高效添加和删除**:对于`push`和`pop`操作,只需要修改头节点的指向即可,时间复杂度通常是O(1)。
4. **不适合随机访问**:由于链表结构,无法像数组那样通过索引快速访问元素,查找效率较低,为O(n)。
阅读全文