定义链式存储的栈(单链表实现
时间: 2024-04-27 13:20:21 浏览: 130
链式存储的栈是使用单链表实现的一种数据结构。栈是一种后进先出(LIFO)的数据结构,只允许在栈顶进行插入和删除操作。
在单链表实现的链式存储中,每个节点包含两个部分:数据域和指针域。数据域用于存储元素的值,指针域用于指向下一个节点。栈顶元素即为链表的头节点,栈底元素即为链表的尾节点。
以下是一个示例代码,展示了如何定义链式存储的栈(单链表实现):
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.top = None
def is_empty(self):
return self.top is None
def push(self, data):
new_node = Node(data)
if self.is_empty():
self.top = new_node
else:
new_node.next = self.top
self.top = new_node
def pop(self):
if self.is_empty():
return None
else:
popped_node = self.top
self.top = self.top.next
popped_node.next = None
return popped_node.data
def peek(self):
if self.is_empty():
return None
else:
return self.top.data
```
在上述代码中,定义了一个节点类 `Node`,其中包含两个属性:`data` 用于存储元素值,`next` 用于指向下一个节点。
栈类 `Stack` 包含一个属性 `top`,用于指向栈顶节点。具有以下几个方法:
- `is_empty()`:判断栈是否为空,如果栈顶为空,则返回 `True`,否则返回 `False`。
- `push(data)`:将元素 `data` 入栈,创建一个新节点,并将其指针指向当前栈顶节点,然后更新栈顶节点为新节点。
- `pop()`:出栈操作,将栈顶节点弹出,并返回其数据值。如果栈为空,则返回 `None`。
- `peek()`:查看栈顶元素的值,如果栈为空,则返回 `None`。
这样就定义了一个链式存储的栈(单链表实现)。
阅读全文