数据结构 栈的操作实例详解

什么是栈？

栈（stack）是一种具有特殊限制的线性数据结构。它只允许在表的一端进行插入和删除操作，另一端是固定的，称为栈底；相反的另一端称为栈顶。栈底用于存放最早进入的元素，栈顶用于存放最近进入的元素，所以栈又称为后进先出的数据结构。

栈的操作

栈的主要操作包括入栈（push）、出栈（pop）、获取栈顶元素（top）和判断栈是否为空（isEmpty）。

入栈（push）

入栈操作是将元素放到栈顶的过程，即将元素添加到栈顶。在实现中，可以用数组或链表来作为底层储存结构，每次入栈将元素添加到数组或链表的末尾，同时更新栈顶指针。

以下是一个使用链表实现的入栈示例：

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

class Stack:
    def __init__(self):
        self.top = None
        self.size = 0

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node
        self.size += 1

出栈（pop）

出栈操作是将栈顶元素弹出的过程，即将栈顶元素删除。同样地，在实现中，我们可以用数组或链表来作为底层储存结构，每次出栈将数组或链表的末尾元素或链表头元素删除，并更新栈顶指针。

以下是一个使用数组实现的出栈示例：

class Stack:
    def __init__(self):
        self.items = []

    def push(self, data):
        self.items.append(data)

    def pop(self):
        return self.items.pop()

获取栈顶元素（top）

获取栈顶元素的操作是仅返回栈顶元素但不将它弹出的过程。

以下是一个使用链表实现的获取栈顶元素示例：

class Stack:
    def __init__(self):
        self.top = None
        self.size = 0

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node
        self.size += 1

    def top(self):
        if self.top:
            return self.top.data
        return None

判断栈是否为空（isEmpty）

判断栈是否为空的操作是判断栈是否没有任何元素的过程。通常，我们可以通过判断栈顶指针是否为空来判断栈是否为空。

以下是一个使用数组实现的判断栈是否为空示例：

class Stack:
    def __init__(self):
        self.items = []

    def push(self, data):
        self.items.append(data)

    def pop(self):
        return self.items.pop()

    def isEmpty(self):
        return len(self.items) == 0

示例说明

下面给出两个示例，分别演示栈的入栈和出栈操作。

示例一：入栈操作

stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.top.data)  # 3

在上面的示例中，我们创建了一个空栈，并连续入栈了三个元素。由于栈的特性，栈顶元素为最后入栈的元素3。

示例二：出栈操作

stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # 3
print(stack.pop())  # 2

在上面的示例中，我们创建了一个空栈，并连续入栈了三个元素。接着，我们两次出栈操作，分别将栈顶元素2和3弹出。