② 实现一个链栈及其基本操作
时间: 2023-06-23 13:10:20 浏览: 81
链栈是基于单链表实现的栈。下面是链栈的基本操作:
1. 初始化链栈:创建一个空链表,将链栈的头指针指向该链表。
2. 判断链栈是否为空:判断链栈的头指针是否为空。
3. 进栈:首先创建一个新节点,将数据存入节点中,然后将新节点插入到链表的头部。
4. 出栈:删除链表的头节点,并返回该节点的数据。
5. 清空链栈:遍历链表,逐一删除链表的每个节点。
6. 获取栈顶元素:返回链表的头节点的数据。
下面是链栈的实现代码:
```python
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class LinkedStack:
def __init__(self):
self.top = Node()
def is_empty(self):
return self.top.next is None
def push(self, data):
new_node = Node(data)
new_node.next = self.top.next
self.top.next = new_node
def pop(self):
if self.is_empty():
raise Exception("Stack is empty!")
else:
pop_node = self.top.next
self.top.next = pop_node.next
return pop_node.data
def clear(self):
self.top.next = None
def get_top(self):
if self.is_empty():
raise Exception("Stack is empty!")
else:
return self.top.next.data
```
其中,节点类 Node 包括数据域 data 和指针域 next,表示该节点的下一个节点。链栈类 LinkedStack 包括头指针 top,表示链栈的栈顶元素。is_empty() 方法判断链栈是否为空;push(data) 方法插入新节点;pop() 方法删除链表的头节点;clear() 方法清空链栈;get_top() 方法获取链栈的栈顶元素。
阅读全文