手拉手的链表玩过了，追逐游戏也玩过了，今天来认识两位讲规矩的朋友：栈和队列。它们都是特殊的线性表，只是插入和删除被限定了位置——一个像羽毛球筒，一个像排队买面包。
栈：羽毛球筒的小脾气
栈只允许在固定的一端插入和删除，这一端叫栈顶，另一端叫栈底。数据遵守 LIFO（Last In First Out，后进先出）：像羽毛球筒，后放进去的球会先被取出来。插入叫压栈，删除叫出栈，都发生在栈顶。
动态栈的样子
typedef int STDataType;
typedef struct Stack
{
STDataType* a; // 动态数组
int top; // 栈顶位置
int capacity; // 容量
}ST;这里有个容易犯迷糊的地方：top 到底指向哪？
top 指向栈顶元素 → 初始化为 -1，判满用 top == capacity - 1；
top 指向栈顶的下一个位置 → 初始化为 0，判满用 top == capacity。
下面按前一种写。入栈前照例检查空间，不够就 2 倍扩容——和顺序表的增容小心机一模一样：
void StackPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity - 1) // 栈满
{
int newCapacity = (ps->capacity == 0) ? 4 : ps->capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->a,
sizeof(STDataType) * ps->capacity * 2);
if (tmp == NULL)
{
perror("realloc fail");
exit(1);
}
ps->a = tmp;
ps->capacity = newCapacity;
}
ps->top++;
ps->a[ps->top] = x;
}
void StackPop(ST* ps) // 出栈
{
assert(ps);
assert(ps->top != -1); // 空栈不能弹
ps->top--;
}配套的还有 StackTop（看一眼栈顶）、StackEmpty（top == -1 就为空）、StackSize（top + 1 个元素）。有个好玩的细节：入栈 1、2、3 再依次出栈，不一定是 3、2、1——完全可以边进边出，出场顺序可以有很多种。
把剩下的小函数一次配齐：
void StackInit(ST* ps)
{
assert(ps);
ps->a = (STDataType*)malloc(sizeof(STDataType) * 4); // 初始容量4
if (ps->a == NULL)
{
perror("malloc fail");
exit(1);
}
ps->top = -1; // top 指向栈顶元素
ps->capacity = 4;
}
void StackDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
STDataType StackTop(ST* ps)
{
assert(ps);
assert(ps->top != -1); // 空栈不能偷看
return ps->a[ps->top];
}
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == -1;
}
int StackSize(ST* ps)
{
assert(ps);
return ps->top + 1;
}括号配对：栈的第一次出场
经典面试题（力扣 20 有效的括号）：判断一串括号是否匹配。思路很清爽——左括号入栈，遇到右括号就出栈比对，类型对得上继续，最后栈为空才算圆满：
if (*s == '(' || *s == '{' || *s == '[')
StackPush(&stack, *s);
else
{
char top = StackTop(&stack);
if ((*s == ')' && top == '(') ||
(*s == '}' && top == '{') ||
(*s == ']' && top == '['))
StackPop(&stack);
else
return false; // 类型对不上，不匹配
}把判断过程装进完整的函数里，记得每个出口都要顺手销毁栈，不留小垃圾：
bool isValid(char* s)
{
ST stack;
StackInit(&stack);
while (*s)
{
if (*s == '(' || *s == '{' || *s == '[')
{
StackPush(&stack, *s);
}
else
{
if (StackEmpty(&stack)) // 右括号先多了出来
{
StackDestroy(&stack);
return false;
}
char top = StackTop(&stack);
if ((*s == ')' && top == '(') ||
(*s == '}' && top == '{') ||
(*s == ']' && top == '['))
{
StackPop(&stack);
}
else
{
StackDestroy(&stack);
return false;
}
}
s++;
}
bool isEmpty = StackEmpty(&stack); // 栈空才算匹配圆满
StackDestroy(&stack);
return isEmpty;
}队列：排队的礼貌
队列正好反过来：一端只进（队尾），另一端只出（队头），遵守 FIFO（First In First Out，先进先出）。它像单链表，但多了根队尾指针，于是可以尾插头删，两头都痛快。
typedef struct QueueNode
{
QDDataType data;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* front; // 队头
QNode* back; // 队尾
int size; // 元素个数
}Queue;把 front、back、size 包进一个结构体是小巧思：不用在每次调用时传两个指针，也顺手解决了 size 的统计。要改变
int传int*，要改变Queue就传Queue*——道理是同一棵藤上的。
入队在队尾接上节点，出队从队头摘下节点，摘完记得处理「队列刚好空了」的情况：
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->size != 0);
if (pq->front->next == NULL) // 只剩一个节点
{
free(pq->front);
pq->front = pq->back = NULL;
}
else // 多个节点
{
QNode* tmp = pq->front;
pq->front = pq->front->next;
free(tmp);
}
pq->size--;
}把剩下的配套小函数也一次配齐：
void QueueInit(Queue* pq)
{
assert(pq);
pq->front = NULL;
pq->back = NULL;
pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->front;
while (cur)
{
QNode* tmp = cur;
cur = cur->next;
free(tmp);
}
pq->front = NULL;
pq->back = NULL;
pq->size = 0;
}
void QueuePush(Queue* pq, QDDataType x)
{
assert(pq);
QNode* newNode = (QNode*)malloc(sizeof(QNode));
if (newNode == NULL)
{
perror("malloc fail");
exit(1);
}
newNode->next = NULL;
newNode->data = x;
if (pq->back == NULL) // 空队列：新节点既是头也是尾
pq->front = pq->back = newNode;
else
{
pq->back->next = newNode; // 接到队尾
pq->back = newNode;
}
pq->size++;
}
QDDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->size != 0); // 空队列没有队头
return pq->front->data;
}
QDDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->size != 0);
return pq->back->data;
}
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->size == 0;
}你变我，我变你的小魔法
面试题三连，全是栈和队列互相扮演对方：
两个队列实现栈（力扣 225 用队列实现栈）：入栈时丢进非空的那个队列；出栈时把前 n-1 个元素搬到空队列，最后剩下的那个就是栈顶。
两个栈实现队列（力扣 232 用栈实现队列）：入队一律压 s1；出队时如果 s2 是空的，就把 s1 全部倒入 s2 再弹——倒一遍顺序正好翻过来。
循环队列（力扣 622 设计循环队列）：只有 k 个位置的环。小诀窍是多开一个空间，head == tail 判空、(tail + 1) % (k + 1) == head 判满，空和满就再也不会撞衫。
MyCircularQueue* myCircularQueueCreate(int k)
{
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->a = (int*)malloc(sizeof(int) * (k + 1)); // 多开 1 个空间
obj->head = 0;
obj->tail = 0;
obj->k = k;
return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
return obj->head == obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
return (obj->tail + 1) % (obj->k + 1) == obj->head;
}// 入队与取队尾
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
if (myCircularQueueIsFull(obj))
return false;
obj->a[obj->tail] = value;
obj->tail++;
obj->tail %= (obj->k + 1); // 走到头就绕回起点
return true;
}
int myCircularQueueRear(MyCircularQueue* obj)
{
if (myCircularQueueIsEmpty(obj))
return -1;
return obj->a[(obj->tail + obj->k) % (obj->k + 1)]; // tail 往回退一步
}出队和取队头就是它的镜像动作啦：
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
if (myCircularQueueIsEmpty(obj))
return false;
obj->head++;
obj->head %= (obj->k + 1); // 同样绕圈走
return true;
}
int myCircularQueueFront(MyCircularQueue* obj)
{
if (myCircularQueueIsEmpty(obj))
return -1;
return obj->a[obj->head];
}
✿ 摘要
- 栈 LIFO，进出都走栈顶；
top指向元素还是下一位置，初始化和判满都不同。 - 栈扩容照抄顺序表：不够就 2 倍 realloc。
- 括号匹配：左括号入栈，右括号出栈比对，最后栈空才算匹配。
- 队列 FIFO，队尾进队头出；
front/back/size包成一个结构体更好管理。 - 两队列可扮栈、两栈可扮队列；循环队列多开一个空间区分空和满。
愿当下的花如你所见般美丽
评论交流
欢迎留下你的想法