【数据结构】栈与队列经典oj题

深藏阁楼爱情的钟 2024-04-27 16:00 70阅读 0赞

![在这里插入图片描述][6ac7346dc5944908b5dd227e55fab217.gif_pic_center]

> ?write in front?  
> ?所属专栏：[初阶数据结构][Link 1]  
> ?️博客主页：[睿睿的博客主页][Link 2]  
> ?️代码仓库：?[VS2022\_C语言仓库][VS2022_C]  
> ?您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！  
> **关注我，关注我，关注我**，你们将会看到更多的优质内容！！

![在这里插入图片描述][85d8f838a7524c8bb8bed80b7ac059c1.gif_pic_center]

#### 文章目录 ####

*  前言
 *  例题1：\[循环队列\](https://leetcode.cn/problems/design-circular-queue/)
 *  例题2：\[用队列实现栈\](https://leetcode.cn/problems/implement-stack-using-queues/)
 *  例题3：\[用栈实现队列\](https://leetcode.cn/problems/implement-queue-using-stacks/)
 *  例题4：\[括号匹配问题\](https://leetcode.cn/problems/valid-parentheses/)
 *  总结

## 前言 ##

## 例题1：[循环队列][Link 3] ##

栈两种线性表示都能实现，队列呢？队列适合使用链表实现，使用顺序结构(即固定的连续空间)实现时会出现假溢出的问题，因此大佬们设计出了循环队列，循环队列就是为了解决顺序结构实现队列假溢出问题的现在我们来看看用顺序表实现队列：

![在这里插入图片描述][5e0d23d7c837457d8acf5458e72556cd.png]  
因为队列长度有限，所以我们要及时的判断什么时候队列满了。那么怎么判断队列是否满了呢？  
如果我们通过队尾和队顶是否相等来判断是否填满就会发现，在队列空的时候，队尾也等于对队顶。所以我们不能通过这种方法来判断：  
![在这里插入图片描述][2049ed103dbc4abbb2388e27e2e8fd1a.png]  
![在这里插入图片描述][913812518cb24b899f489ec1895bf35b.png]  
那么我们该如何解决呢？  
**方法1：**

加一个size来计数

**方法2：**  
多添加一个位置：

**空的情况：**  
![在这里插入图片描述][3e2d468c015f428cb5dc43bbf578ea02.png]  
**满的情况：**  
![在这里插入图片描述][44da4207a2cc4c898f265889b6b7b5f1.png]

下面我们就以方法2来实现代码：

typedef struct 
    {
        
        int *a;
        int front;
        int rear;
        int k;
    } MyCircularQueue;
    
    MyCircularQueue* myCircularQueueCreate(int k) 
    {
        
        MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    
        obj->a=(int*)malloc(sizeof(int)*(k+1));
        obj->k=k;
        obj->front=obj->rear=0;
        return obj;
    }
    
    bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
    {
        
        return obj->rear==obj->front;
    }
    
    bool myCircularQueueIsFull(MyCircularQueue* obj) 
    {
        
        return (obj->rear+1)%(obj->k+1)==obj->front;
    }
    //入队
    bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
    {
        
        if(myCircularQueueIsFull(obj))
            return false;
            obj->a[obj->rear++]=value;
            obj->rear%=(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];
    }
    
    int myCircularQueueRear(MyCircularQueue* obj) 
    {
        
        if(myCircularQueueIsEmpty(obj))
            return -1;
    
            return obj->a[(obj->rear-1+obj->k+1)%(obj->k+1)];
    }
    
    void myCircularQueueFree(MyCircularQueue* obj) 
    {
        
        free(obj->a);
        free(obj);
    }

这里我们只要关注这几点，其他的都很好实现：

**空的情况：**  
![在这里插入图片描述][08f34b9cd629422e9c1f2540d586106e.png]  
**满的情况：**  
![在这里插入图片描述][887bb7d447824e41a878add2758a9c34.png]  
  在这里我们学到了如何在数组里建立循环！那就是通过mod数组的长度，就可以使数组循环起来！

**找队尾：**  
![在这里插入图片描述][05460fae940a40eb8ae446185f49f12a.png]  
  尾部其实就是rear的后面一个元素，即**rear-1**，但是当**rear等于0**的时候，**-1就会导致越界**。对一个正数加a模a，得到的值不变。对于rear=0的时候进行这个操作就会避免越界的情况。

## 例题2：[用队列实现栈][Link 4] ##

![在这里插入图片描述][1fb7ed4bf2c94b88859792a673892d71.png]  
  要通过队列表示栈就要熟知他们两个各自的性质。栈是有“先进后出”的特点，队列有“先进先出的特点”，**综合她两的特点，我们通过以下方法来实现数据的出入：**  
![在这里插入图片描述][50db7a89ee3d4c03b253d273708c9bc8.png]

1.  保持**一个队列为空**，**一个队列存数据**
2.  **出栈的时候把前面的数据导入空队列**，将**最后一个数据**pop出去。

具体实现：（队列的代码之前写过，就不展示了，详细：[栈与队列][Link 5]）

void QueueInit(Queue* pq);
    void QueueDestroy(Queue* pq);
    void QueuePush(Queue* pq, QDatatype x);
    void QueuePop(Queue* pq);
    int QueueSize(Queue* pq);
    bool QueueEmpty(Queue* pq);
    QDatatype QueueFront(Queue* pq);
    QDatatype QueueBack(Queue* pq);
    
    typedef int QDatatype;
    
    typedef struct QueueNode
    {
        
    	struct QueueNode* next;
    	QDatatype data;
    }QNode;
    
    typedef struct Queue
    {
        
    	QNode* head;
    	QNode* tail;
    	int size;
    }Queue;
    
    
    typedef struct 
    {
        
        Queue q1;
        Queue q2;
    } MyStack;
    
    
    MyStack* myStackCreate() 
    {
        
        MyStack*ptr=(MyStack*)malloc(sizeof(MyStack));
        if(ptr==NULL)
        {
        
            perror("malloc::fail");
            return 0;
        }
        QueueInit(&ptr->q1);
        QueueInit(&ptr->q2);
    
        return ptr;
    }
    
    void myStackPush(MyStack* obj, int x) 
    {
        
        if(!QueueEmpty(&obj->q1))
        {
        
            QueuePush(&obj->q1,x);
        }
        else
        {
        
            QueuePush(&obj->q2,x);
        }
    }
    
    int myStackPop(MyStack* obj) 
    {
        
        Queue*emptyQ=&obj->q1;
        Queue *noneQ=&obj->q2;
        if(!QueueEmpty(emptyQ))
        {
        
            emptyQ=&obj->q2;
            noneQ=&obj->q1;
        }
        while(QueueSize(noneQ)>1)
        {
        
            QueuePush(emptyQ,QueueFront(noneQ));
            QueuePop(noneQ);
        }
        int top=QueueBack(noneQ);
        QueuePop(noneQ);
    
        return top;
    }
    
    int myStackTop(MyStack* obj) 
    {
        
        if(!QueueEmpty(&obj->q1))
        {
        
            return QueueBack(&obj->q1);
        }
        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);
    }

## 例题3：[用栈实现队列][Link 6] ##

![在这里插入图片描述][bc273f41833141f4aed1c9c08ef68411.png]

将一个栈当作输入栈，用于压入 push传入的数据；另一个栈当作输出栈，用于 pop 和peek 操作。

每次 pop 或 peek时，**若输出栈为空**则将**输入栈的全部数据依次弹出并压入输出栈**，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

![在这里插入图片描述][b5620436d73148c68e47c13d7237d684.png]  
**具体代码实现**：

typedef int STDataType;
    typedef struct Stack
    {
        
    	STDataType* a;
    	int top; // 栈顶
    	int capacity; // 容量
    }Stack;
    // 初始化栈
    void StackInit(Stack* ps);
    // 入栈
    void StackPush(Stack* ps, STDataType data);
    // 出栈
    void StackPop(Stack* ps);
    // 获取栈顶元素
    STDataType StackTop(Stack* ps);
    // 获取栈中有效元素个数
    int StackSize(Stack* ps);
    // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
    bool empty(Stack* ps);
    // 销毁栈
    void StackDestroy(Stack* ps);
    typedef struct 
    {
        
        Stack pushST;
        Stack popST;
    } MyQueue;
    
    int myQueuePeek(MyQueue* obj) ;
    MyQueue* myQueueCreate() 
    {
        
        MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
        if(obj==NULL)
        {
        
            perror("malloc::fail");
            return 0;
        }
        StackInit(&obj->pushST);
        StackInit(&obj->popST);
    
        return obj;
    }
    
    void myQueuePush(MyQueue* obj, int x) 
    {
        
        assert(obj);
        StackPush(&obj->pushST,x);
    }
    
    int myQueuePop(MyQueue* obj) 
    {
        
       int top=myQueuePeek(obj);
       StackPop(&obj->popST);
       return top;
    }
    
    int myQueuePeek(MyQueue* obj) 
    {
        
        if(empty(&obj->popST))
        {
        
            while(!empty(&obj->pushST))
            {
        
                StackPush(&obj->popST,StackTop(&obj->pushST));
                StackPop(&obj->pushST);
            }
        }
        return StackTop(&obj->popST);
    }
    
    bool myQueueEmpty(MyQueue* obj) 
    {
        
        return empty(&obj->pushST)&&empty(&obj->popST);
    }
    
    void myQueueFree(MyQueue* obj) {
        
        StackDestroy(&obj->pushST);
        StackDestroy(&obj->popST);
    
        free(obj);
    }

## 例题4：[括号匹配问题][Link 7] ##

![在这里插入图片描述][5e53af8d2e984d8e87950e9bb49270bf.png]  
我们遍历给定的字符串 s。当我们遇到一个左括号时，我们会期望在后续的遍历中，**有一个相同类型的右括号将其闭合**。由于**后遇到的左括号要先闭合**，因此我们可以将这个**左括号放入栈顶**。

当我们遇到一个右括号时，我们需要将一个相同类型的左括号闭合。此时，我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。**如果不是相同的类型**，或者栈中**并没有左括号**，**那么字符串 s 无效**，返回 False。

在遍历结束后，如果栈中没有左括号，说明我们将字符串 s中的所有左括号闭合，返回 True，否则返回 False。

注意到有效字符串的长度一定为偶数，因此**如果字符串的长度为奇数**，我们可以直接返回 False ，省去后续的遍历判断过程。  
![在这里插入图片描述][8b937757581640c7b446f9b13dd7b3e4.gif_pic_center]

**完整代码：**  
![在这里插入图片描述][5bc0633321694cb59da45c03c0a9d2e0.png]

## 总结 ##

这就是栈和队列的相关oj题，你学会了吗？  
  更新不易，辛苦各位小伙伴们动动小手，?三连走一走?? ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

> **专栏订阅：**  
> [每日一题][Link 8]  
> [c语言学习][c]  
> [算法][Link 9]  
> [智力题][Link 10]  
> [初阶数据结构][Link 1]  
> 更新不易，辛苦各位小伙伴们动动小手，?三连走一走?? ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

![在这里插入图片描述][55270e2552774a17a711aa978da84193.gif_pic_center]

[6ac7346dc5944908b5dd227e55fab217.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/60b7e1236946455a90d6e3d0fa394518.gif
[Link 1]: https://blog.csdn.net/qq_74310471/category_12216969.html?spm=1001.2014.3001.5482
[Link 2]: https://blog.csdn.net/qq_74310471?spm=1000.2115.3001.5343
[VS2022_C]: https://gitee.com/zhangxuruihhhh/c-language-learning
[85d8f838a7524c8bb8bed80b7ac059c1.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/a7b55ce328f84a1f99ad9daed4c6adc1.gif
[Link 3]: https://leetcode.cn/problems/design-circular-queue/
[5e0d23d7c837457d8acf5458e72556cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/fd5101b05a334691886c93b08ccdaad6.png
[2049ed103dbc4abbb2388e27e2e8fd1a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/ab2cb25f93e147639068a3d02c86408f.png
[913812518cb24b899f489ec1895bf35b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/05c0c2467fd940a9879c311ad53d9c39.png
[3e2d468c015f428cb5dc43bbf578ea02.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/9441a1f1a84c4657b6451324b484ac24.png
[44da4207a2cc4c898f265889b6b7b5f1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/32370adb112f450d8370b5e066182020.png
[08f34b9cd629422e9c1f2540d586106e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/0bdb969ff74545198fbefc88a54442e1.png
[887bb7d447824e41a878add2758a9c34.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/538314dabbed40e691ee8a0d103d535c.png
[05460fae940a40eb8ae446185f49f12a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/4eead3b439274bd0ab337f3eb25f271d.png
[Link 4]: https://leetcode.cn/problems/implement-stack-using-queues/
[1fb7ed4bf2c94b88859792a673892d71.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/32aa5d0c2e164791b9b17b341ed67743.png
[50db7a89ee3d4c03b253d273708c9bc8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/cabd7aa10904498bbbf7a76137fb48b8.png
[Link 5]: https://blog.csdn.net/qq_74310471/article/details/129772808?spm=1001.2014.3001.5501
[Link 6]: https://leetcode.cn/problems/implement-queue-using-stacks/
[bc273f41833141f4aed1c9c08ef68411.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/d99817fcaa974c699102fb2b2f91586e.png
[b5620436d73148c68e47c13d7237d684.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/c006fff0ede34177ad20d5312ab1f017.png
[Link 7]: https://leetcode.cn/problems/valid-parentheses/
[5e53af8d2e984d8e87950e9bb49270bf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/e9c9e71447dd458f965a451cba94d11c.png
[8b937757581640c7b446f9b13dd7b3e4.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/c86e90cbd1e94777a7c71fede98a6e92.gif
[5bc0633321694cb59da45c03c0a9d2e0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/118a59b01e214228a6d0cb15cdd7314e.png
[Link 8]: https://blog.csdn.net/qq_74310471/category_12166401.html?spm=1001.2014.3001.5482
[c]: https://blog.csdn.net/qq_74310471/category_12157207.html?spm=1001.2014.3001.5482
[Link 9]: https://blog.csdn.net/qq_74310471/category_12144452.html?spm=1001.2014.3001.5482
[Link 10]: https://blog.csdn.net/qq_74310471/category_12166402.html
[55270e2552774a17a711aa978da84193.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/8eda9764e17543709c013c81319918e2.gif