栈和队列的知识点总结
栈和队列是数据结构中的两个基本概念，在算法和编程中经常被使用到。本文将从定义、分类、实现和应用等多个角度对栈和队列进行分析和总结，帮助读者加深对这两个数据结构的理解。
一、定义
1.栈：栈是一种具有后进先出(LIFO)特点的线性数据结构，具体来说，最先插入的元素最后一个被取出，而最后插入的元素最先被取出。
2.队列：队列是一种具有先进先出(FIFO)特点的线性数据结构，具体来说，最先插入的元素最先被取出，而最后插入的元素最后被取出。
二、分类
1.栈
- 静态栈：栈的容量是固定的，一旦栈满了，就不能再添加任何元素；
- 动态栈：栈的容量是可以动态调整的，可以在需要时改变栈的大小；
- 数组栈：使用数组来实现栈；
- 链表栈：使用链表来实现栈。
2.队列
- 单向队列：队列只能从一端插入元素，从另一端取出元素；
- 双向队列：队列可以从两端插入元素，从两端取出元素；
- 循环队列：队列尾部指针指向队列最后一个元素的下一个位置，头部指针指向队列第一个元素。
三、实现
1.栈
- 数组栈实现：
```cpp
#define MAX_SIZE 100 // 定义栈的最大容量
template
class Stack{
private:
T data[MAX_SIZE]; // 栈的数据存储
int top_index; // 栈顶的下标
public:
Stack() : top_index(-1){} // 构造函数
bool empty() { return top_index == -1; } // 判断栈是否为空
bool full() { return top_index == (MAX_SIZE - 1); } // 判断栈是否已经满了
void push(T x) { // 压入栈顶
if(full()) return;
data[++top_index] = x;
}
void pop() { // 弹出栈顶元素
if(empty()) return;
--top_index;
}
T top() { // 返回栈顶元素
if(empty()) return;
return data[top_index];
}
};
```
- 链表栈实现：
```cpp
template
class StackNode{
public:
T value; // 栈节点存储的值
StackNode *next; // 下一个节点的指针
StackNode(T x) : value(x), next(nullptr){} // 构造函数
};
template
class Stack{
private:
StackNode
public:
Stack() : top_node(nullptr){} // 构造函数
bool empty() { return top_node == nullptr; } // 判断栈是否为空
void push(T x) { // 压入栈顶
StackNode
new_node->next = top_node;
top_node = new_node;
}
void pop() { // 弹出栈顶元素
if(empty()) return;
StackNode
top_node = top_node->next;
delete(temp);
}
T top() { // 返回栈顶元素
if(empty()) return;
return top_node->value;
}
};
```
2.队列
- 链表队列实现：
```cpp
template
class QueueNode{
public:
T value; // 队列节点存储的值
QueueNode *next; // 下一个节点的指针
QueueNode(T x) : value(x), next(nullptr){} // 构造函数
};
template
class Queue{
private:
QueueNode
QueueNode
public:
Queue() : front_node(nullptr), rear_node(nullptr){} // 构造函数
bool empty() { return front_node == nullptr; } // 判断队列是否为空
void enqueue(T x) { // 入队
QueueNode
if(empty()){
front_node = new_node;
rear_node = new_node;
}
else{
rear_node->next = new_node;
rear_node = new_node;
}
}
void dequeue() { // 出队
if(empty()) return;
QueueNode
front_node = front_node->next;
delete(temp);
}
T front() { // 返回队头元素
if(empty()) return;
return front_node->value;
}
T rear() { // 返回队尾元素
if(empty()) return;
return rear_node->value;
}
};
```
- 循环队列实现：
```cpp
#define MAX_SIZE 100 // 定义队列的最大容量
template
class Queue{
private:
T data[MAX_SIZE]; // 队列数据存储
int front_index; // 队头下标
int rear_index; // 队尾下标
public:
Queue() : front_index(-1), rear_index(-1){} // 构造函数
bool empty() { return front_index == -1; } // 判断队列是否为空
bool full() { return (rear_index + 1) % MAX_SIZE == front_index; } // 判断队列是否已满
void enqueue(T x) { // 入队
if(full()) return;
if(empty()) front_index = 0;
rear_index = (rear_index + 1) % MAX_SIZE;
data[rear_index] = x;
}
void dequeue() { // 出队
if(empty()) return;
if(front_index == rear_index){
front_index = -1;
rear_index = -1;
}
else{
front_index = (front_index + 1) % MAX_SIZE;
}
}
T front() { // 返回队头元素
if(empty()) return;
return data[front_index];
}
T rear() { // 返回队尾元素
if(empty()) return;
return data[rear_index];
}
};
```
四、应用
1.栈的应用：
- 表达式求值；
- 逆波兰表达式转换；
- 回文判断；
- DFS(深度优先搜索)算法实现；
- 括号匹配问题。
2.队列的应用：
- 广度优先搜索算法实现；
- 缓存调度；
- 线程池调度；
- 最近最少使用页面置换算法实现(Least Recently Used, LRU)。
综上所述，本文从定义、分类、实现和应用等多个角度对栈和队列进行了分析和总结。可以看出，栈和队列作为数据结构的基本概念，在算法和编程中应用广泛，熟练掌握它们的使用方法，可以大大提高算法和编程的效率。
