摘要:本文将介绍如何使用Python实现链栈和顺序栈,包括初始化、判断栈是否为空、入栈、出栈、获取栈顶元素以及遍历栈的操作。
正文:
在计算机科学中,栈是一种抽象数据类型,只允许在一端(称为顶部)进行插入和删除操作。根据存储方式的不同,栈可以分为链式栈和顺序栈。本文将分别介绍这两种栈的实现方法。
一、链式栈
链式栈是一种动态分配内存的栈结构,其特点是不需要预先设定栈的大小,可以根据需要动态地扩展。链式栈的基本操作包括:初始化、判断栈是否为空、入栈、出栈、获取栈顶元素以及遍历栈。
1. 初始化节点类
```python
class Node(object):
def __init__(self, values):
self.data = values
self.next = None
```
2. 初始化链栈类
```python
class LinkenStacks(object):
def __init__(self):
self.top = None
def Empty(self):
return self.top is None
def push(self, values):
newNode = Node(values)
newNode.next = self.top
self.top = newNode
def pop(self):
if self.Empty():
return '栈空,不可操作'
else:
p = self.top
self.top = self.top.next
return p
def getTopData(self):
if self.Empty():
return '栈空,不可操作'
else:
data = self.top.data
return data
# 遍历这个栈
def Traversal(self):
p = self.top
while p:
print(p.data)
p = p.next
```
3. 测试链式栈
```python
if __name__ == '__main__':
test = LinkenStacks()
test.push('a')
test.push('b')
test.push('c')
test.push('d')
test.pop()
print('获取栈顶元素:', test.getTopData())
test.Traversal()
```
二、顺序栈
顺序栈是一种基于数组实现的栈结构,其特点是需要预先设定栈的大小,当栈满时无法再添加元素。顺序栈的基本操作包括:初始化、判断栈是否为空、入栈、出栈、获取栈顶元素以及遍历栈。
1. 初始化顺序栈类
```python
class Stacks(object):
def __init__(self, MaxSize):
self.MaxSize = MaxSize
self.top = -1
self.data = [None for _ in range(self.MaxSize)]
def Empty(self):
return self.top == -1
def push(self, values):
if self.top == self.MaxSize - 1:
raise IndexError('栈满,不可操作')
else:
self.top += 1
self.data[self.top] = values
return 1
def pop(self):
if self.Empty():
return '栈空,不可操作'
else:
self.top -= 1
return self.data[self.top]
def getTopData(self):
if self.Empty():
return '栈空,不可操作'
else:
return self.data[self.top]
# 遍历顺序栈
def Traversal(self):
if self.Empty():
return '栈空,不可操作'
else:
for i in range(self.top + 1):
print(self.data[i])
```
2. 测试顺序栈
```python
if __name__ == '__main__':
test = Stacks(5)
test.push('a')
test.push('b')
test.pop()
test.push('c')
test.push('d')
test.push('e')
test.pop()
print(test.getTopData())
test.Traversal()
```
总结:本文介绍了如何使用Python实现链式栈和顺序栈,包括初始化、判断栈是否为空、入栈、出栈、获取栈顶元素以及遍历栈的操作。希望对大家有所帮助。