栈和队列的知识点总结

栈和队列是数据结构中的两个基本概念，在算法和编程中经常被使用到。本文将从定义、分类、实现和应用等多个角度对栈和队列进行分析和总结，帮助读者加深对这两个数据结构的理解。

一、定义

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 *top_node; // 栈顶节点指针

public:

Stack() : top_node(nullptr){} // 构造函数

bool empty() { return top_node == nullptr; } // 判断栈是否为空

void push(T x) { // 压入栈顶

StackNode *new_node = new StackNode (x);

new_node->next = top_node;

top_node = new_node;

}

void pop() { // 弹出栈顶元素

if(empty()) return;

StackNode *temp = top_node;

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 *front_node; // 队列头节点指针

QueueNode *rear_node; // 队列尾节点指针

public:

Queue() : front_node(nullptr), rear_node(nullptr){} // 构造函数

bool empty() { return front_node == nullptr; } // 判断队列是否为空

void enqueue(T x) { // 入队

QueueNode *new_node = new QueueNode (x);

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 *temp = front_node;

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)。

综上所述，本文从定义、分类、实现和应用等多个角度对栈和队列进行了分析和总结。可以看出，栈和队列作为数据结构的基本概念，在算法和编程中应用广泛，熟练掌握它们的使用方法，可以大大提高算法和编程的效率。