栈 - 栈的实现 - 顺序栈与链式栈的实现

栈 - 栈的实现 - 顺序栈与链式栈的实现

一、栈的基本概念

栈（Stack）是一种特殊的线性数据结构，遵循后进先出（Last In First Out，LIFO）的原则。这就好比一摞盘子，最后放上去的盘子总是最先被拿走。栈有两个主要的操作：入栈（Push）和出栈（Pop）。入栈是将元素添加到栈的顶部，而出栈则是从栈的顶部移除元素。此外，还有一个查看栈顶元素的操作叫做 peek。

二、顺序栈的实现

1. 原理

顺序栈使用数组来实现栈的功能。通过一个指针（通常称为栈顶指针）来记录栈顶元素的位置。当进行入栈操作时，栈顶指针向上移动；出栈操作时，栈顶指针向下移动。

2. 代码实现（Python）

class SeqStack:
    def __init__(self, max_size=100):
        # 初始化栈，使用列表存储元素
        self.max_size = max_size
        self.stack = [None] * max_size
        self.top = -1
    def is_empty(self):
        # 判断栈是否为空
        return self.top == -1
    def is_full(self):
        # 判断栈是否已满
        return self.top == self.max_size - 1
    def push(self, item):
        # 入栈操作
        if self.is_full():
            print("Stack is full")
            return
        self.top += 1
        self.stack[self.top] = item
    def pop(self):
        # 出栈操作
        if self.is_empty():
            print("Stack is empty")
            return None
        item = self.stack[self.top]
        self.top -= 1
        return item
    def peek(self):
        # 查看栈顶元素
        if self.is_empty():
            print("Stack is empty")
            return None
        return self.stack[self.top]
# 测试顺序栈
stack = SeqStack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # 输出 3
print(stack.peek())  # 输出 2

3. 优缺点

三、链式栈的实现

1. 原理

链式栈使用链表来实现栈的功能。链表的每个节点包含一个数据元素和一个指向下一个节点的指针。栈顶元素位于链表的头部，入栈操作相当于在链表头部插入一个新节点，出栈操作相当于删除链表头部的节点。

2. 代码实现（Python）

class Node:
    def __init__(self, data):
        # 初始化节点，包含数据和指向下一个节点的指针
        self.data = data
        self.next = None
class LinkedStack:
    def __init__(self):
        # 初始化栈，栈顶指针初始化为 None
        self.top = None
    def is_empty(self):
        # 判断栈是否为空
        return self.top is None
    def push(self, item):
        # 入栈操作
        new_node = Node(item)
        new_node.next = self.top
        self.top = new_node
    def pop(self):
        # 出栈操作
        if self.is_empty():
            print("Stack is empty")
            return None
        item = self.top.data
        self.top = self.top.next
        return item
    def peek(self):
        # 查看栈顶元素
        if self.is_empty():
            print("Stack is empty")
            return None
        return self.top.data
# 测试链式栈
stack = LinkedStack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # 输出 3
print(stack.peek())  # 输出 2

3. 优缺点

四、顺序栈与链式栈的选择

• 空间固定且较小：如果栈的大小在使用过程中不会发生太大变化，并且需要快速访问元素，那么顺序栈是一个不错的选择。例如，在一些嵌入式系统中，内存资源有限，栈的大小可以提前确定，使用顺序栈可以更有效地利用内存。
• 空间动态变化：如果栈的大小在使用过程中会动态变化，那么链式栈更合适。例如，在一个表达式求值的程序中，需要处理不同长度的表达式，栈的大小无法提前确定，使用链式栈可以避免空间浪费或不足的问题。

栈是一种非常重要的数据结构，顺序栈和链式栈是栈的两种常见实现方式。通过了解它们的原理、优缺点和适用场景，我们可以根据具体的需求选择合适的实现方式。