LeetCode_栈和队列相关OJ

 

✨✨所属专栏：LeetCode刷题专栏✨✨

✨✨作者主页：嶔某✨✨

上一篇：数据结构_栈和队列(Stack & Queue)-CSDN博客 

 有效的括号

解析:

这里我们用数组实现的栈来解决这个问题，在有了栈的几个基础接口之后，我们运用这几个接口解决问题。

首先新建一个栈并初始化，进入循环如果当前指针指向的字符元素为左括号 {([ 就入栈，反之就出栈，之后判断指针指向的字符是否和出栈的字符左右括号相匹配。

(  (top == '{'&& *s != '}')  ||  (top == '['&& *s != ']')  ||  (top == '('&& *s !=')')  )

 每次循环后s++，如果 *s != '\0' 就进行下一次循环。

写完后提交会发现当只有一个元素的时候这种写法是不能过的

 这里我们在else里面做一个判空，因为如果进了else里面，就说明这是个右括号，那么栈里面一定有其所对应的左括号，如果这时后栈为空，那么显然括号之间是不匹配的。这样就很好的解决了诸如此类的问题。

if(STEmpty(&S))
{
        STDestroy(&S);
        return false;

}

最后s遇到了 '\0' 循环结束，我们判断栈是否为空，如果为空返回true，否则栈中还有元素括号之间也是不匹配的。

return STEmpty(&S);

 可以这么理解这两段代码：一个判断了左括号是否多了，一个判断了右括号是否多了。

 示例代码：

 function/数据结构_栈 · 钦某/c-language-learning - 码云 - 开源中国 (gitee.com)https://gitee.com/wang-qin928/c-language-learning/tree/master/function/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_%E6%A0%88

bool isValid(char* s)
{
    ST S;
    STInit(&S);
    while(*s)
    {
        if(*s == '{' || *s == '[' || *s == '(')
        {
            STPush(&S,*s);
        }
        else
        {
            if(STEmpty(&S))
            {
                STDestroy(&S);
                return false;
            }
            char top = STTop(&S);
            STPop(&S);
 
            if((top == '{'&& *s != '}')||
            (top == '['&& *s != ']') ||
            (top == '('&& *s !=')'))
            {
                STDestroy(&S);
                return false;               
            }
        }
        s++;
    }
    return STEmpty(&S);
}

 用队列实现栈

解析：

这里我们使用数组实现的队列，只需要创建两个队列，把数据在两个队列之间互相导就行了。

定义结构体MyStack：

将mystack结构体里面创建两个队列q1、q2。

myStackCreate函数：

malloc出结构体pst的内存空间 ，并将q1、q2交给 QueueInit函数，返回这个结构体。

myStackPush函数：

将数据方放进 QueuePush，入队列q1就行。

myStackPop函数：

将q1队列的数据转到q2里面，最后剩一个数据不转，直接删除，之后再将数据从q2转到q1里面。返回删除的那个数据。

myStackTop函数：

和上一个函数一样，只不过myStackTop不删除数据，直接返回就好了。

myStackEmpty函数：

return !QueueSize(&(obj->q1));

 myStackFree函数：

这里一定要先释放q1、q2的空间之后再释放pst。

示例代码：

function/队列 · 钦某/c-language-learning - 码云 - 开源中国 (gitee.com)https://gitee.com/wang-qin928/c-language-learning/tree/master/function/%E9%98%9F%E5%88%97

 
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) {
    QueuePush(&(obj->q1),x);
}
 
int myStackPop(MyStack* obj) {
    while(QueueSize(&(obj->q1)) != 1)
    {
        QueuePush(&(obj->q2),QueueFront(&(obj->q1)));
        QueuePop(&(obj->q1));
    }
    int tmp = QueueFront(&(obj->q1));
    QueuePop(&(obj->q1));
    while(QueueSize(&(obj->q2)))
    {
        QueuePush(&(obj->q1),QueueFront(&(obj->q2)));
        QueuePop(&(obj->q2));
    }
    return tmp;
}
 
int myStackTop(MyStack* obj) {
    return QueueBack(&(obj->q1));
}
 
bool myStackEmpty(MyStack* obj) {
    return !QueueSize(&(obj->q1));
}
 
void myStackFree(MyStack* obj) {
    Destory(&(obj->q1));
    Destory(&(obj->q2));
    free(obj);
}

 用栈实现队列

解析：

此题与上题思路差不多，有一些细节上的改变，我们在代码里面细说。

定义结构体MyQueue：

创建两个栈st1、st2

myQueueCreate函数：

为MyQueue结构体malloc一块空间，将里面的st1、st2交给 STInit函数。

myQueuePush函数：

直接利用STPush函数插入就行。

myQueuePeek函数：

这里判断一下，如果st2为空的话，就将st1的数据转到st2来，取栈顶元素返回（转过来的时候数据会反过来）如果st2不为空，就直接返回st2栈顶元素。

myQueuePop函数：

这里本来也是要进行判断、转数据的，但是我们可以简化一下代码，直接调用myQueuePeek返回值存起来，这样st2必然就有数据，我们就可以直接pop掉st2里面的数据。

myQueueEmpty函数：

只有st1、st2同时为空，这个队列才为空。

myQueueFree函数：

先用 STDestroy释放掉st1、st2的空间，之后再free掉obj。

总结：此题目不用将st2的数据再转回到st1里，相当于st2是专门用来出数据的，st1专门用来入数据的。

示例代码：

function/数据结构_栈 · 钦某/c-language-learning - 码云 - 开源中国 (gitee.com)https://gitee.com/wang-qin928/c-language-learning/tree/master/function/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_%E6%A0%88

typedef struct {
    ST st1;
    ST st2;
} MyQueue;
 
MyQueue* myQueueCreate() {
    MyQueue* Q = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&(Q->st1));
    STInit(&(Q->st2));
    return Q;
}
 
void myQueuePush(MyQueue* obj, int x) {
    STPush(&(obj->st1),x);
}
 
int myQueuePop(MyQueue* obj) {
    int tmp = myQueuePeek(obj);
    STPop(&(obj->st2));
    return tmp;
}
 
int myQueuePeek(MyQueue* obj) {
    if(STEmpty(&(obj->st2)))
    {
        while(!STEmpty(&(obj->st1)))
        {
            STPush(&(obj->st2),STTop(&(obj->st1)));
            STPop(&(obj->st1));
        }
        return STTop(&(obj->st2));
    }
    else
    {
        return STTop(&(obj->st2));
    }
}
 
bool myQueueEmpty(MyQueue* obj) {
    return (STEmpty(&(obj->st1)) && STEmpty(&(obj->st2)));
}
 
void myQueueFree(MyQueue* obj) {
    STDestroy(&(obj->st1));
    STDestroy(&(obj->st2));
    free(obj);
}

设计循环队列 

解析：

用数组实现，多开辟一块空间，防止假溢出。或多定义一个size元素记录数组元素个数。主要都是为了解决判空和判满的问题。

定义MyCircularQueue结构体：

一个int*指针、一个head、一个tail、一个k表示队列容量。

myCircularQueueCreate函数：

为MyCircularQueue建立空间，并为data建立空间，其他值：obj->head = obj->tail = 0，obj->k = k。

myCircularQueueIsEmpty函数：

如果obj->head == obj->tail就为空，返回true，反之返回false。

myCircularQueueIsFull函数：

如果obj->head == (obj->tail+1)%(obj->k+1)就为满，返回true，反之返回false。

myCircularQueueEnQueue函数：

先判断是否为满，之后再往里面插入数据。注意这里tail的变化:

(obj->tail) %= (obj->k+1);

myCircularQueueDeQueue函数：

先判断是否为空，之后再删除数据。注意head的变化：

 (obj->head) %= (obj->k+1);

myCircularQueueFront函数：

return myCircularQueueIsEmpty(obj)?-1:obj->data[obj->head];

myCircularQueueRear函数：

return myCircularQueueIsEmpty(obj)?-1:obj->data[(obj->tail+obj->k)%(obj->k+1)];

注意这里tail+1后可能回超出范围，所以我们要在这里模上(k+1)。

myCircularQueueFree函数：

先free掉obj->data,之后free掉obj。

总结：

我们要时刻注意，tail和head的范围，不能超过k，否则就应该模上(k+1)。其次这道题用单链表写会麻烦很多，因为不好处理循环的问题。如果你用双向循环链表，当我没说……（我们要用最少的消耗，干最多的事儿！）

示例代码：

typedef struct {
    int *data;
    int head;
    int tail;
    int k;
} MyCircularQueue;
 
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* CQ = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    CQ->data = (int*)malloc(sizeof(int)*(k+1));//data需另外开辟空间
    CQ->head = 0;
    CQ->tail = 0;
    CQ->k = k;
    return CQ;
}
 
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->head == obj->tail;
}
 
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->tail+1) % (obj->k + 1) == obj->head;
}
 
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
        return false;
 
    obj->data[obj->tail] = value;
    obj->tail++;
    (obj->tail) %= (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) {
    return myCircularQueueIsEmpty(obj)?-1:obj->data[obj->head];
}
 
int myCircularQueueRear(MyCircularQueue* obj) {
    return myCircularQueueIsEmpty(obj)?-1:obj->data[(obj->tail+obj->k)%(obj->k+1)];
}
 
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->data);
    free(obj);
}

本期博客到这里就结束了，如果有什么错误，欢迎指出，如果对你有帮助，请点个赞，谢谢！