链式栈的基本操作与代码实现

更新时间:2024-04-21 05:46:30   人气:6460
# 链式栈的数据结构及基本操作的实现

链式栈是一种基于线性表顺序存储结构改进而来的数据结构,它采用链表作为底层支持来模拟“后进先出”(Last In First Out, LIFO)原则。相比于数组实现的传统栈,在元素数量不确定或者频繁进行插入、删除等动态操作的情况下,其优势更为明显。

## 1. 数据结构定义

在链式栈中,每个节点包含两个部分:`data`用于储存实际的有效负载或数据;另一个是引用下一个节点的指针 `next`。下面是一个简单的单链表结点类的设计:

python

class ListNode:
def __init__(self, data):
self.data = data
self.next = None


为了管理这个链表并提供栈的功能,我们需要创建一个 Stack 类,并在此内部维护指向栈顶位置 (即最新加入元素) 的头指针:

python

class ChainStack:
def __init__(self):
self.top = None


## 2. 基本操作及其代码实现

### (a)入栈(Push)

向链式栈添加新元素的操作被称为"push",新的元素将被放置于栈顶的位置上。以下是该操作的具体实现:

python

def push(self, item):
new_node = ListNode(item)

if not self.top: # 如果当前为空栈,则直接让new_node成为栈顶
self.top = new_node
else: # 否则把原来的栈顶移到新节点之后
new_node.next = self.top
self.top = new_node

return True # 表示成功执行了压栈操作


### (b)出栈(Pop)

从链式栈移除和返回最近进入(也就是位于栈顶)的项称为 "pop" 操作。如果尝试对空栈执行此操作通常会引发异常或者其他特殊标记以表示失败。下面是 pop 方法的实现:

python

def pop(self):
if not self.is_empty(): # 判断是否为非空栈
temp = self.top # 存储即将弹出的栈顶元素
self.top = self.top.next # 移动栈顶到下一位元素
popped_item = temp.data # 获取已保存临时变量中的原栈顶值
del(temp) # 删除无用旧栈顶对象
return popped_item # 返回刚刚取出的栈顶元素

raise Exception("Cannot Pop from empty stack.") # 对于空栈抛出错误提示


### (c)查看栈顶元素(Peek 或 Top)

无需改变堆栈内容即可检查顶部项目的方法叫做 peek 或 top。以下是如何实现在不更改栈状态的前提下获取栈顶元素:

python

def peek(self):
if not self.is_empty():
return self.top.data
else:
raise Exception("Can't Peek an Empty Stack.")

def is_empty(self):
"""判断栈是否为空"""
return bool(not self.top)


综述以上所述,链式栈通过灵活运用链表特性实现了高效的栈相关基础功能。无论是在内存分配还是时间复杂度方面,对于需要大量变动序列末尾的情况来说都是相当高效的选择。同时它的扩展性和灵活性也使得它可以应对更多复杂的场景需求。