栈与队列的实现与应用
发布时间: 2023-12-11 16:17:13 阅读量: 12 订阅数: 12
# 第一章:栈的基本概念及实现
## 1.1 栈的定义与特性
栈是一种具有特定操作限制的线性数据结构,它的特点是后进先出(LIFO,Last In First Out)。栈的主要操作包括入栈和出栈,入栈表示将元素插入栈顶,出栈表示将栈顶元素删除并返回。栈可以通过顺序存储结构和链式存储结构来实现。
## 1.2 栈的基本操作:入栈与出栈
栈的基本操作包括入栈和出栈。入栈操作将元素插入栈顶,使之成为新的栈顶元素;出栈操作将栈顶元素删除并返回。栈还可以提供其他操作,如获取栈顶元素、判断栈是否为空、获取栈的大小等。
以下是栈的基本操作的Python代码实现:
```python
class Stack:
def __init__(self):
self.stack = []
def is_empty(self):
return len(self.stack) == 0
def push(self, value):
self.stack.append(value)
def pop(self):
if self.is_empty():
return None
return self.stack.pop()
def peek(self):
if self.is_empty():
return None
return self.stack[-1]
def size(self):
return len(self.stack)
```
## 1.3 栈的顺序存储结构
栈的顺序存储结构可以使用数组实现。使用数组作为底层数据结构,通过下标操作数组元素,使得栈的入栈和出栈操作的时间复杂度都为O(1)。栈的大小可以预先定义,当栈满时进行扩容。
以下是栈的顺序存储结构的Python代码实现:
```python
class Stack:
def __init__(self, capacity):
self.capacity = capacity
self.stack = [None] * capacity
self.top = -1
def is_empty(self):
return self.top == -1
def is_full(self):
return self.top == self.capacity - 1
def push(self, value):
if self.is_full():
return False
self.top += 1
self.stack[self.top] = value
return True
def pop(self):
if self.is_empty():
return None
value = self.stack[self.top]
self.top -= 1
return value
def peek(self):
if self.is_empty():
return None
return self.stack[self.top]
def size(self):
return self.top + 1
```
## 1.4 栈的链式存储结构
栈的链式存储结构可以使用单链表实现。链表的头部作为栈顶,每个节点存储一个元素。入栈操作将新元素插入链表头部,出栈操作删除链表头部节点。
以下是栈的链式存储结构的Python代码实现:
```python
class Node:
def __init__(self, value):
self.value = value
self.next = None
class Stack:
def __init__(self):
self.top = None
def is_empty(self):
return self.top is None
def push(self, value):
new_node = Node(value)
new_node.next = self.top
self.top = new_node
def pop(self):
if self.is_empty():
return None
value = self.top.value
self.top = self.top.next
return value
def peek(self):
if self.is_empty():
return None
return self.top.value
def size(self):
count = 0
current = self.top
while current:
count += 1
current = current.next
return count
```
## 1.5 栈的应用场景
栈在计算机领域有着广泛的应用场景:
- 表达式求值:利用栈进行中缀表达式转后缀表达式以及后缀表
0
0