手撕数据结构算法OJ——栈和队列

一、前言

兄弟们，今天的你们还在学习吗？快快跟随up的脚步，让up和大家一起长脑子吧！俗话说得好：一日学一日功，一日不学十日空。好啦言归正传，前面up已经给大家讲解完了栈和队列这两个数据结构，不知道你有没有把它们吃透呢？今天呢咱们就来手撕与之相关的算法OJ题。

二、手撕OJ

2.1有效的括号

力扣20题 有效的括号链接

条件限制：
1、只能有这三种括号( ) 、[ ]、{ }
2、左括号必须用相同类型的右括号闭合
3、左括号必须以正确的顺序闭合
4、每个右括号都有一个对应的相同类型的左括号
画图展示（用栈解决）：
注意阅图顺序：先从左往右，在从上往下。




注意：因为此题是用栈来实现，关于栈的各功能up在上一次已经给大家书写过一次了，所以这里我们就直接复制粘贴。（如有疑问请查看上一节分享）
代码展示：

typedef char STDataType;
typedef struct Stack
{STDataType* arr;int top;int capacity;
}ST;
void StackInit(ST* ps)//栈初始化
{assert(ps);ps->arr = NULL;ps->top = 0;ps->capacity;
}
void StackPush(ST* ps,STDataType x)//入栈
{assert(ps);if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType));if (tmp == NULL){printf("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;}ps->arr[ps->top++] = x;
}
bool Stackempty(ST* ps)//判空
{assert(ps);return ps->top == 0;
}
void StackPop(ST* ps)//出栈
{assert(!Stackempty(ps));--ps->top;
}
STDataType StackFront(ST* ps)//取栈顶
{assert(!Stackempty(ps));return ps->arr[ps->top - 1];
}
int StackSIze(ST* ps)//有效个数
{assert(ps);return ps->top;
}
void StackDestroy(ST* ps)//销毁
{assert(ps);if (ps->arr){free(ps->arr);}ps->arr = NULL;ps->top = 0;ps->capacity = 0;
}
//.......................以上为栈的各功能实现代码
bool isValid(char* s) {ST st;StackInit(&st);char* pi = s;while(*pi!='\0'){if(*pi == '(' || * pi == '[' || *pi =='{'){StackPush(&st,*pi);}else{if(Stackempty(&st)){StackDestroy(&st);return false;}char top = StackFront(&st);if((top == '(' && *pi != ')')||(top == '[' && *pi != ']')||(top == '{' && *pi != '}')){StackDestroy(&st);return false;}StackPop(&st);}pi++;}bool ret = Stackempty(&st) ? true : false;StackDestroy(&st);return ret;
}

思路：定义一个pi从第一个括号开始,若pi为左括号则直接进栈，如果没有左括号只有右括号则注定无法匹配，return false;待遇到右括号就与栈顶的左括号进行匹配，如果没有右括号或者匹配不成功直接返回false,若匹配成功就出栈，继续用下一个右括号与栈顶进行匹配，当pi走到空并且栈中也没有元素的时候，说明全部括号匹配成功，return true.

提交通过：

2.2用队列实现栈

力扣225 用队列实现栈链接

2.2.1初始化

代码展示：

MyStack* myStackCreate() {//初始化MyStack* pst = (MyStack*)malloc(sizeof(MyStack));QueueInit(&pst->q1);QueueInit(&pst->q2);return pst;
}

2.2.2入栈

画图展示：

思路：找到不为空的队列，把要进行入栈操作的元素直接入队即可。

代码展示：

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

2.2.3出栈

画图展示：

思路：找到不为空的队列，把队列的前size-1个元素入队到另外一个空队列中，待原先不为空的队列只剩一个元素的时候，把最后一个元素保存直接出栈掉即可，再反复进行以上操作，直到一 一出栈。

代码展示：

int myStackPop(MyStack* obj) {//出栈Queue* emp = &obj->q1;Queue* noneEmp = &obj->q2;if(Queueempty(&obj->q2)){emp = &obj->q2;noneEmp = &obj->q1;}while(QueueSize(noneEmp)>1){QueuePush(emp,QueueFront(noneEmp));QueuePop(noneEmp);}int top = QueueFront(noneEmp);QueuePop(noneEmp);return top;
}

2.2.4取栈顶

画图展示：

思路：直接返回不为空的队列中的队尾元素即为所需要的栈顶元素。
代码展示：

int myStackTop(MyStack* obj) {//取栈顶if(!Queueempty(&obj->q1)){return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}

2.2.5判空

思路：当队列1和队列2同时都不为空则栈不为空，反之有一个为空则栈为空。

代码展示：

bool myStackEmpty(MyStack* obj) {//判空return Queueempty(&obj->q1) && Queueempty(&obj->q2);
}

2.2.6销毁

思路：把队列1和队列2销毁掉，再把存放这两个队列的空间释放掉，最后再置为空即可。

代码展示：

void myStackFree(MyStack* obj) {//销毁QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);obj = NULL;
}

2.2.7整体代码

注意：队列的实现是直接复制粘贴上一节的代码。

typedef int QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QueueNode;
typedef struct Queue
{QueueNode* phead;QueueNode* ptail;
}Queue;
void QueueInit(Queue* pq)//初始化
{assert(pq);pq->phead = NULL;pq->ptail = NULL;
}
void QueuePush(Queue* pq,QDataType x)//入队
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){printf("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = pq->ptail->next;}
}
bool Queueempty(Queue* pq)//判空
{assert(pq);return pq->phead == NULL;
}
void QueuePop(Queue* pq)//出队
{assert(!Queueempty(pq));if (pq->phead == pq->ptail){free(pq->phead);pq->phead = NULL;}else{QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}
}
QDataType QueueFront(Queue* pq)//取队头
{assert(!Queueempty(pq));return pq->phead->data;
}
QDataType QueueBack(Queue* pq)//取队尾
{assert(!Queueempty(pq));return pq->ptail->data;
}
int QueueSize(Queue* pq)//有效个数
{assert(pq);QueueNode* pcur = pq->phead;int size = 0;while (pcur){size++;pcur = pcur->next;}return size;
}
void QueueDestroy(Queue* pq)//销毁
{assert(pq);QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = NULL;pq->ptail = NULL;
}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) {if(!Queueempty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}int myStackPop(MyStack* obj) {Queue* emp = &obj->q1;Queue* noneEmp = &obj->q2;if(Queueempty(&obj->q2)){emp = &obj->q2;noneEmp = &obj->q1;}while(QueueSize(noneEmp)>1){QueuePush(emp,QueueFront(noneEmp));QueuePop(noneEmp);}int top = QueueFront(noneEmp);QueuePop(noneEmp);return top;
}int myStackTop(MyStack* obj) {if(!Queueempty(&obj->q1)){return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}bool myStackEmpty(MyStack* obj) {return Queueempty(&obj->q1) && Queueempty(&obj->q2);
}void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);obj = NULL;
}

提交通过：

2.3用栈实现队列

力扣232 用栈实现队列链接

2.3.1初始化

代码展示：

MyQueue* myQueueCreate() {//初始化MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));StackInit(&pq->pushST);StackInit(&pq->popST);return pq;
}

2.3.2入队

画图展示：

思路：直接把要入队的元素入栈即可。

代码展示：

void myQueuePush(MyQueue* obj, int x) {//入队StackPush(&obj->pushST,x);
}

2.3.3出队

画图展示：

思路：把原来不为空的栈中的元素依次入栈到另外一个空栈中，此时原先的空栈的栈顶元素就是要出队的元素，直接把队头出队即可

代码展示：

int myQueuePop(MyQueue* obj) {//出队if(Stackempty(&obj->popST)){while(!Stackempty(&obj->pushST)){StackPush(&obj->popST,StackFront(&obj->pushST));StackPop(&obj->pushST);}}int top = StackFront(&obj->popST);StackPop(&obj->popST);return top;
}

2.3.4取队头

画图展示：

思路：把原来不为空的栈中的元素依次入栈到另外一个空栈中，此时原先的空栈的栈顶元素就是队头。

代码展示：

int myQueuePeek(MyQueue* obj) {//取队头if(Stackempty(&obj->popST)){while(!Stackempty(&obj->pushST)){StackPush(&obj->popST,StackFront(&obj->pushST));StackPop(&obj->pushST);}}return StackFront(&obj->popST);
}

2.3.5判空

思路：两个栈同时不为空即队列不为空，反之有一个栈为空则队列为空。

代码展示：

bool myQueueEmpty(MyQueue* obj) {//判空return Stackempty(&obj->pushST) && Stackempty(&obj->popST);
}

2.3.6销毁

思路：把两个栈销毁掉，再把存放这两个栈的空间释放掉，最后再置为空即可。

代码展示：

void myQueueFree(MyQueue* obj) {//销毁StackDestroy(&obj->pushST);StackDestroy(&obj->popST);free(obj);obj = NULL;
}

2.3.7整体代码

注意：栈的各功能实现是直接复制粘贴上一节的代码。

typedef int STDataType;
typedef struct Stack
{STDataType* arr;int top;int capacity;
}ST;
void StackInit(ST* ps)//栈初始化
{assert(ps);ps->arr = NULL;ps->top = 0;ps->capacity = 0;
}
void StackPush(ST* ps,STDataType x)//入栈
{assert(ps);if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType));if (tmp == NULL){printf("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;}ps->arr[ps->top++] = x;
}
bool Stackempty(ST* ps)//判空
{assert(ps);return ps->top == 0;
}
void StackPop(ST* ps)//出栈
{assert(!Stackempty(ps));--ps->top;
}
STDataType StackFront(ST* ps)//取栈顶
{assert(!Stackempty(ps));return ps->arr[ps->top - 1];
}
int StackSIze(ST* ps)//有效个数
{assert(ps);return ps->top;
}
void StackDestroy(ST* ps)//销毁
{assert(ps);if (ps->arr){free(ps->arr);}ps->arr = NULL;ps->top = 0;ps->capacity = 0;
}typedef struct {ST pushST;ST popST;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));StackInit(&pq->pushST);StackInit(&pq->popST);return pq;
}void myQueuePush(MyQueue* obj, int x) {StackPush(&obj->pushST,x);
}int myQueuePop(MyQueue* obj) {if(Stackempty(&obj->popST)){while(!Stackempty(&obj->pushST)){StackPush(&obj->popST,StackFront(&obj->pushST));StackPop(&obj->pushST);}}int top = StackFront(&obj->popST);StackPop(&obj->popST);return top;
}int myQueuePeek(MyQueue* obj) {if(Stackempty(&obj->popST)){while(!Stackempty(&obj->pushST)){StackPush(&obj->popST,StackFront(&obj->pushST));StackPop(&obj->pushST);}}return StackFront(&obj->popST);
}bool myQueueEmpty(MyQueue* obj) {return Stackempty(&obj->pushST) && Stackempty(&obj->popST);
}void myQueueFree(MyQueue* obj) {StackDestroy(&obj->pushST);StackDestroy(&obj->popST);free(obj);obj = NULL;
}

提交通过：

四、总结

宝子们，怎么样？是否被这三道OJ题震撼到了呢？相信你在看完up的分析之后，可能会感慨——原来栈和队列还能这么用,真NB。不过震撼归震撼，下来还是得深入理解。up期待大家更上一层楼。

这世界上，最富有的人是跌倒最多的人；最勇敢的人是每次跌倒都能站起来的人；最成功的人是那些每次跌倒，不单能站起来，还能够坚持走下去的人