栈和队列专题（LeetCode）

有效的括号

在这里插入图片描述

题解

左括号从s字符串中取出来放入栈中
s中就只有右括号了
那么栈顶的左括号和s的右括号匹配即可
代码中也详细解释了左括号和右括号多少的问题

代码加解释

bool isValid(char* s) 
{Stack sl;StackInit(&sl);while(*s){//先插入左括号if(*s == '('||*s == '{'||*s == '['){StackPush(&sl,*s);}else//右括号取栈顶左括号尝试匹配{if(STEmpty(&sl)){//解决右括号比左括号多的情况//s中只有右括号，top == 0StackDestroy(&sl);//释放sl指向的空间return false;}//取栈顶数据char top = STTop(&sl);//把栈顶的括号取出来和右括号匹配StackPop(&sl);//弹出栈顶数据，方便取下一个数据//不匹配if(top == '('&& *s != ')'||top == '['&&*s != ']'||top == '{'&&*s != '}'){StackDestroy(&sl);return false;}}s++;}//栈不为空，左括号的数量比右括号的数量多，数量不匹配//只有一个左括号,假//解决的是右括号和左括号一样多和左括号多的情况bool ret = STEmpty(&sl);//栈为空，top == 0，真StackDestroy(&sl);return ret; 
}

用队列实现栈

请你仅使用两个队列实现一个后入先出（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（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：
[“MyStack”, “push”, “push”, “top”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示：

1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空

进阶：你能否仅用一个队列来实现栈。

题解

实现各个接口，用两个队列实现栈
主体思路还是保证一个队列是空的，一个队列是非空的
空的队列用于导数据，比如非空队列 1 2 3 4,1 2 3导到空的队列中，4直接pop,对应栈顶的删除
非空的队列直接插入数据，因为队列是尾插，也就是栈顶的插入
在这里插入图片描述
MyStack下有一个重要的说明
1.后取地址，相当于开了一个新的队列，在新的队列中许多值是未定义的，相当于随机值，所以不能后取地址

2.先取地址，是对原队列进行操作，指针指向原队列
在这里插入图片描述

代码加解释

//C语言要造轮子，前面的接口在上一个博客，需要的可以自取
typedef struct 
{Queue q;//队列1Queue p;//队列2
} MyStack;MyStack* myStackCreate() 
{//一个队列为空，另一个队列为有数据//把数据插入非空队列中，空的队列用来导数据MyStack* obj = (MyStack*)malloc(sizeof(MyStack));//不能和题里创建一样的指针，重定义QueueInit(&(obj->p));QueueInit(&(obj->q));//初始化队列1和队列2return obj;
}void myStackPush(MyStack* obj, int x) 
{if(!QueueEmpty(&(obj->p))){QueuePush(&(obj->p),x);//第一个队列是非空的就插入第一个队列中}   else//1.p空q非空，插入队列q 2.p空q空，这种随便插入那个队列{QueuePush(&(obj->q),x);}
}int myStackPop(MyStack* obj) 
{//你不知道q,p那个队列是空，所以要假设//用空队列导一下//假设法，假设队列p为非空，队列q为空Queue* Noempty = &(obj->p);Queue* Empty = &(obj->q);if(!QueueEmpty(&(obj->q))){Empty = &(obj->p);Noempty = &(obj->q);}   while(QueueSize(Noempty) > 1){QueuePush(Empty, QueueTop(Noempty));QueuePop(Noempty);//卡在这个地方，把对头数据取出来，然后头删，再尾插入空的队列}int top = QueueTop(Noempty);QueuePop(Noempty); //把栈顶数据取出来，返回栈顶数据//再删掉最后的栈顶数据    return top;
}int myStackTop(MyStack* obj) 
{if(!QueueEmpty(&(obj->q))){return QueueTail(&(obj->q));}  else{return QueueTail(&(obj->p));}
}bool myStackEmpty(MyStack* obj) 
{return QueueEmpty(&(obj->q)) && QueueEmpty(&(obj->p));    
}void myStackFree(MyStack* obj) 
{QueueDestroy(&(obj->q));QueueDestroy(&(obj->p));free(obj);    
}/**  * Your MyStack struct will be instantiated and called as such:* MyStack* obj = myStackCreate();* myStackPush(obj, x);* int param_2 = myStackPop(obj);* int param_3 = myStackTop(obj);* bool param_4 = myStackEmpty(obj);* myStackFree(obj);*/

设计循环队列

在这里插入图片描述

题解

主要多开一个空间为了解决假溢出问题
代码里也有写

队列为空 -> head == tail
在这里插入图片描述

队列为满 -> （tail+1）% （k+1） == head
%k+1 为了解决回绕问题
普通的情况tail + 1 = head
在这里插入图片描述

插入数据 -> (obj->tail) %= (obj->k+1);
tail++ 变成5又要解决回绕问题，%k+1回到0位置可以插入数据
删除数据 -> obj->head %= (obj->k+1)
head++ 变成5又要解决回绕问题，%k+1回到0位置可以删除数据
取队头数据 -> obj->a[obj->head]
head指向头直接取队头数据
取队尾数据 ->
1.return obj->a[(obj->tail-1 + obj->k+1) % (obj->k+1)]
2.return obj->tail == 0 ? obj->a[obj->k] : obj->a[obj->tail-1]

tail是指向队尾的下一个位置
取队尾数据要tail - 1，但是tail == 0时，tail - 1就会越界，
tail == 0时要回绕到 tail == k 是队尾数据的下标

有两种方法可以理解第二种比较好理解
第一种取一个数据也比较好理解
比如tail = 0,k = 4 时，-1+5 = 4 % k+1 = 4,就取到队尾的下标了

代码加解释

typedef struct 
{int* a;int head;//指向头int tail;//指向尾int k;     
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) 
{MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->a = (int*)malloc(sizeof(int)*(k+1));//多开一个空间，为了解决循环队列的假溢出问题//假溢出问题：比如开四个空间，head == tail是空，head == tail也是满obj->head = 0;obj->tail = 0;    obj->k = k;return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{return obj->head == obj->tail;    
}bool myCircularQueueIsFull(MyCircularQueue* obj)  
{// tail + 1 == head;return (obj->tail+1) % (obj->k+1) == obj->head;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{if(myCircularQueueIsFull(obj)){return false;}obj->a[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)
{if(myCircularQueueIsEmpty(obj)){return -1;}return obj->a[obj->head];
}int myCircularQueueRear(MyCircularQueue* obj) 
{if(myCircularQueueIsEmpty(obj)){return -1;}return obj->a[(obj->tail-1 + obj->k+1) % (obj->k+1)];//return obj->tail == 0 ? obj->a[obj->k] : obj->a[obj->tail-1];
}void myCircularQueueFree(MyCircularQueue* obj) 
{free(obj->a);//先把数组释放，再把结构体释放free(obj);
}/*** Your MyCircularQueue struct will be instantiated and called as such:* MyCircularQueue* obj = myCircularQueueCreate(k);* bool param_1 = myCircularQueueEnQueue(obj, value);* bool param_2 = myCircularQueueDeQueue(obj);* int param_3 = myCircularQueueFront(obj);* int param_4 = myCircularQueueRear(obj);* bool param_5 = myCircularQueueIsEmpty(obj);* bool param_6 = myCircularQueueIsFull(obj);* myCircularQueueFree(obj);
*/

用栈实现队列

在这里插入图片描述

题解

设计一个为poplist的栈和pushlist的栈
一个栈专门插入数据
一个栈专门删除数据
StackPush(&(obj->pushlist),x)
直接入栈达到了先进的效果
将pushlist中的数据导入poplist中，先进的数据就达到先出的效果了
poplist中有数据直接出
没有数据从pushlist中导数据在出数据
所以两个栈只要有一个栈是非空的就可以出数据
只要有一个栈是非空的，就是非空队列
在这里插入图片描述

代码加解释

typedef struct 
{Stack pushlist;Stack poplist;//后进先出栈实现先进先出队列
} MyQueue;MyQueue* myQueueCreate() 
{MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));StackInit(&(obj->pushlist));StackInit(&(obj->poplist));return obj;
}void myQueuePush(MyQueue* obj, int x) 
{//直接插入pushlist的队列，队尾入数据也就是栈顶入数据StackPush(&(obj->pushlist),x);
}int myQueuePop(MyQueue* obj) 
{int front = myQueuePeek(obj);//push pop//传过去的应该是obj，指向两个栈的结构体指针StackPop(&(obj->poplist));return front;
}int myQueuePeek(MyQueue* obj) 
{if(STEmpty(&(obj->poplist))){while(!STEmpty(&(obj->pushlist))){StackPush(&(obj->poplist),STTop(&(obj->pushlist)));StackPop(&(obj->pushlist));}}int ret = STTop(&(obj->poplist));return ret;
}bool myQueueEmpty(MyQueue* obj) 
{return STEmpty(&(obj->pushlist)) && STEmpty(&(obj->poplist));    
}void myQueueFree(MyQueue* obj) 
{StackDestroy(&(obj->pushlist));StackDestroy(&(obj->poplist));free(obj);
}/*** Your MyQueue struct will be instantiated and called as such:* MyQueue* obj = myQueueCreate();* myQueuePush(obj, x);* int param_2 = myQueuePop(obj);* int param_3 = myQueuePeek(obj);* bool param_4 = myQueueEmpty(obj);* myQueueFree(obj);
*/