【刷题专栏—突破思维】栈和队列

2024-01-03 07:54:38

在这里插入图片描述

前言:
本篇博客讲解有关栈及队列的习题:有效的括号、用队列实现栈、用栈实现队列、设计循环队列。


1. 有效的括号

题目链接:Leetcode 20. 有效的括号

题目介绍
给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。
3.每个右括号都有一个对应的相同类型的左括号。
示例 1:
输入:s = “()”
输出:true
示例 2:
输入:s = “()[]{}”
输出:true
示例 3:
输入:s = “(]”
输出:false

这是一个典型的括号匹配问题,可以使用栈来解决。基本思路如下:

  1. 遍历字符串,对于每个字符:

    • 如果是左括号(‘(’,‘{’,‘[’),将其压入栈。
    • 如果是右括号(‘)’,‘}’,‘]’),则判断栈是否为空。
      • 如果栈为空,说明没有匹配的左括号,返回 false。
      • 如果栈不为空,弹出栈顶元素,并判断是否和当前右括号匹配。
        • 如果匹配,继续遍历下一个字符。
        • 如果不匹配,返回 false。
  2. 遍历完字符串后,检查栈是否为空。

    • 如果栈为空,说明所有括号都匹配,返回 true。
    • 如果栈不为空,说明有左括号没有匹配,返回 false。

代码实现:

// 定义栈元素的数据类型
typedef int STDataType;

// 定义栈结构体
typedef struct Stack {
    STDataType* a;   // 存储栈元素的数组
    int top;         // 标识栈顶
    int capacity;    // 容量
} ST;

// 初始化栈
void StackInit(ST* pst) {
    assert(pst);
    
    pst->a = NULL;
    pst->capacity = 0;
    pst->top = 0; // 指向栈顶下一个元素
}

// 销毁栈
void StackDestroy(ST* pst) {
    assert(pst);

    free(pst->a);
}

// 入栈
void StackPush(ST* pst, STDataType x) {
    assert(pst);

    // 如果栈满,进行动态扩容
    if (pst->top == pst->capacity) {
        int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
        STDataType* temp = realloc(pst->a, sizeof(STDataType) * newcapacity);
        if (temp == NULL) {
            perror("realloc fail");
            return;
        }

        pst->a = temp;
        pst->capacity = newcapacity;
    }

    pst->a[pst->top] = x;
    pst->top++;
}

// 出栈
void StackPop(ST* pst) {
    assert(pst);
    // 栈不为空
    assert(pst->top > 0);

    pst->top--;
}

// 获取栈顶元素
STDataType StackTop(ST* pst) {
    assert(pst);
    // 栈不为空
    assert(pst->top > 0);

    return pst->a[pst->top - 1];
}

// 判断栈是否为空
bool StackEmpty(ST* pst) {
    assert(pst);

    return pst->top == 0;
}

// 判断给定字符串是否是有效的括号组合
bool isValid(char* s) {
    ST st;
    StackInit(&st);

    // 遍历字符串
    while (*s) {
        if (*s == '[' || *s == '(' || *s == '{') {
            // 左括号入栈
            StackPush(&st, *s);
        } else {
            // 右括号处理
            // 如果栈为空,说明右括号多于左括号,返回 false
            if (StackEmpty(&st)) {
                StackDestroy(&st);
                return false;
            }

            char top = StackTop(&st);
            StackPop(&st);

            // 判断右括号和栈顶左括号是否匹配
            if ((*s == ']' && top != '[') ||
                (*s == ')' && top != '(') ||
                (*s == '}' && top != '{')) {
                StackDestroy(&st);
                return false;
            }
        }
        ++s;
    }

    // 栈为空,说明左括号多于右括号,返回 true
    bool ret = StackEmpty(&st);
    StackDestroy(&st);

    return ret;
}

2. 用队列实现栈

题目链接:225. 用队列实现栈

题目描述:
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。
实现 MyStack 类:
1.void push(int x) 将元素 x 压入栈顶。
2.int pop() 移除并返回栈顶元素。
3.int top() 返回栈顶元素。
4.boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。
注意:
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。

两个队列之间进行元素的转移,以模拟栈的后进先出(LIFO)特性。基本思路:

  1. 使用两个队列,分别称为queue1和queue2。

  2. 当需要push一个元素时,将其加入非空的队列(假设初始时选择queue1)。

  3. 当需要pop一个元素时,将非空队列的前n-1个元素出队并入队到另一个空队列,然后将剩余的最后一个元素出队(即模拟栈的pop操作)。

  4. 将队列互换,使得新的非空队列成为主队列。

    在这里插入图片描述
    代码实现:

// 定义队列中元素的数据类型
typedef int QDataType;

// 节点结构体,表示队列中的每个元素
typedef struct QueueNode {
    QDataType val;           // 元素的值
    struct QueueNode* next;  // 指向下一个节点的指针
} QNode;

// 队列结构体,包含队头、队尾和元素数量信息
typedef struct Queue {
    QNode* phead;  // 队头节点
    QNode* ptail;  // 队尾节点
    int size;      // 元素长度
} Queue;

// 初始化队列,设置队头、队尾为NULL,元素数量为0
void QueueInit(Queue* pq) {
    assert(pq);
    pq->phead = pq->ptail = NULL;
    pq->size = 0;
}

// 销毁队列,释放队列中每个节点的内存
void QueueDestroy(Queue* pq) {
    assert(pq);

    QNode* cur = pq->phead;
    while (cur) {
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->phead = pq->ptail = NULL;
    pq->size = 0;
}

// 入队操作,将元素加入队尾
void QueuePush(Queue* pq, QDataType x) {
    assert(pq);

    // 创建新节点
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL) {
        perror("malloc fail");
        return;
    }

    // 设置节点值和指针
    newnode->val = x;
    newnode->next = NULL;

    // 判断队列是否为空,如果是,将队头和队尾都设置为新节点
    if (pq->ptail == NULL) {
        pq->ptail = pq->phead = newnode;
    } else {
        // 否则,将新节点连接到队尾,并更新队尾指针
        pq->ptail->next = newnode;
        pq->ptail = newnode;
    }

    // 更新元素数量
    pq->size++;
}

// 出队操作,删除队头元素
void QueuePop(Queue* pq) {
    assert(pq->phead);
    assert(pq);

    // 记录需要删除的节点
    QNode* del = pq->phead;
    // 更新队头指针
    pq->phead = pq->phead->next;
    // 释放节点内存
    free(del);
    del = NULL;

    // 如果队头为空,表示队列已空,更新队尾指针
    if (pq->phead == NULL)
        pq->ptail = NULL;

    // 更新元素数量
    pq->size--;
}

// 获取队头元素的值
QDataType QueueFront(Queue* pq) {
    assert(pq);
    assert(pq->phead);

    return pq->phead->val;
}

// 获取队尾元素的值
QDataType QueueBack(Queue* pq) {
    assert(pq);
    assert(pq->ptail);

    return pq->ptail->val;
}

// 判断队列是否为空
bool QueueEmpty(Queue* pq) {
    assert(pq);

    return pq->phead == NULL;
}

// 获取队列的元素数量
int QueueSize(Queue* pq) {
    assert(pq);

    return pq->size;
}



// 定义MyStack结构体,包含两个队列
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;

// 创建并初始化MyStack结构体,内部调用QueueInit初始化两个队列
MyStack* myStackCreate() {
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);

    return pst;
}

// 入栈操作,将元素加入非空队列
void myStackPush(MyStack* obj, int x) {
    if (!QueueEmpty(&obj->q1)) {
        QueuePush(&obj->q1, x);
    } else {
        QueuePush(&obj->q2, x);
    }
}

// 出栈操作,模拟栈的pop操作
int myStackPop(MyStack* obj) {
    // 选择非空队列为需要操作的队列,将元素转移到另一队列,直到只剩一个元素
    Queue* emptyq = &obj->q1;
    Queue* nonemptyq = &obj->q2;
    if (!QueueEmpty(&obj->q1)) {
        emptyq = &obj->q2;
        nonemptyq = &obj->q1;
    }

    while (QueueSize(nonemptyq) > 1) {
        QueuePush(emptyq, QueueFront(nonemptyq));
        QueuePop(nonemptyq);
    }

    // 获取并删除最后一个元素,模拟栈的pop操作
    int top = QueueFront(nonemptyq);
    QueuePop(nonemptyq);
    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);
}

// 释放MyStack结构体和两个队列的内存
void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);

    free(obj);
}


3. 用栈是实现队列

题目链接:Leetcode 232.用栈实现队列

题目描述:
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty):
实现 MyQueue 类:
1.void push(int x) 将元素 x 推到队列的末尾
2.int pop() 从队列的开头移除并返回元素
3.int peek() 返回队列开头的元素
4.boolean empty() 如果队列为空,返回 true ;否则,返回 false

用两个栈来实现队列的基本思路:

  1. 两个栈: 使用两个栈,一个用于入队(push操作),另一个用于出队(pop操作)。

  2. 入队操作: 将元素压入入队栈中。这样,最新的元素会始终位于栈顶,而最早加入的元素则位于栈底。

  3. 出队操作: 如果出队栈不为空,直接从出队栈弹出元素;否则,将入队栈的元素逐个弹出并压入出队栈,然后从出队栈弹出元素。这确保了队列的先进先出特性。
    在这里插入图片描述
    代码实现:

typedef int STDataType;

typedef struct Stack {
    STDataType* a;   // 栈数组
    int top;         // 标识栈顶
    int capacity;    // 容量
} ST;

// 栈的初始化
void StackInit(ST* pst) {
    assert(pst);
    pst->a = NULL;
    pst->capacity = 0;
    pst->top = 0;  // 指向栈顶下一个元素
}

// 栈的销毁
void StackDestroy(ST* pst) {
    assert(pst);
    free(pst->a);
}

// 入栈操作
void StackPush(ST* pst, STDataType x) {
    assert(pst);

    if (pst->top == pst->capacity) {
        int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
        STDataType* temp = realloc(pst->a, sizeof(STDataType) * newcapacity);
        if (temp == NULL) {
            perror("realloc fail");
            return;
        }

        pst->a = temp;
        pst->capacity = newcapacity;
    }

    pst->a[pst->top] = x;
    pst->top++;
}

// 出栈操作
void StackPop(ST* pst) {
    assert(pst);
    // 不为空
    assert(pst->top > 0);

    pst->top--;
}

// 获取栈顶元素
STDataType StackTop(ST* pst) {
    assert(pst);
    // 不为空
    assert(pst->top > 0);

    return pst->a[pst->top - 1];
}

// 判断栈是否为空
bool StackEmpty(ST* pst) {
    assert(pst);
    return pst->top == 0;
}

// 获取栈的大小
int StackSize(ST* pst) {
    assert(pst);
    return pst->top;
}

// 队列结构
typedef struct {
    ST pushst;  // 入队栈
    ST popst;   // 出队栈
} MyQueue;

// 创建一个新的队列
MyQueue* myQueueCreate() {
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    if (obj != NULL) {
        StackInit(&obj->pushst);
        StackInit(&obj->popst);
    }

    return obj;
}

// 将元素入队
void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->pushst, x);
}

// 查看队头元素
int myQueuePeek(MyQueue* obj) {
    // popst为空,StackEmpty(&obj->popst)为真
    // popst不为空,直接执行return StackPop(&obj->popst);
    if (StackEmpty(&obj->popst)) {
        // pushst若不为空,将pushst中数据推入popst中
        while (!StackEmpty(&obj->pushst)) {
            StackPush(&obj->popst, StackTop(&obj->pushst));
            StackPop(&obj->pushst);
        }
    }
    return StackTop(&obj->popst);
}

// 出队操作
int myQueuePop(MyQueue* obj) {
    STDataType front = myQueuePeek(obj);
    StackPop(&obj->popst);

    return front;
}

// 判断队列是否为空
bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->pushst) && StackEmpty(&obj->popst);
}

// 释放队列内存
void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->pushst);
    StackDestroy(&obj->popst);
    free(obj);
}


4. 设计循环队列

题目链接:Leetcode 622. 设计循环队列

题目描述:
设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。
你的实现应该支持如下操作:
1.MyCircularQueue(k): 构造器,设置队列长度为 k 。
2.Front: 从队首获取元素。如果队列为空,返回 -1 。
3.Rear: 获取队尾元素。如果队列为空,返回 -1 。
4.enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
5.deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
6.isEmpty(): 检查循环队列是否为空。
7.isFull(): 检查循环队列是否已满。
示例:
MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false,队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4

基本思路:
在实现循环队列时,我们选择数组来实现。相对于循环链表,数组实现循环队列更加容易访问数据,且在空间上连续。
在这里插入图片描述
代码实现:

// 定义循环队列的结构体
typedef struct {
    int* a;     // 用于存储队列元素的数组
    int front;   // 指向队列头部
    int back;    // 指向队列尾部的下一位
    int k;       // 队列的容量
} MyCircularQueue;

// 创建循环队列并初始化
MyCircularQueue* myCircularQueueCreate(int k) {
    // 分配内存并初始化结构体成员
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a = (int*)malloc(sizeof(int) * (k + 1)); // 长度为 k+1,避免判满和判空时的歧义
    obj->front = 0;
    obj->back = 0;
    obj->k = k;

    return obj;
}

// 判断循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->back == obj->front;
}

// 获取循环队列尾部元素
int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) {
        return -1; // 队列为空,返回特定值表示错误
    } else {
        return obj->a[(obj->back + obj->k) % (obj->k + 1)]; // 利用取模操作实现循环
    }
}

// 判断循环队列是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->back + 1) % (obj->k + 1) == obj->front; // 利用取模操作实现循环
}

// 入队操作
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj)) {
        return false; // 队列已满,无法入队
    }
    obj->a[obj->back] = value; // 将元素存储在队尾
    ++obj->back; // 尾指针后移
    obj->back %= (obj->k + 1); // 利用取模操作实现循环
    return true;
}

// 出队操作
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) {
        return false; // 队列为空,无法出队
    }
    ++obj->front; // 头指针后移
    obj->front %= (obj->k + 1); // 利用取模操作实现循环
    return true;
}

// 获取循环队列头部元素
int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) {
        return -1; // 队列为空,返回特定值表示错误
    }
    return obj->a[obj->front]; // 返回队头元素
}

// 释放循环队列的内存
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

在这里插入图片描述
如果你喜欢这篇文章,点赞👍+评论+关注??哦!
欢迎大家提出疑问,以及不同的见解。

文章来源:https://blog.csdn.net/weixin_73551991/article/details/135353057
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。