手撕数据结构算法OJ——栈和队列
文章目录
- 一、前言
- 二、手撕OJ
- 2.1有效的括号
- 2.2用队列实现栈
- 2.2.1初始化
- 2.2.2入栈
- 2.2.3出栈
- 2.2.4取栈顶
- 2.2.5判空
- 2.2.6销毁
- 2.2.7整体代码
- 2.3用栈实现队列
- 2.3.1初始化
- 2.3.2入队
- 2.3.3出队
- 2.3.4取队头
- 2.3.5判空
- 2.3.6销毁
- 2.3.7整体代码
- 四、总结
一、前言
兄弟们,今天的你们还在学习吗?快快跟随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期待大家更上一层楼。
这世界上,最富有的人是跌倒最多的人;最勇敢的人是每次跌倒都能站起来的人;最成功的人是那些每次跌倒,不单能站起来,还能够坚持走下去的人