跳到主要内容 数据结构：栈与队列详解 | 极客日志
C 算法
数据结构：栈与队列详解 本文详细讲解了数据结构中的栈和队列。栈遵循后进先出原则，通常用数组实现；队列遵循先进先出原则，通常用链表实现。文章提供了基于 C 语言的代码实现，包括初始化、销毁、入栈/队、出栈/队等操作。此外，还通过四个经典算法题（有效的括号、用队列实现栈、用栈实现队列、设计循环队列）展示了实际应用，重点分析了循环队列的空满判断及空间优化方案。
数据结构：栈与队列详解
概念与结构
栈
栈：一种特殊的线性表 ，只允许在固定的一端 进行插入和删除 元素操作。数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的元素遵守后进先出 (或先进后出) 的原则。
压栈 (进栈/入栈) ：插入数据在栈顶。
出栈 ：在栈顶出数据。
栈的实现可由数组或链表实现，那么哪种是优解呢？
底层用数组：在进栈时只需要在栈顶 (尾部) 插入数据，不用进行遍历；
底层用链表：在进栈时链表遍历到尾结点再进行插入数据，需要 O(n) 的时间复杂度，会有一定的消耗。
因此数组的结构实现更优一些。
队列
概念：只允许在一端插入数据 ，在另一端删除数据的特殊线性表，队列具有先进先出 (后进后出) 的原则。
入队列 ：在队尾插入数据。
出队列 ：在队头删除数据。
同样，队列底层也可由数组或链表实现，哪种是优解呢？
底层用数组：删除数据时需要将后面的数据往前挪，有一定的消耗。
底层用链表：出队列时只需要让指向第一个有效结点的指针指向第二个有效结点，不需要遍历；
因此链表的结构实现更优一些。
代码实现
栈
栈的底层是数组，和前面在实现 [顺序表] 的底层结构是一样的。
typedef int STDataType;
typedef struct Stack {int top;
int capacity;
} ST;
微信扫一扫，关注极客日志 微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具 加密/解密文本 使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器 将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
Markdown 转 HTML 将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
HTML 转 Markdown 将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
JSON 压缩 通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
由于栈的初始化、销毁、入栈 (顺序表尾插)、出栈 (顺序表尾删) 功能 与顺序表功能实现是一样的，就不过多赘述。
void STInit (ST* st) {
assert(st);
st->arr = NULL ;
st->top = st->capacity = 0 ;
}
void STDestroy (ST* st) {
assert(st);
if (st->arr) {
free (st->arr);
}
st->arr = NULL ;
st->capacity = st->top = 0 ;
}
void STPush (ST* st, STDataType x) {
assert(st);
if (st->capacity == st->top) {
int NewCapacity = st->capacity == 0 ? 4 : 2 * st->capacity;
STDataType* tmp = (STDataType*)realloc (st->arr, NewCapacity * sizeof (STDataType));
if (tmp == NULL ) {
perror("realloc fail!" );
exit (1 );
}
st->arr = tmp;
st->capacity = NewCapacity;
}
st->arr[st->top] = x;
st->top++;
}
void STPop (ST* st) {
assert(st);
assert(!STEmpty(st));
st->top--;
}
栈是否为空，取栈顶数据、栈的有效个数 栈是否为空，即栈里面是否存在数据，即 top 是否为 0(为 0 则返回真)。
bool STEmpty (ST* st) {
assert(st);
return st->top == 0 ;
}
取栈顶数据首先得保证栈不为空，其次取 top-1 的数据即可，栈的有效个数即 top。
STDataType STTop (ST* st) {
assert(!STEmpty(st));
return st->arr[st->top - 1 ];
}
int STSize (ST* st) {
assert(st);
return st->top;
}
队列 队列的底层是链表，和前面在实现 [单链表] 的底层结构是一样的。
但队列额外定义了指向第一个有效结点的 phead 指针、指向最后一个有效结点的 ptail 指针，目的是减少入队列的消耗（不用遍历链表）。
这里多定义的 size 变量 是为了记录队列的有效个数 。
typedef int QDataType;
typedef struct QueueNode {struct QueueNode * next ;typedef struct Queue {int size;
} Queue;
入队列 需要往队尾插入数据，必然涉及申请新节点 --> 在 [单链表] 中实现过。
链表为空，phead 和 ptail 指向申请的新结点； 链表不为空，ptail 指向新结点并成为新结点，并让 size++。
void QueuePush (Queue* pq, QDataType x) {
assert(pq);
QueueNode* newnode = (QueueNode*)malloc (sizeof (QueueNode));
if (newnode == NULL ) {
perror("malloc: fail" );
exit (1 );
}
newnode->data = x;
newnode->next = NULL ;
if (pq->phead == NULL ) {
pq->phead = pq->ptail = newnode;
} else {
pq->ptail->next = newnode;
pq->ptail = pq->ptail->next;
}
pq->size++;
}
出队列
当只存在一个结点时，释放后 phead 和 ptail 指向为 NULL； 释放尾结点，让 ptail 指向上一个结点。
void QueuePop (Queue* pq) {
assert(pq);
assert(!QueueEmpty(pq));
if (pq->phead == pq->ptail) {
free (pq->phead);
pq->phead = pq->ptail = NULL ;
} else {
QueueNode* next = pq->phead->next;
free (pq->phead);
pq->phead = next;
}
pq->size--;
}
队列判空，取队头、队尾数据，队列的有效个数
bool QueueEmpty (Queue* pq) {
assert(pq);
return pq->phead == NULL ;
}
QDataType QueueFront (Queue* pq) {
assert(pq);
assert(!QueueEmpty(pq));
return pq->phead->data;
}
QDataType QueueBack (Queue* pq) {
assert(pq);
assert(!QueueEmpty(pq));
return pq->ptail->data;
}
int QueueSize (Queue* pq) {
assert(pq);
return pq->size;
}
算法题解 掌握了栈和队列这两种数据结构后，重点在于算法题上的解答，下面通过四种题型领略栈和队列的魅力。
有效的括号
根据题目需求判断字符串是否有效，但还存在一些特殊情况如上图所示。那这题思路该从哪里入手呢？用栈的方法实现。
将 s 从头开始遍历直到结束，若遍历过程遇到 '(' '{' '[' 则入栈 st；
若遇到 ')' '}' ']' 时则取栈顶比较 (前提是栈不为空);
遍历结束后，需判断栈是否为空，因为若是有效的字符串则栈应为空 (如上图特殊处理 1)。
bool isValid (char * s) {
ST st;
STInit(&st);
char * pi = s;
while (*pi != '\0' ) {
if (*pi == '(' || *pi == '{' || *pi == '[' ) {
STPush(&st, *pi);
} else {
if (STEmpty(&st)) {
return false ;
}
char top = STTop(&st);
if ((top == '(' && *pi != ')' ) || (top == '{' && *pi != '}' ) || (top == '[' && *pi != ']' )) {
return false ;
}
STPop(&st);
}
pi++;
}
bool ret = STEmpty(&st) ? true : false ;
STDestroy(&st);
return ret;
}
用队列实现栈
typedef struct {myStackCreate () {
MyStack* ret = (MyStack*)malloc (sizeof (MyStack));
QueueInit(&ret->q1);
QueueInit(&ret->q2);
return ret;
}
void myStackPush (MyStack* obj, int x) {
if (!QueueEmpty(&obj->q1)) {
QueuePush(&obj->q1, x);
} else {
QueuePush(&obj->q2, x);
}
}
int myStackPop (MyStack* obj) {
Queue* emp = &obj->q1;
Queue* Unemp = &obj->q2;
if (QueueEmpty(&obj->q2)) {
emp = &obj->q2;
Unemp = &obj->q1;
}
while (QueueSize(Unemp) > 1 ) {
QueuePush(emp, QueueFront(Unemp));
QueuePop(Unemp);
}
int top = QueueFront(Unemp);
QueuePop(Unemp);
return top;
}
int myStackTop (MyStack* obj) {
if (!QueueEmpty(&obj->q1)) {
return QueueBack(&obj->q1);
} else {
return QueueBack(&obj->q2);
}
}
bool myStackEmpty (MyStack* obj) {
return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
void myStackFree (MyStack* obj) {
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free (obj);
obj = NULL ;
}
用栈实现队列
将 STPush 栈里的数据全部导入到 STPop 栈里，并删除 STPop 栈顶元素。
typedef struct {myQueueCreate () {
MyQueue* obj = (MyQueue*)malloc (sizeof (MyQueue));
STInit(&obj->pushST);
STInit(&obj->popST);
return obj;
}
void myQueuePush (MyQueue* obj, int x) {
STPush(&obj->pushST, x);
}
int myQueuePop (MyQueue* obj) {
if (STEmpty(&obj->popST)) {
while (!STEmpty(&obj->pushST)) {
STPush(&obj->popST, STTop(&obj->pushST));
STPop(&obj->pushST);
}
}
int top = STTop(&obj->popST);
STPop(&obj->popST);
return top;
}
int myQueuePeek (MyQueue* obj) {
if (STEmpty(&obj->popST)) {
while (!STEmpty(&obj->pushST)) {
STPush(&obj->popST, STTop(&obj->pushST));
STPop(&obj->pushST);
}
}
int top = STTop(&obj->popST);
return top;
}
bool myQueueEmpty (MyQueue* obj) {
return STEmpty(&obj->pushST) && STEmpty(&obj->popST);
}
void myQueueFree (MyQueue* obj) {
STDestroy(&obj->pushST);
STDestroy(&obj->popST);
free (obj);
obj = NULL ;
}
复用 由于出队列和取队尾数据的代码相似度极高，因此我们可以用复用的方法使代码更简洁，增强代码可维护性。
设计循环队列
若底层用链表的结构来实现，则会出现如下情况 1 和 2 出现矛盾，此时又该怎样判断循环队列是否为空 呢？
因此，底层用链表的结构来实现很难行得通。
数组结构实现循环队列 如果按题目需要多少空间就开多少空间，此时会循环队列空和满的情况下，front 和 rear 的下标都指向同一下标，那该如何判断循环队列是空还是满呢？
构造、销毁循环队列 typedef struct {int * arr;
int front;
int rear;
int capacity;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate (int k) {
MyCircularQueue* pq = (MyCircularQueue*)malloc (sizeof (MyCircularQueue));
if (pq == NULL ) {
exit (1 );
}
if (pq->arr == NULL ) {
exit (1 );
}
pq->arr = (int *)malloc (sizeof (int ) * (k + 1 ));
pq->front = pq->rear = 0 ;
pq->capacity = k;
return pq;
}
判断空和满 bool myCircularQueueIsEmpty (MyCircularQueue* obj) {
return obj->front == obj->rear;
}
bool myCircularQueueIsFull (MyCircularQueue* obj) {
return (obj->rear + 1 ) % (obj->capacity + 1 ) == obj->front;
}
入、出队列 入队列和出队列的时候会出现特例情况，即front 和 rear 是否会越界。
bool myCircularQueueEnQueue (MyCircularQueue* obj, int value) {
if (myCircularQueueIsFull(obj)) {
return false ;
}
obj->arr[obj->rear++] = value;
obj->rear %= obj->capacity + 1 ;
return true ;
}
bool myCircularQueueDeQueue (MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj)) {
return false ;
}
obj->front++;
obj->front %= obj->capacity + 1 ;
return true ;
}
取队头、队尾元素 取队尾元素时，一般返回 rear-1 下标位置的元素即可。但此题是一个循环队列，因此存在特殊情况需要处理 。
int myCircularQueueRear (MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj)) {
return -1 ;
}
return obj->arr[obj->rear - 1 ];
}
特例情况：若 rear–则为 -1，取不到队尾元素。
int myCircularQueueFront (MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj)) {
return -1 ;
}
return obj->arr[obj->front];
}
int myCircularQueueRear (MyCircularQueue* obj) {
if (myCircularQueueIsEmpty(obj)) {
return -1 ;
}
int prev = obj->rear - 1 ;
if (obj->rear == 0 ) {
prev = obj->capacity;
}
return obj->arr[prev];
}
