栈与队列综合实战（二）：最小栈设计、循环双端队列设计

好，咱们接着往下聊。上一章我们把栈和队列的基本操作捋了一遍，今天要玩点更实际的——两个经典的设计题：最小栈和循环双端队列。

说实话，这两个东西在面试里出现的频率极高。我当年去某大厂面试，第一轮手撕代码就是最小栈。当时我心想：这不就是个栈吗？加个变量记录最小值不就完了？结果一写就掉坑里了。嗯，咱们今天就把这些坑一个一个填平。

一、最小栈设计

1.1 问题本质

最小栈，说白了就是：一个普通的栈，加一个能O(1)返回最小值的功能。

你可能会想：那我用一个变量 min 记录当前最小值，每次 push 的时候更新一下，不就行了？

问题来了——当最小值被 pop 出去之后，新的最小值是什么？ 你没法知道。这就是核心难点。

1.2 我的解法：辅助栈

我个人习惯用双栈法。一个栈存数据，另一个栈存当前的最小值。

思路很简单：

• push 时，数据栈正常压入；辅助栈压入当前最小值（即 min(当前值, 辅助栈栈顶)）
• pop 时，两个栈同时弹出
• getMin 时，直接返回辅助栈栈顶

这样，两个栈的深度始终一致，pop 操作不会丢失最小值信息。

typedef struct {
    int *data;      // 数据栈
    int *minStack;  // 辅助最小值栈
    int top;        // 栈顶指针
    int capacity;   // 容量
} MinStack;

MinStack* minStackCreate(int capacity) {
    MinStack *obj = (MinStack*)malloc(sizeof(MinStack));
    obj->data = (int*)malloc(sizeof(int) * capacity);
    obj->minStack = (int*)malloc(sizeof(int) * capacity);
    obj->top = -1;
    obj->capacity = capacity;
    return obj;
}

void minStackPush(MinStack* obj, int val) {
    if (obj->top == obj->capacity - 1) return; // 栈满
    obj->top++;
    obj->data[obj->top] = val;
    // 辅助栈：压入当前最小值
    if (obj->top == 0) {
        obj->minStack[obj->top] = val;
    } else {
        int curMin = obj->minStack[obj->top - 1];
        obj->minStack[obj->top] = (val < curMin) ? val : curMin;
    }
}

void minStackPop(MinStack* obj) {
    if (obj->top == -1) return;
    obj->top--;
}

int minStackTop(MinStack* obj) {
    return obj->data[obj->top];
}

int minStackGetMin(MinStack* obj) {
    return obj->minStack[obj->top];
}

1.3 避坑指南

我曾经在项目里用最小栈做任务优先级管理，结果出了个bug——辅助栈没同步pop。数据栈pop了，辅助栈没动，getMin返回的全是历史最小值。排查了半小时才发现。

所以记住：两个栈的push和pop必须成对出现，一个都不能少。

二、循环双端队列设计

2.1 什么是循环双端队列？

双端队列（Deque）就是两端都能插入和删除的队列。循环双端队列，就是底层用环形数组实现的双端队列。

你想想看，如果用链表实现双端队列，插入删除确实方便，但内存碎片和缓存不友好。用环形数组，空间连续、访问快、没有碎片，是嵌入式场景的首选。

2.2 核心设计要点

环形数组的关键就两个：头指针和尾指针。我习惯用头指针指向第一个有效元素，尾指针指向最后一个有效元素的下一个位置。

这样设计的好处是：空队列时 head == tail，满队列时 (tail + 1) % capacity == head。注意，这里会浪费一个元素空间来区分空和满。

typedef struct {
    int *arr;
    int head;       // 指向第一个有效元素
    int tail;       // 指向最后一个有效元素的下一个位置
    int capacity;   // 容量（实际可用 capacity - 1）
} MyCircularDeque;

MyCircularDeque* myCircularDequeCreate(int k) {
    MyCircularDeque *obj = (MyCircularDeque*)malloc(sizeof(MyCircularDeque));
    obj->arr = (int*)malloc(sizeof(int) * (k + 1)); // 多分配一个
    obj->head = 0;
    obj->tail = 0;
    obj->capacity = k + 1;
    return obj;
}

bool myCircularDequeInsertFront(MyCircularDeque* obj, int value) {
    if (myCircularDequeIsFull(obj)) return false;
    obj->head = (obj->head - 1 + obj->capacity) % obj->capacity;
    obj->arr[obj->head] = value;
    return true;
}

bool myCircularDequeInsertLast(MyCircularDeque* obj, int value) {
    if (myCircularDequeIsFull(obj)) return false;
    obj->arr[obj->tail] = value;
    obj->tail = (obj->tail + 1) % obj->capacity;
    return true;
}

bool myCircularDequeDeleteFront(MyCircularDeque* obj) {
    if (myCircularDequeIsEmpty(obj)) return false;
    obj->head = (obj->head + 1) % obj->capacity;
    return true;
}

bool myCircularDequeDeleteLast(MyCircularDeque* obj) {
    if (myCircularDequeIsEmpty(obj)) return false;
    obj->tail = (obj->tail - 1 + obj->capacity) % obj->capacity;
    return true;
}

int myCircularDequeGetFront(MyCircularDeque* obj) {
    if (myCircularDequeIsEmpty(obj)) return -1;
    return obj->arr[obj->head];
}

int myCircularDequeGetRear(MyCircularDeque* obj) {
    if (myCircularDequeIsEmpty(obj)) return -1;
    int rear = (obj->tail - 1 + obj->capacity) % obj->capacity;
    return obj->arr[rear];
}

bool myCircularDequeIsEmpty(MyCircularDeque* obj) {
    return obj->head == obj->tail;
}

bool myCircularDequeIsFull(MyCircularDeque* obj) {
    return (obj->tail + 1) % obj->capacity == obj->head;
}

三、知识体系总览

下面这张图把本章的核心逻辑串起来了。你看一眼，心里就有谱了。

四、总结与经验

这两个设计题，说白了就是考你对数据结构的理解深度。最小栈考的是「如何用空间换时间」，循环双端队列考的是「环形缓冲区的边界处理」。

我在实际项目中，最小栈用在实时任务调度器里，用来快速获取当前优先级最高的任务。循环双端队列则用在串口数据缓冲里，两端都能读写，非常灵活。

最后送你一句话：写代码容易，写对边界条件的代码难。多花点时间在空、满、边界这三种情况上，你的代码质量会上一个台阶。

---

公众号:蓝海资料掘金营，微信deep3321