数组在数据结构中的应用：栈、队列、链表，揭示数组的广泛用途

# 1. 数组在数据结构中的基本概念

**1.1 数组的定义和特点**

数组是一种线性数据结构，它存储一系列具有相同数据类型的元素。数组中的元素使用连续的内存地址进行访问，并且可以通过索引来访问特定的元素。数组的特点包括：

- **固定大小：**数组的大小在创建时确定，并且在以后不能更改。
- **连续内存：**数组中的元素存储在连续的内存地址中，这使得对数组的访问非常高效。
- **随机访问：**可以使用索引直接访问数组中的任何元素，而无需遍历整个数组。

# 2. 数组在栈中的应用

### 2.1 栈的基本原理和操作

#### 2.1.1 栈的定义和特点

栈是一种遵循后进先出（LIFO）原则的数据结构。它类似于现实生活中的栈，后放入的物品会先被取出。栈具有以下特点：

* **后进先出：**后放入的元素会先被删除。
* **有限容量：**栈的大小是固定的，不能超过预先定义的容量。
* **只允许在栈顶进行操作：**只能对栈顶元素进行入栈和出栈操作。

#### 2.1.2 栈的常用操作

栈的常用操作包括：

* **入栈（push）：**将元素添加到栈顶。
* **出栈（pop）：**从栈顶删除元素。
* **栈顶元素（top）：**返回栈顶元素，但不删除它。

### 2.2 使用数组实现栈

#### 2.2.1 数组栈的实现原理

使用数组实现栈是一种简单有效的方法。数组中的每个元素代表栈中的一个元素，数组的第一个元素是栈顶元素。

class ArrayStack:
    def __init__(self, size):
        self.stack = [None] * size
        self.top = -1

    def is_empty(self):
        return self.top == -1

    def is_full(self):
        return self.top == len(self.stack) - 1

    def push(self, item):
        if self.is_full():
            raise IndexError("Stack is full")
        self.top += 1
        self.stack[self.top] = item

    def pop(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        item = self.stack[self.top]
        self.top -= 1
        return item

    def top_element(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.stack[self.top]

#### 2.2.2 数组栈的常见操作实现

# 创建一个容量为 5 的栈
stack = ArrayStack(5)

# 入栈
stack.push(1)
stack.push(2)
stack.push(3)

# 出栈
item = stack.pop()  # item = 3
item = stack.pop()  # item = 2

# 获取栈