栈和队列经典练习题

前言：

一、括号匹配问题

1.题目描述

2.解题思路

3.题目链接

二、用队列实现栈

1.题目描述

2.解题思路

3.题目链接

三、用栈实现队列

1.题目描述

2.题目分析

3.题目链接

四、设计循环队列

1.题目描述

2. 题目分析

3.题目链接

最后

前言：

前面已经为大家讲解了栈和队列的概念以及如何实现，接下来本博主为大家整理了几道题目，帮助大家更好的理解栈和队列，请大家看完本文后不要忘记练习哦。

一、括号匹配问题

1.题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

2.解题思路

大家在看到此题时，相信会有以下思路：既然要解决括号匹配，那么，我用一个变量left来记录左括号的数量，用变量right来记录右括号的数量，咋一听似乎是可行的，那么，我们使用如下的代码经行测试。

bool isValid(char* s) {
    int left = 0;
    int right = 0;
    while(*s)
    {
        if(*s == '(' || *s == '{' || *s == '[')
        {
            left++;
        }
        if(*s == ')' || *s == '}' || *s == ']')
        {
            right++;
        }
        s++;
    }
    if(right == left)
    {
        return true;
    }
    else
    {
        return false;
    }
}

结果如下：

很显然官方也知道我们会有这样的想法，提前准备好用例来隔绝此种可能。那么，我们就束手无策了吗？当然不能，坐以待毙不是我们的风格，对吧？

我们之前学习过了栈，那么，这道题我们用栈来考虑一下：

我们首先开辟一个栈用来放左括号，当有右括号要来匹配时，我们拿出最后入栈的左括号与之匹配，若能匹配成功，就继续比较下一组，若不行就反回false。

这个思路明显可行，那我们就来实现一下吧！

bool isValid(char* s) {
    Stack st;
    StackInit(&st);
    while(*s)
    {
        if(*s == '(' || *s == '[' || *s == '{')
        {
            StackPush(&st,*s);
        }
        else
        {
            int top = StackTop(&st);
            StackPop(&st);
            if(top == '(' && *s != ')'|| top == '{' && *s != '}' || top == '[' && *s != ']')
            {
                return false;
            }
        }
        s++;
    }
    return true;
}

使用以上代码进行测试，至于栈的底层实现，相信大家都很乐意当CV工程师（手动dogo）。这样写，测试用例也可以通过，但提交会失败。

这是为什么呢？大家这时把这个带入到代码中试一下，我们会发现无右括号与之匹配，那么，我们怎么处理比较好？我们可不可以在最后去判空一下，因为有右括号在时，我们才会进行Pop，这时又来个问题，如果只有右括号，没左括号，那还是true，对吧。所以，我们也应该在else那经行判空。这次思路代码如下：

bool isValid(char* s) {
    Stack st;
    StackInit(&st);
    while(*s)
    {
        if(*s == '(' || *s == '[' || *s == '{')
        {
            StackPush(&st,*s);
        }
        else
        {
            if(StackEmpty(&st))
            {
                return false;
            }
            int top = StackTop(&st);
            StackPop(&st);
            if(top == '(' && *s != ')'|| top == '{' && *s != '}' || top == '[' && *s != ']')
            {
                return false;
            }
        }
        s++;
    }
    bool ret = StackEmpty(&st);
    StackDestroy(&st);
    return ret;
}

这次的提交不就通过了，所以，我们今后写代码一定要考虑周全。

3.题目链接

. - 力扣（LeetCode）

二、用队列实现栈

1.题目描述

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

2.解题思路

题目要求使用队列来实现栈，首先，我们都明白队列和栈的特点。队列：先进先出。栈：先进后出。那么使用两个队列来实现栈，就要使用其特性来进行实现。这里，给大家说一说思路：

代码实现思路如下：

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;

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);
    }
}int myStackPop(MyStack* obj) {
    Queue* empty = &obj->q1;
    Queue* nonempty = &obj->q2;
    if (!QueueEmpty(&obj->q1))
    {
        nonempty = &obj->q1;
        empty = &obj->q2;
    }
    while (QueueSize(nonempty) > 1)
    {
        QueuePush(empty, QueueFront(nonempty));
        QueuePop(nonempty);
    }
    int tmp = QueueFront(nonempty);
    QueuePop(nonempty);
    return tmp;
}

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);
}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

对于底层代码大家若是想练习敲一遍即可，如果熟悉了即可成为CV工程师。

3.题目链接

. - 力扣（LeetCode）

三、用栈实现队列

1.题目描述

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

2.题目分析

此题与上题类似，都是互相实现对方的题目。此类题目都要求我们掌握其特性以及都对其底层代码都能熟练掌握。话不多说，我们来分析一下此题，大家都可以思考一下，此题大致思路与上题类似。

代码实现思路如下：

typedef struct {
    Stack p1;
    Stack p2;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* pst = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&pst->p1);
    StackInit(&pst->p2);
    return pst;
}

void myQueuePush(MyQueue* obj, int x) {
   StackPush(&obj->p1,x);
}

int myQueuePop(MyQueue* obj) {
    int front = myQueuePeek(obj);
    StackPop(&obj->p2);
    return front;
}

int myQueuePeek(MyQueue* obj) {
   if(StackEmpty(&obj->p2))
   {
        while(!StackEmpty(&obj->p1))
        {
            int top = StackTop(&obj->p1);
            StackPop(&obj->p1);
            StackPush(&obj->p2,top);
        }
   }
   return StackTop(&obj->p2);
}

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->p1) && StackEmpty(&obj->p2);
}

void myQueueFree(MyQueue* obj) {
    StackDestory(&obj->p1);
    StackDestory(&obj->p2);
    free(obj);
}

3.题目链接

. - 力扣（LeetCode）

四、设计循环队列

在开始说此题前，先简单对大家解释一下什么为循环队列。

大家，可这样理解：相信大家对循环链表不陌生（博主之前讲解链表习题时说过）。那么，大家可以把链表换成数组想象一下即可。

当我们简单知道了这是一个什么东西后，我们一定要明白的知识点为：如何判断此时的链表是空还是满？

如何断定是空？相信大家有办法即：因为要记录其头地址和尾地址，在开始时，使头地址和尾地址指向一致，此时该队列为空。

那么？如何判断该队列为满的情况呢？相信有人说：使头（head）和尾（tatil）一致即可。可是，咱们不是规定为空吗？这不就矛盾了吗？别慌，我将介绍两种方法供大家参考使用。

法一：设一个size常量。刚开始使之为0，数组长度为k，若size % k == 0，认为队列满了。相信此方法大家都能理解。

法二：多开辟一个一个空间，注意：此空间不放元素。判断队列满了的条件为：（tail+1）%k + 1 == head。大家可画图理解都不难。（常用法二）

此处，教大家一个计算队列元素的方法：（ tail-head+size（MAX）） %size（MAX）。可帮助大家解决选择题。

好了，我们一起来看看题目吧！

1.题目描述

设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。

2. 题目分析

此题考查循环队列，其实就是上面我给大家说的知识，此题难点为：如何删除元素以及获取尾元素。

删除元素：使head++，然后确定其下标即可。操作很简单，该如何理解呢？

获取尾元素：有人说，这个简单取tail--的值即可，是不错。那要是tail此时指向头呢？估计会有人说：不可能，绝对不可能。怎么不可能呢？别忘了，这可是循环队列,都有可能。

为了应对这种情况可以用这种写法:(tail-1+k+1) % (k+1) 。这个是常规写法,既然有常规,那肯定还有不常规了,不常规也可以称之为:装逼写法。只要你一键三连便可解锁,即:(tail+k) %(k+1) 。这时,有人说了:就这?也没啥吗?你们这样想,如果没上面的写法,你能看懂这种写法吗?都看到这了,记得承诺哦。

难点已解决,接下来,展示本题代码:

typedef struct {
    int* a;
    int head;
    int ptail;
    int k;
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a = (int*)malloc(sizeof(int) * (k + 1));
    obj->head = obj->ptail = 0;
    obj->k = k;
    return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj)) {
        return false;
    }
    obj->a[obj->ptail] = value;
    obj->ptail++;
    obj->ptail %= (obj->k + 1);

    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) {
        return false;
    }
        ++obj->head;
        obj->head %= (obj->k + 1);
        return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) {
        return -1;
    } else {
        return obj->a[obj->head];
    }
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) {
        return -1;
    } else {
        return obj->a[(obj->ptail + obj->k ) %( obj->k + 1)];
    }
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->head == obj->ptail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->ptail + 1) % (obj->k + 1) == obj->head;
}
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}