栈与队列的实现
使用数组或链表实现栈和队列，并讨论它们的应用场景和性能特点。
栈（Stack）
实现
数组实现：
栈顶指针（top）：用于指向栈顶元素的位置。
初始化时，栈顶指针通常设置为-1（如果栈为空）或0（如果栈可以包含空元素）。
入栈（push）：在栈顶添加元素，栈顶指针加1。
出栈（pop）：移除栈顶元素，栈顶指针减1。
访问栈顶元素（peek/top）：返回栈顶元素的值，但不移除它。
链表实现：
使用链表的头部作为栈顶。
入栈：在链表头部添加新节点。
出栈：移除链表头部节点。
访问栈顶元素：访问链表头部节点的值。
应用场景
后缀表达式求值
深度优先搜索（DFS）
浏览器的前进后退功能
撤销操作（如文本编辑器的撤销）
性能特点
数组实现：
时间复杂度：入栈、出栈、访问栈顶元素均为O(1)。
空间复杂度：O(n)，n为栈中元素数量。
缺点：栈大小受限，可能需要动态扩容。
链表实现：
时间复杂度：入栈、出栈、访问栈顶元素均为O(1)（不考虑链表节点分配的时间）。
空间复杂度：O(n)，n为栈中元素数量。
优点：动态大小，不需要预先分配空间。
队列（Queue）
实现
数组实现：
队首指针（front）：指向队列第一个元素。
队尾指针（rear）：指向队列最后一个元素的下一个位置（或最后一个元素，取决于实现方式）。
入队（enqueue）：在队尾添加元素，队尾指针加1。
出队（dequeue）：移除队首元素，队首指针加1（可能需要考虑队列头部的元素移动到尾部以维持连续性，即循环队列）。
链表实现：
使用链表的头部作为队首，尾部作为队尾。
入队：在链表尾部添加新节点。
出队：移除链表头部节点。
应用场景
广度优先搜索（BFS）
操作系统中的任务调度
打印机任务队列
消息队列（如RabbitMQ、Kafka等）
性能特点
数组实现：
时间复杂度：入队、出队平均情况下为O(1)，但在最坏情况下（如频繁入队出队导致大量元素移动）可能退化到O(n)。
空间复杂度：O(n)，n为队列中元素数量。
优点：随机访问队列中元素速度快。
缺点：可能需要动态扩容，且队列大小受限。
链表实现：
时间复杂度：入队、出队均为O(1)（不考虑链表节点分配的时间）。
空间复杂度：O(n)，n为队列中元素数量。
优点：动态大小，不需要预先分配空间。
缺点：无法像数组那样快速随机访问队列中的元素。
总结
栈和队列是两种非常基础且重要的数据结构，它们在算法设计和系统设计中有着广泛的应用。选择数组还是链表实现取决于具体的应用场景和对性能的需求。数组实现通常具有较好的缓存局部性，但大小受限；链表实现则更加灵活，但随机访问性能较差。
栈与队列的实现（扩展）
在数据结构的设计与实现中，数组和链表作为基础但极其重要的元素，广泛应用于各种算法与系统设计中。本文将从栈（Stack）与队列（Queue）的实现出发，深入探讨它们在不同场景下的应用及性能特点，并通过具体的代码示例进行说明。
栈（Stack）的实现
数组实现
数组实现的栈通过维护一个栈顶指针（top）来追踪栈顶元素的位置。初始化时，栈顶指针可以设置为-1（表示空栈）或根据具体情况而定。以下是基于数组的栈的基本操作代码示例（C++）：
#include <iostream> |
#include <vector> |
|
template<typename T> |
class StackArray { |
private: |
std::vector<T> data; |
int top = -1; |
|
public: |
void push(const T& value) { |
data.push_back(value); |
top++; |
} |
|
T pop() { |
if (isEmpty()) throw std::out_of_range("pop from empty stack"); |
T value = data[top]; |
data.pop_back(); |
top--; |
return value; |
} |
|
T peek() const { |
if (isEmpty()) throw std::out_of_range("peek from empty stack"); |
return data[top]; |
} |
|
bool isEmpty() const { |
return top == -1; |
} |
}; |
|
// 使用示例 |
StackArray<int> stack; |
stack.push(1); |
std::cout << stack.pop() << std::endl; // 输出: 1 |
链表实现
链表实现的栈通常将链表的头部作为栈顶。这允许我们在O(1)时间复杂度内完成入栈（push）和出栈（pop）操作。以下是基于链表的栈的实现代码（C++）：
#include <iostream> |
|
template<typename T> |
class StackNode { |
public: |
T value; |
StackNode* next; |
|
StackNode(T val) : value(val), next(nullptr) {} |
}; |
|
template<typename T> |
class StackLinkedList { |
private: |
StackNode<T>* top = nullptr; |
|
public: |
void push(const T& value) { |
StackNode<T>* newNode = new StackNode<T>(value); |
newNode->next = top; |
top = newNode; |
} |
|
T pop() { |
if (!top) throw std::out_of_range("pop from empty stack"); |
T value = top->value; |
StackNode<T>* temp = top; |
top = top->next; |
delete temp; |
return value; |
} |
|
T peek() const { |
if (!top) throw std::out_of_range("peek from empty stack"); |
return top->value; |
} |
|
bool isEmpty() const { |
return top == nullptr; |
} |
}; |
|
// 使用示例 |
StackLinkedList<int> stack; |
stack.push(1); |
std::cout << stack.pop() << std::endl; // 输出: 1 |
队列（Queue）的实现
数组实现
数组实现的队列需要维护队首指针（front）和队尾指针（rear）。队列的入队（enqueue）操作在队尾添加元素，出队（dequeue）操作移除队首元素。以下是基于数组的队列实现代码（C++）：
// 省略部分代码，因篇幅限制，仅展示关键思路 |
// 注意：数组实现队列时，需处理队列满和队列空的情况，以及可能的动态扩容 |
链表实现
链表实现的队列将链表的头部作为队首，尾部作为队尾。这种实现方式允许在O(1)时间复杂度内完成入队和出队操作。以下是基于链表的队列实现代码（C++）：
#include <iostream> |
|
template<typename T> |
class QueueNode { |
public: |
T value; |
QueueNode* next; |
|
QueueNode(T val) : value(val), next(nullptr) {} |
}; |
|
template<typename T> |
class QueueLinkedList { |
private: |
QueueNode<T>* front = nullptr; |
QueueNode<T>* rear = nullptr; |
|
public: |
void enqueue(const T& value) { |
QueueNode<T>* newNode = new QueueNode<T>(value); |
if |
