数据结构习题——有效的括号（栈），栈与队列和互相实现，循环队列的实现

前言

继上篇博客学习了栈与队列之后，今天我们来尝试着使用他们来写一些题目，话不多说，启动启动启动

1、有效的括号

习题链接：有效的括号

题目

思路

本题给定一个字符串，然后要在指定的条件下判断字符串是否有效
简而言之就是括号要对应起来且类型相同，不多不少刚刚好。
想到昨天学习的栈，先进后出的规则，可以用到这里
遇到左括号入栈，遇到右括号就和栈顶元素匹配
如果最后栈内还有元素，或者遍历字符串途中遇到括号不匹配直接返回false

代码

class Solution 
{
public:
    bool isValid(string s) 
    {
        char stack[10000];    //  定义一个字符数组，简易代表栈   
        int top = -1;
        for(int i = 0; s[i] !='\0'; ++i)    //  循环遍历字符串
        {
            char cur = s[i];
            if(cur == '(' || cur == '[' || cur == '{')    //  遇到左括号就入栈  
            {
                stack[++top] = cur;
            }
            else
            {
                if(top == -1)    //  如果遇到右括号   栈内无元素  ，直接返回false  
                {
                    return false;
                }
                char topcur = stack[top--];       //  取栈顶元素  
                if((topcur == '(' && cur != ')') || (topcur == '[' && cur != ']') || (topcur == '{' && cur != '}'))
                return false;    //   列出不匹配的情况  
            }
        }
        return top == -1;
    }
};

在上一篇的栈的具体学习过后，这个题目相对而言还是简单的，就是对栈的特殊结构的使用

2、用队列实现栈

习题链接：用队列实现栈

题目

思路

本题是仅且使用两个队列去实现一个先进后出的栈
要知道我们的队列是符合先进先出的特殊规则，要怎么才能实现栈呢?
我想到栈分为入栈和出栈还有取栈顶元素三个功能，我用一个队列来实现入栈，另外一个队列来实现出栈

上图


图片解析下，思路清晰明了
入栈就插入不为空的队列，出栈就把队列元素移动到空队列，只留下一个数据出队列就好了，取栈顶元素直接取不为空队列队尾元素即可。两个队列反复横跳。

小编这里还有另外一种思路，因为今天想偷一点小懒，使用stl库中的队列，这样就不用自己手写一个队列了。
一个队列作为主要队列，一个队列作为辅助队列，每次入栈插入辅助队列，然后把主要队列的元素一一插入辅助队列，这个时候，队头元素就是刚刚插入的数据，出栈就直接出队头元素即可，取队头元素也是一样的道理。

代码

class MyStack 
{
public:
    queue<int> q1;    //   本题偷了一点小懒   使用了stl库中的队列  它拥有昨天实现的队列的所有功能
    queue<int> q2;    //   q1为主要队列   q2为辅助队列  
    MyStack() {}
    void push(int x)    //  入栈  
    {
        q2.push(x);     // 将元素先push到  q2中   
        while(!q1.empty())     // q1不为空    
        {  
            q2.push(q1.front());      //  把q1队内的元素放入q2  
            q1.pop();				//  放入之后  q1 pop  
        }
        swap(q1,q2);    //  这个时候q1 是为空的  交换q1  q2  这个时候q1 的队头就是刚刚插入的数据   
    }
    int pop() 
    {
        int x = q1.front();   //  出栈操作   
        q1.pop();
        return x;
    }
    int top()     //  取栈顶元素   
    {
        return q1.front();
    }
    bool empty() 
    {
        return q1.empty();    
    }
};

每次插入都对队列进行一顿操作，相当于是给队列反过来变成栈了。
也是稳稳拿下了。

3、用栈实现对列

习题链接：用栈实现队列

题目

思路

有了上一题用队列实现栈的操作，想必也能想到用栈实现队列也大相径庭，就是用两个栈去把一个栈的特殊结构改变一下
也是构造两个栈，一个主要栈，一个辅助栈，每次入队就直接入辅助栈，等要出队列时，如果主要栈为空就把辅助栈的元素全部出栈，然后入到主要栈，这样元素顺序就颠倒了，也就是主要栈出栈就变成了出队。

代码

class MyQueue 
{
public:
    stack<int> s1;   //  构造主要栈和辅助栈  
    stack<int> s2;   
    MyQueue() {}  
    void push(int x) 
    {
        s1.push(x);   //  每次数据入队  入辅助栈  
    }
    int pop()    //  当要出队时  
    {
        if(s2.empty())   //  若此时主要栈为空  也就是意味着主要栈的元素已经全部出队了  
        {
            while(!s1.empty())   //   这个时候把辅助栈的元素出栈再入主要栈  主要栈的出栈顺序就是队列的出队顺序了  
            {
                s2.push(s1.top());
                s1.pop();
            }
        }
        int ans = s2.top();   //   如果主要栈还不为空   直接出栈即可  
        s2.pop();
        return ans;
    }
    int peek()    //   获取队头元素   
    {
        int ans = this->pop();   //  可以直接出队列  保存元素  再入栈  
        s2.push(ans);
        return ans;
    }
    bool empty() 
    {
        return s1.empty()&&s2.empty();   //  当连个栈都为空时  队列也为空  
    }
};

当对栈和队列的特性理解的深刻一点的时候，栈和队列的相互实现想想也是挺简单的，拿下拿下

4、设计循环队列

4.1循环队列的概念和了解

循环队列，环形队列⾸尾相连成环，环形队列可以使⽤数组实现，也可以使⽤循环链表实现

队列满的情况下，为什么 Q.rear 不存储数据？
为了能使⽤ Q.rear = Q.front 来区别是队空还是队满，我们常常认为出现上图b时的情况即为队满的情况
此时： rear+1=front

在用数组实现循环队列时，需要注意一点的是：当队列空间需要n个时，数组需要开n+1个容量
为什么呢？如果我现在只是按照队列的元素开指定个数组的空间 想想当队列为空的条件是什么 应该是 front == rear 吧 那当队列为满的情况呢 是不是也是 front == rear 这个时候就冲突了 ，不知道队列什么时候是空什么时候是满
所以我们这里是用数组的时候，开辟队列指定元素个数 n + 1个 。



上述图片数组开辟了 n+1和空间，这个时候队列为空和队列满的情况就不冲突了。需要注意的是在判断队列满的情况需要
（rear+1）%（capacity+1） ==front 我来解释一下 ：数组此时容量是n+1，所以有一个空间是不储存数据的，也就是rear，当rear的下一个元素为front时，队列为满，这里%上容量大小是因为怕rear+1越界。

至于用链表实现循环队列，就是单向带头循环链表，相信大家已经滚瓜烂熟了，接下来，上题

习题链接：设计循环队列

题目

思路

本题就是设计一个循环队列，刚才已经带着大家把循环队列的概念已经了解透彻啦。
这里小编在写题就直接用c++啦，stl容器用起来还是很方便的，不要怕看不懂，我的注释是很详细的
话不多说，上代码

代码

class MyCircularQueue 
{
public:
    int front,rear,capacity;
    vector<int> arr;    //  这里类似于顺序表  开辟一个数组  arr
    MyCircularQueue(int k) 
    {
        capacity = k + 1;     //  定义capacity  为k + 1
        arr.assign(capacity,0);   //   这里类似于  给数组初始化全部为  0
        front = rear = 0;    //  然后  front  和   rear   都从数组下标0 开始 
    }    
 	bool isFull()     //  判断循环队列是否为满   
    {
        return (rear + 1) % capacity == front;   //  前面已经详细解释过啦   
    }
    bool enQueue(int value)     //  向循环队列插入元素   插入成功返回真  
    {
        if(isFull())    //  先判断队列是否为满   
        {
            return false;
        }
        arr[rear] = value;    //   不满就在  rear位置   插入数据即可  
        rear = (rear + 1) % capacity;   //  rear位置插入后  需要往后移动一步  这里还是要取模防止数组越界  
        return true;
    }
    
    bool isEmpty()    //  判断循环队列是否为空   
    {
        return front == rear;    //  直接返回判断条件    
    }
    
    bool deQueue()       //  向循环队列中删除一个元素   
    {
        if(isEmpty())    
        return false;
        front = (front + 1) % capacity;   //  如果队列不为空，直接让 front  往前走一步就好了   
        return true;
    }
    int Front()      //  获取队首元素    
    {
        if(isEmpty())    
        return -1;
        return arr[front];    //   队列不为空就直接返回   front位置对应的元素       
    }
    int Rear()     //  获取队尾元素   
    {
        if(isEmpty())
        return -1;
        return arr[(rear - 1 + capacity) % capacity];  //  因为rear位置是空缺不存储数据的 
        								//   所以要返回rear的前一个数据同时要防止数组越界的情况   
    }
};

到这里，循环队列的实现就结束啦，不出意外，还是拿下了。

总结

通过今天的习题，对栈和队列的理解更加深刻，同时也能熟练运用栈和队列，去互相实现还是挺有意思的
同时在写题的过程中不止对知识的掌握更加深刻，也让我学习到了新的知识——循环队列，还是挺有意思的。
好啦，栈和队列的内容就到这里啦，下一篇博客小编将为大家讲述新的知识
另外，有什么写的不好的或者不详细的还请大家指出来，谢谢大家

最后的最后，感谢大家能看到这里，我也是平平无奇的一枚在慢慢学习中的小趴菜，分享自己的学习经历，同时也能复习自己所学的知识。 小编持续跟新中…

芷兰生于深林，不以无人而不芳
每一行代码都是迈向更好的牛奶和面包的一步，加油加油加油