### 数据结构：堆栈与队列的基本操作
#### 一、引言
在计算机科学领域，数据结构是组织和管理数据的重要方式之一。其中，堆栈（Stack）和队列（Queue）作为两种特殊的线性数据结构，在各种应用场景中扮演着重要的角色。本文将详细介绍这两种数据结构的基本概念、特性以及在不同存储结构下的基本操作。
#### 二、堆栈（Stack）
##### 1. 定义
堆栈是一种只允许在一端进行插入和删除操作的线性表，这一端被称为“栈顶”，而另一端则被称为“栈底”。当栈中没有任何元素时，称其为空栈。
##### 2. 特性
- **后进先出（LIFO）**：最后进入栈中的元素最先被移除。
- **栈顶指针**：用于标识栈顶元素的位置，随着元素的出入栈而动态变化。
##### 3. 基本操作
- **初始化栈**：创建一个空栈。
- **判断栈是否为空**：检查栈是否为空。
- **入栈**：将元素添加到栈顶。
- **出栈**：移除栈顶元素。
- **获取栈顶元素**：查看栈顶元素但不移除。
- **显示栈中所有元素**：遍历栈并输出所有元素。
##### 4. 存储结构
- **顺序存储**：使用数组来存储栈中的元素，通常会定义一个变量记录栈顶位置。
- **链式存储**：使用链表来存储栈中的元素，链表的头部为栈顶。
#### 三、队列（Queue）
##### 1. 定义
队列是一种允许在一端进行插入而在另一端进行删除操作的线性表。允许插入的一端称为“队尾”，允许删除的一端称为“队头”。
##### 2. 特性
- **先进先出（FIFO）**：最早进入队列的元素最先被移除。
##### 3. 基本操作
- **初始化队列**：创建一个空队列。
- **判断队列是否为空**：检查队列是否为空。
- **入队**：将元素添加到队尾。
- **出队**：移除队头元素。
- **获取队头元素**：查看队头元素但不移除。
- **显示队中所有元素**：遍历队列并输出所有元素。
##### 4. 存储结构
- **顺序存储**：使用数组来存储队列中的元素，通过两个指针（队头指针和队尾指针）来标记队列的起始和结束位置。为了克服顺序队列可能出现的“假溢出”现象，可以采用循环队列的方式。
- **链式存储**：使用链表来存储队列中的元素，通常会在链表头部添加一个头节点，并设置两个指针分别指向头结点和尾结点。
#### 四、示例代码分析——链式队列
下面是一段关于链式队列的基本操作的C语言示例代码：
```c
#include<stdio.h>
#include<stdlib.h>
#define NULL 0
// 定义队列元素类型
typedef int QElemType;
// 定义队列结点结构体
typedef struct QNode {
QElemType data;
struct QNode* next;
} QNode, *QueuePtr;
// 定义链式队列结构体
typedef struct {
QueuePtr front;
QueuePtr rear;
} LinkQueue;
// 创建链式队列
void CreateQueue(LinkQueue* Q) {
// ...省略部分代码...
}
// 打印队列内容
void PrintfQueue(LinkQueue* Q) {
QueuePtr p;
for (p = Q->front->next; p != NULL; p = p->next) {
printf("%d", p->data);
}
}
// 入队操作
void EnQueue(LinkQueue* Q, QElemType x) {
QueuePtr p;
p = (QueuePtr)malloc(sizeof(QNode));
if (!p) printf("创建失败");
else {
p->data = x;
p->next = NULL;
Q->rear->next = p;
Q->rear = p;
}
}
// 出队操作
void DeQueue(LinkQueue* Q, QElemType* f) {
// ...省略部分代码...
}
```
#### 五、总结
通过对堆栈和队列的基本概念、特性和基本操作的介绍，我们了解了这两种数据结构在实际应用中的重要性。无论是顺序存储还是链式存储，堆栈和队列都提供了灵活且高效的方式来管理数据。通过理解这些基本概念和操作，开发者能够更好地利用这些数据结构来解决问题。
