栈与队列在编程中的应用

# 1. 栈与队列简介

## 1.1 栈的概念与特点
栈（Stack）是一种具有后进先出（Last In First Out，LIFO）特性的数据结构，类似于我们日常生活中的栈（如书堆）。栈的操作主要包括入栈（Push）和出栈（Pop），入栈将元素放入栈顶，出栈将栈顶元素移除。栈常用于实现函数调用、表达式求值、浏览器历史记录等场景。

## 1.2 队列的概念与特点
队列（Queue）是一种具有先进先出（First In First Out，FIFO）特性的数据结构，类似于排队等待的场景。队列的操作主要包括入队（Enqueue）和出队（Dequeue），入队将元素加入队尾，出队将队首元素移除。队列常用于实现消息队列、线程池、广度优先搜索等场景。

## 1.3 栈与队列的比较
栈与队列都是常用的线性数据结构，但在特点和应用场景上有所区别。栈适合于需要快速访问最近加入的元素的场景，而队列适合于需要保持元素顺序且能够按顺序处理的场景。根据具体需求选择合适的数据结构能够提高程序效率。

# 2. 栈与队列的实现

栈（Stack）和队列（Queue）是两种常用的数据结构，它们在编程中有着广泛的应用。在这一章节中，我们将详细介绍栈与队列的实现方式。

### 2.1 栈的实现方式

栈是一种先进后出（LIFO，Last In First Out）的数据结构，最常见的实现方式是使用数组或链表。下面是使用Python实现栈的简单示例代码：

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

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

    def pop(self):
        if not self.is_empty():
            return self.items.pop()

    def peek(self):
        if not self.is_empty():
            return self.items[-1]

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

    def size(self):
        return len(self.items)

# 测试栈的基本操作
stack = Stack()
print(stack.is_empty())  # True
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.peek())  # 3
print(stack.pop())   # 3
print(stack.size())  # 2

上述代码定义了一个Stack类，实现了栈的基本操作：push（压栈）、pop（出栈）、peek（查看栈顶元素）、is_empty（判断是否为空）、size（获取栈的大小）。

### 2.2 队列的实现方式

队列是一种先进先出（FIFO，First In First Out）的数据结构，同样可以使用数组或链表来实现。下面是使用Java实现队列的简单示例代码：

import java.util.LinkedList;

class Queue {
    private LinkedList<Integer> queue;

    public Queue() {
        queue = new LinkedList<>();
    }

    public void enqueue(int item) {
        queue.addLast(item);
    }

    public int dequeue() {
        if (!isEmpty()) {
            return queue.removeFirst();
        }
        return -1;
    }

    public int peek() {
        if (!isEmpty()) {
            return queue.getFirst();
        }
        return -1;
    }

    public boolean isEmpty() {
        return queue.isEmpty();
    }

    public int size() {
        return queue.size();
    }

    public static void main(String[] args) {
        Queue queue = new Queue();
        System.out.println(queue.isEmpty());  // true
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        System.out.println(queue.peek());     // 1
        System.out.println(queue.dequeue());  // 1
        System.out.println(queue.size());     // 2
    }
}

上面的Java代码定义了一个Queue类，实现了队列的基本操作：enqueue（入队）、dequeue（出队）、peek（查看队首元素）、isEmpty（判断是否为空）、size（获取队列大小）。

栈与队列的实现方式多种多样，可以根据实际需求选择适合的数据结构实现方式。

# 3. 栈与队列的操作

栈（Stack）和队列（Queue）是常见的数据结构，它们有着各自独特的操作和应用。本章将深入探讨栈与队列的操作及其应用。

#### 3.1 栈的操作与应用

栈是一种后进先出（LIFO）的数据结构，只允许在栈顶进行插入和删除操作。常见的栈操作包括：

1. **Push操作**：向栈顶插入一个元素。
2. **Pop操作**：从栈顶删除一个元素。
3. **Peek操作**：查看栈顶元素而不移除。

下面是栈的Python实现示例：

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

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

    def pop(self):
        if not self.is_empty():
            return self.items.pop()

    def peek(self):
        if not self.is_empty():
            return self.items[-1]

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

    def size(self):
        return len(self.items)

# 使用栈
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)

print("栈顶元素：", stack.peek())  # 输出：3
print