目录
1. 有效的括号
思路：
2.用队列实现栈
思路：
3.用栈实现队列
思路：
4.设计循环队列
思路：
1. 有效的括号
20. 有效的括号 - 力扣（LeetCode）
给定一个只包括
'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
思路：
左右括号匹配，有两个需要考虑的点；
1.括号顺序问题；
2.括号数量问题；
1.括号顺序问题：括号都有对应的左右边，出现这样的 ({)} 就是错误的；只有相应的左括号会有对应的右括号在旁边；
栈：先进后出；一组括号，先比较的是最后输入的左括号；所以栈满足此功能；
队列：先进先出；最先输入的左括号应该是与最后输入的右括号比较，所以队列不满足此功能；
2.括号顺序问题： 即使右括号都满足了左括号，会有残留问题，比如右括号多些，而此时空间已经为空；
我们构建一个栈的基本功能 ；【数据结构】——栈|队列（基本功能）-CSDN博客
// 支持动态增长的栈
typedef char STDataType;
typedef struct Stack
{
STDataType* arr;
int top; // 栈顶
int capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps)
{
assert(ps);
assert(ps);
ps->arr = NULL;
ps->capacity = 0;
ps->top = -1; //表示栈顶元素
}
// 入栈
void StackPush(Stack* ps, STDataType data)
{
//检查容量
if (ps->top + 1 == ps->capacity) //top表示的是栈顶元素，先++top,再插入的，所以检查+1位置是否可用
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* newnode = (STDataType*)realloc(ps->arr,sizeof(STDataType) * newcapacity);
assert(newnode); //七匹狼式检查是否开辟成功
ps->arr = newnode;
ps->capacity = newcapacity;
}
ps->top++;
ps->arr[ps->top] = data;
}
// 出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->top >= 0);
ps->top--;
}
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top >= 0);
return ps->arr[ps->top];
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(Stack* ps)
{
assert(ps);
if (ps->top < 0) //为空
{
return true;
}
else
{
return false;
}
}
// 销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
ps->capacity = 0;
ps->top = -1;
free(ps->arr);
ps->arr = NULL;
}
当括号字符串 所有左括号都存储进栈中，当遇到右括号就开始逐个和栈顶括号比较；
这里在于比较时，因为比较后还需要继续比较，所以采取找到不符合的条件跳出循环；
在字符串循环结束后，要检查是否栈为空
bool isValid(char* s) {
Stack ps;
StackInit(&ps);
while(*s)
{
//左括号入栈
if(*s == '(' || *s == '{' || *s == '[')
{
StackPush(&ps,*s);
}
//右括号与栈顶比较
else
{
//检查是否数量匹配,检查栈是否还有元素,为空返回非0
if(StackEmpty(&ps))
{
StackDestroy(&ps);
return false;
}
//左右括号比较,不相等返回fasle
char tmp = StackTop(&ps);
StackPop(&ps); //移除栈顶元素
if((tmp != '(' && *s == ')')
||( tmp != '{' && *s == '}')
|| (tmp != '[' && *s == ']'))
{
StackDestroy(&ps);
return false;
}
}
++s;
}
bool tmp = StackEmpty(&ps);
StackDestroy(&ps);
return tmp;
}2.用队列实现栈
225. 用队列实现栈 - 力扣（LeetCode）
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（
push、top、pop和empty）。实现
MyStack类：
void push(int x)将元素 x 压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的，返回true；否则，返回false。
思路：
栈是先进后出的结构，而队列是先进先出的；
两个队列，数据存储到队列1中后，按照先进先出的结构，将size(元数个数)-1移动到队列2中，再输出队列1的话，就实现了栈的结构，先进后出；
可以总结为：如果要输入元素，就输入到空队列中
//将元素X压入栈顶
void myStackPush(MyStack* obj, int x) {
if(!QueueEmpty(&obj->q1)) //为空返回非0，取反
{
QueuePush(&obj->q1,x);
}
else
{
QueuePush(&obj->q2,x);
}
}如何找到栈顶元素呢，我们可以将不为空的队列中 size(有效元素个数)-1个 数据移动到空队列中，再输出原不为空的队列；
我们采取假设法，找到不为空的队列，假设某一队列为empty，另外一个队列为noempty；然后if条件判断假设；
//移除并返回栈顶元素
int myStackPop(MyStack* obj) {
//将size-1个元素移动到 另一个空队列中
//假设q1队列为空，q2不为空
Queue* empty = &obj->q1;
Queue* noempty = &obj->q2;
//验证假设
if(!QueueEmpty(&obj->q1))
{
empty = &obj->q2;
noempty = &obj->q1;
}
//将size-1个元素 移动到空队列中
while(QueueSize(noempty)>1)
{
QueuePush(empty,QueueFront(noempty));
QueuePop(noempty);
}
int top = QueueFront(noempty); //此刻该队列仅有需要的数据
QueuePop(noempty);
return top;
}这两个是这道题较为麻烦的函数，另外的函数需求因为较为简单，我就直接码上讲解；
且这段代码是这道题一半的代码，另外一般就是队列的基本功能实现代码，可以去【数据结构】——栈|队列（基本功能）-CSDN博客获取完整的代码，复制过来即可；
注：这里释放内存是由里往外，因为结构定义了多重
MyStack* myStackCreate() {
MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
QueueInit(&pst->q1);
QueueInit(&pst->q2);
return pst;
}
//将元素X压入栈顶
void myStackPush(MyStack* obj, int x) {
if(!QueueEmpty(&obj->q1)) //为空返回非0，取反
{
QueuePush(&obj->q1,x);
}
else
{
QueuePush(&obj->q2,x);
}
}
//移除并返回栈顶元素
int myStackPop(MyStack* obj) {
//将size-1个元素移动到 另一个空队列中
//假设q1队列为空，q2不为空
Queue* empty = &obj->q1;
Queue* noempty = &obj->q2;
//验证假设
if(!QueueEmpty(&obj->q1))
{
empty = &obj->q2;
noempty = &obj->q1;
}
while(QueueSize(noempty)>1)
{
QueuePush(empty,QueueFront(noempty));
QueuePop(noempty);
}
int top = QueueFront(noempty);
QueuePop(noempty);
return top;
}
//返回栈顶元素
int myStackTop(MyStack* obj) {
if(!QueueEmpty(&obj->q1)) //为空返回非0，取反
{
return QueueBack(&obj->q1);
}
else
{
return QueueBack(&obj->q2);
}
}
//如果栈是空，返回true，非空 返回fasle
bool myStackEmpty(MyStack* obj) {
if(QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2)) //表示为空
{
return true;
}
else
return false;
}
void myStackFree(MyStack* obj) { //注意释放顺序
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
}
3.用栈实现队列
232. 用栈实现队列 - 力扣（LeetCode）
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（
push、pop、peek、empty）：实现
MyQueue类：
void push(int x)将元素 x 推到队列的末尾int pop()从队列的开头移除并返回元素int peek()返回队列开头的元素boolean empty()如果队列为空，返回true；否则，返回false
思路：
这道题和题2相似，要实现1先出去，就是先把入栈的元素全部移动到出栈中，就实现了队列的结构；
与之不同的是：这边需要把全部的数据移动到另一个栈；
可以定义两个栈为：
pushst栈：用来数据存放的栈；
popst栈： 用来输出数据的栈；
1.需要获得栈内数据时，先检查popst栈是否为空，如果不为空，返回该栈数据即刻；
2.如果为空，先将pushst栈数据导入到popst栈内，在进行返回popst栈数据
int myQueuePeek(MyQueue* obj) {
if(!STEmpty(&obj->popst)) //popst栈有数据 直接返回栈顶元素
{
return STTop(&obj->popst);
}
else
{
//先将数据导入到popst栈
while(!STEmpty(&obj->pushst))
{
STPush(&obj->popst,STTop(&obj->pushst));
STPop(&obj->pushst);
}
//返回栈顶元素
return STTop(&obj->popst);
}
}注：这里和题2一样，注意释放顺序
因为其他功能较为思路明了，解析过程会在代码中解释；
栈函数接口实现功能代码在【数据结构】——栈|队列（基本功能）-CSDN博客
MyQueue* myQueueCreate() {
MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
STInit(&obj->pushst);
STInit(&obj->popst);
return obj;
}
void myQueuePush(MyQueue* obj, int x) {
//数据进到pushst栈，
STPush(&obj->pushst,x);
}
int myQueuePop(MyQueue* obj) {
int front = myQueuePeek(obj);
STPop(&obj->popst);
return front;
}
int myQueuePeek(MyQueue* obj) {
if(!STEmpty(&obj->popst)) //popst栈有数据 直接返回栈顶元素
{
return STTop(&obj->popst);
}
else
{
//先将数据导入到popst栈
while(!STEmpty(&obj->pushst))
{
STPush(&obj->popst,STTop(&obj->pushst));
STPop(&obj->pushst);
}
//返回栈顶元素
return STTop(&obj->popst);
}
}
bool myQueueEmpty(MyQueue* obj) {
if(STEmpty(&obj->pushst) && STEmpty(&obj->popst))
{
return true;
}
else
return false;
}
void myQueueFree(MyQueue* obj) {
STDestrory(&obj->pushst);
STDestrory(&obj->popst);
free(obj);
}4.设计循环队列
622. 设计循环队列 - 力扣（LeetCode）
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
思路：
这里有两种数据结构可以选择：数组和链表；
链表对后续的操作比较方便，但是不好控制，而且构建的时候也极为麻烦；
如果用数组 需要考虑的是如何规避为满和为空的判断
采用数组的话，我们定义front，back；来进行判断循环点；
这里的问题就是如何规避 为满和为空的问题；
解决：1.可以定义一个size；在front == back的基础上，size == 0 就是空
size ！= 0就是满；
2. 可以多开辟一块空间；动态空间；
多开辟一块空间，这块空间是动态移动的，但是不存储数据；
当front == back时，就是空；
当 back+1 == front 就是满，
这里因为数组 如果在边界点的话 会导致越界，
所以采取取模来规范范围；也达到了循环的条件
这里需要注意的就是获取最后一个结点；
因为back是指向最后一个数据的下一个位置；如果back在边界 -1 有可能越界；
需要特殊处理规范这块；
取模的操作：如果该数大于本身，就不会有影响；
这里删除和增加一个数据，都有可能引起越界；所以在对back front操作后，都要规范范围；
取模实际空间大小
typedef struct {
int* parr; //动态开辟
int front; //头结点
int back; //指向尾结点的下一个
int size; //实际开辟的空间
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->parr = (int*)malloc(sizeof(int)*(k+1)); //多开辟一块空间
obj->front = 0;
obj->back = 0;
obj->size= k+1;
return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front == obj->back;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->back+1) % obj->size == obj->front; //满了返回真
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
//先判断是否满了
if(myCircularQueueIsFull(obj)) //满了返回真
return false;
obj->parr[obj->back] = value;
obj->back++;
obj->back %= obj->size;
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
//判断是否为空
if(myCircularQueueIsEmpty(obj))
return false;
obj->front++;
obj->front %= obj->size;
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return -1;
return obj->parr[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return -1;
return obj->parr[(obj->back-1 + obj->size) % obj->size];
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->parr);
free(obj);
}
![Electron[4] Electron最简单的打包实践](https://img-blog.csdnimg.cn/direct/1af744d223624f0faac86a65b536ef9f.png)
