目录

前言

一、有效的括号

二、用队列实现栈

三、用栈实现队列

四、设计循环队列

总结

前言

        本期博客博主将为大家带来一些经典的栈和队列OJ题详解，希望能加深大家对栈和队列的理解。下面就让我们正式开始吧！

一、有效的括号

        题目链接：20. 有效的括号 - 力扣（LeetCode）

        解题思路分析：本题我们可以借助数据结构 —— 栈，来遍历字符串，如果是左括号就入栈，如果是右括号就取栈顶元素比较，看看是否匹配。

        实现逻辑解析：

        1.初始化阶段：创建并初始化栈结构，准备遍历字符串。

bool isValid(char* s) {
    //借助数据结构 —— 栈
    ST st;          // 声明一个栈结构体变量
    STInit(&st);    // 初始化栈
    char* pi = s;   // 创建指针指向字符串开头

        2.左括号处理：遇到任何左括号 (、[、{ 都直接压入栈中。

    while(*pi != '\0')  // 遍历字符串直到结束符
    {
        //左括号入栈
        if(*pi == '(' || *pi == '[' || *pi == '{')
        {
            STPush(&st,*pi);  // 将左括号压入栈中
        }

        3.右括号前置检查：在尝试匹配之前，先检查栈是否为空。如果栈为空但遇到了右括号，说明没有对应的左括号，直接返回false。

        else  // 遇到右括号
        {
            //栈不为空才能取栈顶
            if(STEmpty(&st))  // 检查栈是否为空
            {
                STDestroy(&st);  // 销毁栈释放内存
                return false;     // 栈空但遇到右括号，无效
            }

        4.括号匹配检查：检查栈顶左括号与当前右括号是否类型匹配。如果类型不匹配，返回false。

            char top = STTop(&st);  // 获取栈顶元素但不弹出
            if((top == '(' && *pi != ')')  // 栈顶是'('但当前不是')'
             ||(top == '[' && *pi != ']')  // 栈顶是'['但当前不是']'
             ||(top == '{' && *pi != '}')) // 栈顶是'{'但当前不是'}'
             {
                STDestroy(&st);  // 销毁栈
                return false;     // 括号类型不匹配，无效
             }

        5.匹配成功处理：括号匹配成功，弹出栈顶元素，指针移动到下一个字符。

             //本次是匹配 —— 出栈
             STPop(&st);  // 匹配成功，弹出栈顶元素
        }
        pi++;  // 移动到下一个字符
    }

        6.最终检查：遍历完成后，检查栈是否为空。如果栈为空说明所有括号都匹配成功，否则说明有未匹配的左括号。

    //判断栈是否为空，为空则为有效，非空则为无效
    bool ret = STEmpty(&st) ? true : false;  // 检查栈是否为空
    STDestroy(&st);  // 销毁栈释放内存
    return ret;      // 返回最终结果
}

        算法流程图如下：

开始
  ↓
初始化栈
  ↓
遍历字符串
  ↓
是左括号? → 是 → 入栈 → 继续遍历
  ↓否
检查栈是否空? → 是 → 返回false
  ↓否
获取栈顶元素
  ↓
类型匹配? → 否 → 返回false
  ↓是
弹出栈顶，继续遍历
  ↓
遍历结束
  ↓
栈为空? → 是 → 返回true
  ↓否
返回false

        完整代码如下所示：

bool isValid(char* s) {
    //借助数据结构 —— 栈
    ST st;
    STInit(&st);
    char* pi = s;
    while(*pi != '\0')
    {
        //左括号入栈
        if(*pi == '(' || *pi == '[' || *pi == '{')
        {
            STPush(&st,*pi);
        }
        else
        {
            //右括号 —— 取栈顶，比较，匹配则出栈，不匹配直接返回false
            //栈不为空才能取栈顶
            if(STEmpty(&st))
            {
                STDestroy(&st);
                return false;
            }
            char top = STTop(&st);
            if((top == '(' && *pi != ')')
             ||(top == '[' && *pi != ']')
             ||(top == '{' && *pi != '}'))
             {
                STDestroy(&st);
                return false;
             }
             //本次是匹配 —— 出栈
             STPop(&st);
        }
        pi++;
    }
    //判断栈是否为空，为空则为有效，非空则为无效
    bool ret = STEmpty(&st) ? true : false;
    STDestroy(&st);
    return ret;
}

二、用队列实现栈

        题目链接如下：225. 用队列实现栈 - 力扣（LeetCode）

        解题思路分析：

  • 入栈：往不为空的队列中插入数据；
  • 出栈：把不为空的队列中的前size - 1个数据挪到另一个队列，再将最后一个数据出队列；
  • 取栈顶（不出数据）：找不为空的队列，返回队尾数据。

        实现逻辑如下：

        1.数据结构定义：在MyStack结构中定义两个队列。

typedef struct {
    Queue q1;  // 队列1
    Queue q2;  // 队列2
} MyStack;

        2.栈的创建和初始化：分配内存并初始化两个队列。

MyStack* myStackCreate() {
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->q1);  // 初始化队列1
    QueueInit(&pst->q2);  // 初始化队列2
    return pst;
}

        3.入栈操作：向非空队列中添加新元素，如果两个队列都为空，则任意选择一个。

void myStackPush(MyStack* obj, int x) {
    //往不为空的队列中插入数据
    if(!QueueEmpty(&obj->q1)) {
        QueuePush(&obj->q1, x);  // 如果q1不为空，插入q1
    } else {
        QueuePush(&obj->q2, x);  // 否则插入q2（q2可能为空或不为空）
    }
}

        4.出栈操作：

初始状态：q1 = [1, 2, 3], q2 = []  (栈顶为3)
步骤1：将q1的前2个元素移到q2 → q1 = [3], q2 = [1, 2]
步骤2：弹出q1的最后一个元素 → 返回3
最终状态：q1 = [], q2 = [1, 2]  (栈顶变为2)

        

int myStackPop(MyStack* obj) {
    //确定哪个队列为空，哪个不为空
    Queue* emp = &obj->q1;      // 假设q1为空队列
    Queue* noneEmp = &obj->q2;  // 假设q2为非空队列
    
    if(QueueEmpty(&obj->q2)) {  // 如果q2实际为空
        emp = &obj->q2;         // 交换角色
        noneEmp = &obj->q1;
    }
    
    //将非空队列的前size-1个元素转移到空队列
    while(QueueSize(noneEmp) > 1) {
        QueuePush(emp, QueueFront(noneEmp));  // 队头元素转移到空队列
        QueuePop(noneEmp);                    // 弹出队头
    }
    
    //弹出最后一个元素（即栈顶）
    int top = QueueFront(noneEmp);
    QueuePop(noneEmp);
    return top;
}

        5.获取栈顶元素：由于总是向非空队列总添加新元素，所以非空队列的队尾就是最后入栈的元素（栈顶）。

int myStackTop(MyStack* obj) {
    //返回非空队列的队尾元素
    if(!QueueEmpty(&obj->q1)) {
        return QueueBack(&obj->q1);  // 队列的队尾就是栈顶
    } else {
        return QueueBack(&obj->q2);
    }
}

        6.判断栈是否为空：两个队列都为空时栈才为空。

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

        7.释放栈内存：

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);  // 销毁队列1
    QueueDestroy(&obj->q2);  // 销毁队列2
    free(obj);               // 释放栈结构内存
    obj = NULL;              // 避免野指针
}

        本题的执行逻辑如下：

操作序列：push(1), push(2), push(3), pop(), top()

执行过程：
push(1) → q1: [1], q2: []
push(2) → q1: [1, 2], q2: []
push(3) → q1: [1, 2, 3], q2: []
pop()   → 转移前2个到q2: q1: [3], q2: [1, 2] → 弹出3
top()   → 返回q2的队尾: 2

三、用栈实现队列

        题目链接：232. 用栈实现队列 - 力扣（LeetCode）

        解题思路分析：

  • 入队列：往pushST中插入数据；
  • 出队列：popST不为空直接出，否则将pushST中的数据先倒过去再出数据；
  • 取队头：逻辑和出队列一样，但是不出数据，popST不为空直接取队头，否则就将pushST中的数据先搞过去再取队头。

        实现逻辑如下：

        1.数据结构定义：用两个栈实现队列结构，其中一个栈用于入队操作，另一个用于出队操作。

typedef struct {
    ST pushST;  // 用于入队操作的栈
    ST popST;   // 用于出队操作的栈
} MyQueue;

        2.队列的创建和初始化：分配内存并初始化两个栈。

MyQueue* myQueueCreate() {
    MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&pq->pushST);  // 初始化入队栈
    STInit(&pq->popST);   // 初始化出队栈
    return pq;
}

        3.入队操作：直接将新元素压入pushST栈。

void myQueuePush(MyQueue* obj, int x) {
    // 直接往pushST中插入数据
    STPush(&obj->pushST, x);
}

        4.出队操作：

初始状态：pushST = [3, 2, 1] (1是栈顶), popST = [] 
步骤1：将pushST倒入popST → pushST = [], popST = [1, 2, 3] (3是栈顶)
步骤2：弹出popST栈顶 → 返回1（队列的第一个元素）

int myQueuePop(MyQueue* obj) {
    // popST为空时，需要将pushST的所有元素倒入popST
    if(STEmpty(&obj->popST)) {
        while(!STEmpty(&obj->pushST)) {
            // 取pushST栈顶，入popST栈，然后弹出
            STPush(&obj->popST, STTop(&obj->pushST));
            STPop(&obj->pushST);
        }
    }
    
    // 从popST弹出栈顶元素（即队头）
    int top = STTop(&obj->popST);
    STPop(&obj->popST);
    return top;
}

        5.获取队头元素：只查看队头元素，不弹出。

int myQueuePeek(MyQueue* obj) {
    // popST为空时，需要将pushST的所有元素倒入popST
    if(STEmpty(&obj->popST)) {
        while(!STEmpty(&obj->pushST)) {
            STPush(&obj->popST, STTop(&obj->pushST));
            STPop(&obj->pushST);
        }
    }
    
    // 返回popST栈顶元素（即队头）
    int top = STTop(&obj->popST);
    return top;
}

        6.判断队列是否为空：两个栈都为空时队列才为空。

bool myQueueEmpty(MyQueue* obj) {
    return STEmpty(&obj->popST) && STEmpty(&obj->pushST);
}

        7.释放队列内存：

void myQueueFree(MyQueue* obj) {
    STDestroy(&obj->popST);   // 销毁出队栈
    STDestroy(&obj->pushST);  // 销毁入队栈
    free(obj);                // 释放队列结构内存
    obj = NULL;               // 避免野指针
}

        本题的执行流程示例如下：

操作序列：push(1), push(2), push(3), pop(), push(4), pop(), pop()

执行过程：
push(1) → pushST: [1], popST: []
push(2) → pushST: [2, 1], popST: []      (1在栈底，2在栈顶)
push(3) → pushST: [3, 2, 1], popST: []   (1在栈底，3在栈顶)

pop()   → 转移pushST到popST: pushST: [], popST: [1, 2, 3] (3在栈底，1在栈顶)
         → 弹出popST栈顶: 返回1

push(4) → pushST: [4], popST: [2, 3]     (3在栈底，2在栈顶)

pop()   → popST不为空，直接弹出栈顶: 返回2
pop()   → popST不为空，直接弹出栈顶: 返回3
         → 现在popST为空，但pushST还有[4]

        完整代码如下：

typedef struct {
    ST pushST;
    ST popST;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&pq->pushST);
    STInit(&pq->popST);

    return pq;
}

//入队列
void myQueuePush(MyQueue* obj, int x) {
    //往pushST中插入数据
    STPush(&obj->pushST,x);
}

//出队
int myQueuePop(MyQueue* obj) {
    //popST为空---将pushST（不为空）导入到popST
    if(STEmpty(&obj->popST))
    {
        while(!STEmpty(&obj->pushST))
        {
            //取栈顶，入popST栈，出栈
            STPush(&obj->popST,STTop(&obj->pushST));
            STPop(&obj->pushST);
        }
    }
    //popST不为空直接出
    int top = STTop(&obj->popST);
    STPop(&obj->popST);
    return top;
}

//取队头
int myQueuePeek(MyQueue* obj) {
    //popST为空---将pushST（不为空）导入到popST
    if(STEmpty(&obj->popST))
    {
        while(!STEmpty(&obj->pushST))
        {
            //取栈顶，入popST栈，出栈
            STPush(&obj->popST,STTop(&obj->pushST));
            STPop(&obj->pushST);
        }
    }
    //popST不为空直接取数据
    int top = STTop(&obj->popST);
    return top;
}

bool myQueueEmpty(MyQueue* obj) {
    return STEmpty(&obj->popST) && STEmpty(&obj->pushST);
}

void myQueueFree(MyQueue* obj) {
    STDesTroy(&obj->popST);
    STDesTroy(&obj->pushST);
    free(obj);
    obj = NULL;
}

四、设计循环队列

        题目链接如下：622. 设计循环队列 - 力扣（LeetCode）

        解题思路分析：使用数组实现队列，通过模运算实现循环使用空间，解决普通数组队列的"假溢出"问题。

  • 预留一个空位：区分队列空和满的状态

  • 模运算实现循环：通过 %(capacity+1) 实现指针循环

  • front指向队头元素，rear指向队尾元素的下一个位置

        实现逻辑如下：

        1.数据结构定义：

typedef struct {
    int* arr;        // 存储数据的数组
    int front;       // 队头指针（指向第一个元素）
    int rear;        // 队尾指针（指向下一个插入位置）
    int capacity;    // 队列的实际容量（可存储capacity个元素）
} MyCircularQueue;

        2.队列创建和初始化：

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* pq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    // 申请k+1个空间（实际容量为k）
    pq->arr = (int*)malloc(sizeof(int)*(k+1));
    pq->front = pq->rear = 0;  // 初始都指向0位置
    pq->capacity = k;          // 记录实际容量
    return pq;
}

        在这里我们申请k+1个空间，留一个空位是用于区分队列的空满状态。

  • 空队列：front == rear

  • 满队列：(rear+1) % (capacity+1) == front

        3.判断队列是否为空：front和rear指向同一位置时队列为空。

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->rear;
}

        4.判断队列是否已满：rear的下一个位置是front时队列为满。

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->rear + 1) % (obj->capacity + 1) == obj->front;
}

        5.入队操作：首先检查是否已满，然后在rear位置插入元素，最后rear指针后移并取模（实现循环）。

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj)) {
        return false;  // 队列已满，插入失败
    }
    
    obj->arr[obj->rear++] = value;           // 插入元素，rear后移
    obj->rear %= obj->capacity + 1;          // 循环处理
    return true;
}

        6.出队操作：这里只是移动指针，实际数据还在数组中（会被后续入队操作覆盖）

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)) {
        return false;  // 队列为空，删除失败
    }
    
    ++obj->front;                      // front指针后移
    obj->front %= obj->capacity + 1;   // 循环处理
    return true;
}

        7.获取队头元素：

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)) {
        return -1;
    }
    return obj->arr[obj->front];  // 直接返回front位置的元素
}

        8.获取队尾元素：

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)) {
        return -1;
    }
    
    int prev = obj->rear - 1;        // rear的前一个位置
    if(obj->rear == 0) {             // 处理边界情况
        prev = obj->capacity;        // 循环到数组末尾
    }
    return obj->arr[prev];
}

        下面还有一种更为简洁的等价写法：

int prev = (obj->rear - 1 + obj->capacity + 1) % (obj->capacity + 1);
return obj->arr[prev];

        9.释放内存：

void myCircularQueueFree(MyCircularQueue* obj) {
    if(obj->arr)
        free(obj->arr);    // 先释放数组内存
    free(obj);             // 再释放结构体内存
    obj = NULL;            // 避免野指针
}

        运行示例如下：假设k=3（容量为3），分配4个空间。

初始状态：front=0, rear=0
[ _, _, _, _ ]  空队列

插入1：front=0, rear=1
[1, _, _, _ ]

插入2：front=0, rear=2  
[1, 2, _, _ ]

插入3：front=0, rear=3
[1, 2, 3, _ ]  队列已满（(3+1)%4=0==front）

删除1：front=1, rear=3
[1, 2, 3, _ ]  front指向2

插入4：front=1, rear=0
[1, 2, 3, 4]   循环到开头

        完整代码如下：

typedef struct {
    int* arr;
    int front;      //队头
    int rear;       //队尾
    int capacity;   //循环队列的空间大小
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* pq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //申请k+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;
}

//向循环队列插入一个元素
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;
}

//从队首获取元素
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];
}



void myCircularQueueFree(MyCircularQueue* obj) {
    if(obj->arr)
        free(obj->arr);
    free(obj);
    obj = NULL;
}

总结

        以上就是本期博客的全部内容啦！希望这些OJ题能够加深大家对栈和队列相关知识的理解，谢谢大家的支持！

# 数据结构 # c语言 # 算法
Logo
乐奇 Rokid 开放社区

更多推荐

cover

智能眼镜新品扎堆：AR、VR、MR到底怎么分？

avatar 乐奇 Rokid 开放社区
cover

AI眼镜里面有晶振吗？智能眼镜的时钟系统

avatar 乐奇 Rokid 开放社区
cover

Meta Muse 爆火：12 天下载量反超 ChatGPT，个人 AI 智能体完整使用指南

avatar 乐奇 Rokid 开放社区