目录

题目

序号 题目 链接
1 括号匹配问题 LeetCode
2 用队列实现栈 LeetCode
3 用栈实现队列 LeetCode
4 设计循环队列 LeetCode

1.括号匹配问题

栈和队列经典OJ#yyds干货盘点#_栈和队列

这个题目比较有意思的点在于可以用栈的方式进行实现，但是由于博主目前学习的数据结构主要是由c语言进行编写，所以在使用栈的时候需要引入栈的相关函数和一些结构体的定义。

题目的具体思路比较简单，将左括号放入堆栈，同时进行字符指针s++，如果遇到右括号则与栈顶的括号进行比较，如果不匹配，则为false，如果匹配则左括号出栈，接着重复步骤继续运行直至*s == '\0’时停止循环，如下：

栈和队列经典OJ#yyds干货盘点#_C语言_02

循环结束后，返回true，另外我们需要考虑字符串里的两种情况：

① “}}”：这种情况进入循环体的时候，栈为空，无法执行StackPush命令，所以进入循环体的时候需要使用StackEmpty函数来判断是否栈为空。

②"{{"：这种情况会导致出循环体的时候，栈不为空，所以直接返回true是错误的，出循环体的时候我们需要用if条件语句来判断*s是否为‘\0’，然后在使用StackEmpty函数即可。

代码如下：

bool isValid(char * s){
    Stack st;
    StackInit(&st);
    bool ret;
    while(*s != '\0')
    {
        if(*s == '[' || *s == '{' || *s == '(')
        {
            StackPush(&st, *s);
            s++;
        }
        else
        {
            if(StackEmpty(&st))
            {
                ret = false;
                break;
            }

            if(StackTop(&st) != '[' && *s == ']')
            {
                ret = false;
                break;
            }

            if(StackTop(&st) != '(' && *s == ')')
            {
                ret = false;
                break;
            }

            if(StackTop(&st) != '{' && *s == '}')
            {
                ret = false;
                break;
            }
            s++;
            StackPop(&st);
        }

    }
    if(*s == '\0')
        ret = StackEmpty(&st);
    StackDestroy(&st);
    return ret;
}

2.用队列实现栈

栈和队列经典OJ#yyds干货盘点#_栈和队列_03

同样需要c语言自己造一个轮子来实现队列。

这里提供的思路是用两个队列实现栈的功能，其中应用双队列的目的是为了解决出栈的问题，将非空队列的值导入空队列直至非空队列只剩队尾的时候，执行QueuePop（出队列）即可，如下：

栈和队列经典OJ#yyds干货盘点#_OJ_04

代码如下：

typedef struct {
    Queue _q1;
    Queue _q2;

} MyStack;

/** Initialize your data structure here. */

MyStack* myStackCreate() {
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->_q1);
    QueueInit(&pst->_q2);
    return pst;
}

/** Push element x onto stack. */
void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->_q1))
    {
        QueuePush(&obj->_q1, x);
    }
    else
    {
        QueuePush(&obj->_q2, x);
    }
}

/** Removes the element on top of the stack and returns that element. */
int myStackPop(MyStack* obj) {
    //注意生命周期的问题，所以定义成指针类型
    Queue *nonEmpty = &obj->_q1;
    Queue *empty = &obj->_q2;
    if(QueueEmpty(&obj->_q1))
    {
        empty = &obj->_q1;
        nonEmpty = &obj->_q2;
    }
    while(QueueSize(nonEmpty)>1)
    {
        QueuePush(empty,QueueFront(nonEmpty));
        QueuePop(nonEmpty);
    }
    int top = QueueFront(nonEmpty);
    QueuePop(nonEmpty);
    return top;
}

/** Get the top element. */
int myStackTop(MyStack* obj) {
    if(QueueEmpty(&obj->_q1))
    {
       return QueueBack(&obj->_q2);
    }
    else
    {
        return QueueBack(&obj->_q1);
    }
}

/** Returns whether the stack is empty. */
bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->_q1) && QueueEmpty(&obj->_q2);
}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->_q1);
    QueueDestroy(&obj->_q2);
    free(obj);
}