数据结构 | 栈和队列

栈和队列

在计算机科学中，栈和队列是两种基本且重要的数据结构，它们在处理数据存储和访问顺序方面有着独特的规则和应用。本文将详细介绍栈和队列的概念、结构、实现方式，并通过几个经典的算法题目来展示它们的实际应用。

1. 栈：后进先出（LIFO）的数据结构

1.1 概念与结构

栈是一种特殊的线性表，它只允许在一端（称为栈顶）进行插入和删除操作。另一端称为栈底。栈中的数据元素遵循后进先出（LIFO）的原则，即最后进入的数据项最先被移除。

• 压栈（进栈/入栈）：数据插入操作在栈顶进行。
• 出栈：数据删除操作也在栈顶进行。

1.2 栈的实现

栈可以使用数组或链表来实现，但数组由于在尾部插入数据的效率较高，通常更受青睐。以下是栈的基本操作的C语言实现：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>typedef int STDataType;typedef struct Stack {STDataType* array;int top;int capacity;
} ST;// 初始化栈
void STInit(ST* ps, int capacity) {ps->array = (STDataType*)malloc(sizeof(STDataType) * capacity);ps->top = -1;ps->capacity = capacity;
}// 销毁栈
void STDestroy(ST* ps) {free(ps->array);ps->array = NULL;ps->top = -1;ps->capacity = 0;
}// 入栈
void STPush(ST* ps, STDataType x) {if (ps->top >= ps->capacity - 1) {// 栈满，扩容或者报错return;}ps->array[++ps->top] = x;
}// 出栈
void STPop(ST* ps) {if (ps->top < 0) {// 栈空，报错return;}ps->top--;
}// 取栈顶元素
STDataType STTop(ST* ps) {if (ps->top < 0) {// 栈空，报错return -1;}return ps->array[ps->top];
}// 获取栈中有效元素个数
int STSize(ST* ps) {return ps->top + 1;
}// 栈是否为空
bool STEmpty(ST* ps) {return ps->top < 0;
}

2. 队列：先进先出（FIFO）的数据结构

2.1 概念与结构

队列是一种只允许在一端（称为队尾）进行插入操作，在另一端（称为队头）进行删除操作的线性表。队列遵循先进先出（FIFO）的原则。

• 入队列：数据插入操作在队尾进行。
• 出队列：数据删除操作在队头进行。

2.2 队列的实现

队列通常使用链表实现，因为如果使用数组，出队操作（尤其是在数组头部）的效率会较低。以下是队列的基本操作的C语言实现：

typedef int QDataType;typedef struct QueueNode {QDataType val;struct QueueNode* next;
} QNode;typedef struct Queue {QNode* front;QNode* rear;int size;
} Queue;// 初始化队列
void QueueInit(Queue* pq) {pq->front = pq->rear = (QNode*)malloc(sizeof(QNode));if (pq->rear) {pq->rear->next = NULL;}pq->size = 0;
}// 销毁队列
void QueueDestroy(Queue* pq) {QNode* current = pq->front;QNode* next;while (current != NULL) {next = current->next;free(current);current = next;}pq->front = pq->rear = NULL;pq->size = 0;
}// 入队列，队尾添加元素
void QueuePush(Queue* pq, QDataType x) {QNode* newNode = (QNode*)malloc(sizeof(QNode));if (newNode == NULL) {return; // 内存分配失败}newNode->val = x;newNode->next = NULL;if (pq->rear) {pq->rear->next = newNode;}pq->rear = newNode;if (pq->front->next == NULL) { // 队列原来为空pq->front->next = newNode;}pq->size++;
}// 出队列，队头删除元素
void QueuePop(Queue* pq) {if (QueueEmpty(pq)) {return; // 队列为空，无法出队}QNode* temp = pq->front->next;QNode* prev = pq->front;if (temp == pq->rear) { // 只有一个元素pq->front = pq->rear = NULL;} else {pq->front->next = temp->next;if (temp == pq->rear) {pq->rear = prev;}}free(temp);pq->size--;
}// 取队头数据
QDataType QueueFront(Queue* pq) {if (QueueEmpty(pq)) {return -1; // 队列为空}return pq->front->next->val;
}// 取队尾数据
QDataType QueueBack(Queue* pq) {if (QueueEmpty(pq)) {return -1; // 队列为空}return pq->rear->val;
}// 队列判空
bool QueueEmpty(Queue* pq) {return (pq->size == 0);
}// 队列有效元素个数
int QueueSize(Queue* pq) {return pq->size;
}

3. 栈和队列算法题

3.1 有效的括号

题目描述：给定一个只包括 '(', ')', '{', '}', '[', ']' 的字符串，判断字符串是否有效。

思路：使用栈来解决这个问题。遍历字符串中的每个字符，如果是左括号，就压入栈中。如果是右括号，则检查栈顶是否有对应的左括号，如果有，则弹出栈顶元素并继续遍历；如果没有，说明字符串无效。最后，如果栈为空，则字符串有效；否则，无效。

力扣题目链接：有效的括号

3.2 用队列实现栈

题目描述：使用队列实现栈的下列操作：push、pop、top 和 empty。

思路：使用两个队列来模拟栈的行为。对于入栈操作，直接添加到队列中；对于出栈操作，将除了最新的元素外的所有元素重新入队一次，最新的元素即为要出栈的元素。这样可以保证队列的 FIFO 特性来模拟栈的 LIFO 特性。

力扣题目链接：用队列实现栈

3.3 用栈实现队列

题目描述：使用栈实现队列的下列操作：push、pop、peek 和 empty。

思路：使用两个栈来实现队列的功能。入队操作直接压入一个栈中，出队操作则涉及到两个栈的配合：将一个栈中的所有元素依次弹出并压入另一个栈中，这样第一个弹出的元素就是队列的前端元素，可以作为出队操作的返回值。

力扣题目链接：用栈实现队列

3.4 设计循环队列

循环队列是一种特殊的队列，它可以高效地利用数组空间，避免队列满时的额外处理。循环队列可以通过Q.rear = Q.front来区分队空和队满的情况。

结论

栈和队列不仅是数据结构的基础，也是许多算法和应用的核心。理解它们的原理和实现对于任何软件开发者来说都是至关重要的。通过实际的编程练习和算法题目，我们可以进一步加深对这些概念的理解。