栈和队列刷题 Leetcode.22523220【C语言实现】

声明：由于C的局限性，以下OJ题所用到的接口(如Init、Pop、Push等)都需要自己实现，详情请看C语言实现栈和队列

1. 有效的括号

思路：利用栈的结构特性：先进后出。

假设输入()[]{}

1. 将所有的左括号压入栈中(([{)
2. 剩下的右括号与离它最近的左括号匹配。如何匹配？——出栈

• 函数调用的接口是自己实现的，唯一需要改动的是数据类型typedef char STDataType; 此处体现了类型重命名的好处。
• 匹配前注意判空
• 注意字符串的迭代

bool isValid(char * s){
    struct Stack st;
    StackInit(&st);

    while(*s)
    {
        if(*s == '[' || *s == '(' || *s == '{')
        {
            StackPush(&st, *s);//压栈
            s++;//字符串迭代
        }
        else
        {
            if(StackEmpty(&st))//前面无括号
            {
                StackDestroy(&st);
                return false;
            }
            else
            {
                char top = StackTop(&st);//得到栈顶元素
                if((top == '[' && *s != ']')//不匹配的情况
                || (top == '(' && *s != ')')
                || (top == '{' && *s != '}'))
                {
                    StackDestroy(&st);
                    return false;
                }
                else//剩下的是匹配的情况
                {
                    StackPop(&st);//出栈，下次循环开始得到下一个元素
                    s++;//字符串迭代
                }
            }
        }
    }
		//如果栈中都匹配完了，就不会剩下括号
    bool ret = StackEmpty(&st);//改接口判断栈是否为空
    StackDestroy(&st);
    return ret;
}

2. 用队列实现栈

思路：用队列实现栈，实际上就是用先进先出实现先进后出的效果。可以用两个队列来实现。

• 入数据：往非空的队列入数据
• 出数据：将最后一个元素之前的所有元素放到另一个空队列中，然后把剩下的一个返回后删除
  

2.1 结构的定义

用队列实现栈，MyStack这个结构就要用两个队列作为成员

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

2.2 队列的初始化和销毁

要先为结构体（队列）开辟空间，然后再初始化两个队列

MyStack* myStackCreate() {
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);

    return pst;
}

注意free的顺序，从结构体内到外

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

2.3 模拟入栈

用入队模拟入栈。

• 注意入队的是非空队列

void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1, x);
    }
    else
    {
        QueuePush(&obj->q2, x);
    }
}

2.4 模拟出栈

假设入栈的是1、2、3、4，出栈第一个数据是4

首先假设空的是q1，非空是q2，如果事实相反，则用条件判断反置

然后将非空队列的前size-1个(要调用size接口)放到空的队列，边放边删除(这样才能放下一个)。

放完以后把剩下的那一个没放的删掉。但是这个数据(4)就是要出栈的数据，所以要用一个变量保存它并 返回，这样就达到了出栈的效果。

int myStackPop(MyStack* obj) {
		//假设
    Queue* pEmpty = &obj->q1;
    Queue* pNonEmpty = &obj->q2;
    if(!QueueEmpty(&obj->q1))//如果假设不成立，反置赋值语句
    {
        pEmpty = &obj->q2;
        pNonEmpty = &obj->q1;
    }

    while(QueueSize(pNonEmpty) > 1)//留下最后一个要出栈的数据
    {
				//将数据放到空队列中
        QueuePush(pEmpty, QueueFront(pNonEmpty));
				//边放边删除非空队列的数据
        QueuePop(pNonEmpty);
    }
		//在删除最后一个要出栈的数据之前保存并返回它
    int front = QueueFront(pNonEmpty);
    QueuePop(pNonEmpty);

    return front;
}

2.5 模拟获取栈顶数据

队列一定是一个为空，一个非空，将非空队列中的队尾数据返回

例如1、2、3、4，栈顶数据为4，它处于队尾

int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

2.6 判空

因为模拟的栈中是两个队列，所以两个队列都要判断

bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

3. 用栈实现队列

思路：

思路和上一题类似，同样是用两个栈(先进后出)模拟实现队列(先进先出)。不同的是，两个栈各自的功能不同，一个只出栈，一个只入栈。

ps：这里的思路有点像反转字符串。每次出栈都是调换一次顺序，出两次栈就抵消了。

3.1 结构的定义

用栈模拟实现队列，需要连续出栈两次，所以要定义两个栈

typedef struct {
    Stack pushSt;
    Stack popSt;
} MyQueue;

3.2 栈的初始化和销毁

首先要为队列开辟空间，然后初始化栈

MyQueue* myQueueCreate() {
    MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&q->pushSt);
    StackInit(&q->popSt);

    return q;
}

销毁注意顺序

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->pushSt);
    StackDestroy(&obj->popSt);
    free(obj);
}

3.3 判空

判断队列是否为空，即判断两个栈是否为空

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->pushSt) && StackEmpty(&obj->popSt);
}

3.4 压栈

直接压入即可

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

3.5 获取栈顶元素

• 要把非空的pushST的所有元素放到空的popST中，注意判断条件
• 在把pushST元素放入popST中后，记得删除该元素
• 最后才是返回popST的栈顶元素

int myQueuePeek(MyQueue* obj) {
    if(StackEmpty(&obj->popSt))
    {
        while(!StackEmpty(&obj->pushSt))
        {
            StackPush(&obj->popSt, StackTop(&obj->pushSt));
            StackPop(&obj->pushSt);
        }
    }

    return StackTop(&obj->popSt);
}

3.6 出栈

边出栈，边删除，用top保存popST的栈顶元素并返回

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

4. 设计循环队列

详见循环队列

---

日志

4/23/2022