合肥做网站的企业,福州整站优化,visual studio网页界面设计,佛山网站建设联系创作不易#xff0c;感谢友友们三连#xff01;#xff01;
一、前言 栈和队列的相互实现是用两个栈去实现队列或者是用两个队列去实现栈#xff0c;这样其实是把问题复杂化的#xff0c;实际中没有什么应用价值#xff0c;但是通过他们的相互实现可以让我们更加深入地理… 创作不易感谢友友们三连
一、前言 栈和队列的相互实现是用两个栈去实现队列或者是用两个队列去实现栈这样其实是把问题复杂化的实际中没有什么应用价值但是通过他们的相互实现可以让我们更加深入地理解栈和队列的特点而我也是用两道相关的OJ题来分析这个过程 二、用两个队列实现栈
力扣队列实现栈 2.1 思路 2.2 代码实现
2.2.1 队列的代码
我们先把队列的实现声明放这
Queue.h
#includestdbool.h
#includeassert.h
typedef int QDatatype;//方便后面修改存储数据的数据类型
typedef struct QueueNode//队列结点的数据结构
{QDatatype data;//存储数据struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;//指向队头用于出队头删QNode* ptail;//指向队尾用于入队尾插int size;//记录有效元素个数
}Queue;//创建一个队列相关结构体
void QueueInit(Queue* pq);//队列的初始化
void QueuePush(Queue* pq, QDatatype x);//队列的入队尾插
void QueuePop(Queue* pq);//队列的出队(头删)
QDatatype QueueFront(Queue* pq);//获取队列头部元素
QDatatype QueueBack(Queue* pq);//获取队列尾部元素
int QueueSize(Queue* pq);//获取队列中有效元素个数
bool QueueEmpty(Queue* pq);//判断队列是否为空
void QueueDestory(Queue* pq);//队列的销毁
2.2.2 结构体的创建
封装一个myStack结构体管理两个队列
typedef struct MyStack
{Queue q1;Queue q2;
} MyStack;
//用两个队列实现栈构建一个结构体去管理这两个队列
2.2.3 初始化栈
初始化栈相当于先构建栈的结构体变量然后再初始化他的两个队列成员
MyStack* myStackCreate() //返回一个MySack类型的指针
{MyStack* obj (MyStack*)malloc(sizeof(MyStack));if (obj NULL){perror(malloc fail);exit(1);}
//如果开辟成功对栈初始化相当于对栈结构体中的两个队列初始化QueueInit(obj-q1);QueueInit(obj-q2);return obj;
}
2.2.4 模拟压栈
按照我们之前的思路压栈直接找到不为空的队列尾插就行
void myStackPush(MyStack* obj, int x)
//压栈前必须在不为空的队列中压栈
{if (!QueueEmpty(obj-q1))//如果q1不为空压q1QueuePush(obj-q1, x);else//如果q1为空则压q2QueuePush(obj-q2, x);
}
2.2.5 模拟出栈并返回栈顶元素
按照之前的思路出栈就是先找到非空的队列移除到空的队列上只留下最后一个元素再头删
int myStackPop(MyStack* obj)
//出栈必须找到不为空的队列然后将该队列的元素倒倒另一个队列中知道只剩最后一个元素的时候就删除
{//要找到不为空的队列进行操作所以先假设一个为空一个不为空如果给个条件判断Queue* Emptyq obj-q1;Queue* NonEmptyq obj-q2;if (!QueueEmpty(obj-q1))//错了的话就认个错然后换回来{NonEmptyq obj-q1;Emptyq obj-q2;}//开始导数据while (QueueSize(NonEmptyq) 1){//将队列头的元素倒进去另一个队列在出栈QueuePush(Emptyq, QueueFront(NonEmptyq));//压栈QueuePop(NonEmptyq);//倒入一个就将非空队列出队列一个}//倒完后只剩一个数据了先记录返回值再删除int top QueueFront(NonEmptyq);QueuePop(NonEmptyq);return top;
}
2.2.6 获取栈顶元素
找到不为空的队列然后获取队列尾的元素就是获取栈顶元素
int myStackTop(MyStack* obj)
//找到不为空的队列然后获取队列尾的元素相当于获取栈顶元素
{if (!QueueEmpty(obj-q1))//如果q1不为空取q1队尾return QueueBack(obj-q1);else//如果q2不为空取q2队尾return QueueBack(obj-q2);
}
2.2.7 判断栈是否为空
判断栈是否为空本质上就是判断两个队列是否为空
bool myStackEmpty(MyStack* obj) //栈为空当且仅当两个队列都为空
{return QueueEmpty(obj-q1) QueueEmpty(obj-q2);
}
2.2.8 释放栈
要先释放掉栈的队列成员的空间然后再释放栈的空间并置空
void myStackFree(MyStack* obj)
{//释放obj前一定也要将q1和q2的空间释放了QueueDestory(obj-q1);QueueDestory(obj-q2);free(obj);//obj NULL;没用一级指针接受指针相当于值传递//要手动在main函数中置空
}
值得注意的是这边给obj置空是没有的要想改变obj必须用二级指针所以我们最后要释放的话要在程序的最后自己手动释放。
2.3 全部代码
2.3.1 queue.h
#includestdlib.h
#includestdbool.h
#includeassert.h
typedef int QDatatype;//方便后面修改存储数据的数据类型
typedef struct QueueNode//队列结点的数据结构
{QDatatype data;//存储数据struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;//指向队头用于出队头删QNode* ptail;//指向队尾用于入队尾插int size;//记录有效元素个数
}Queue;//创建一个队列相关结构体
void QueueInit(Queue* pq);//队列的初始化
void QueuePush(Queue* pq, QDatatype x);//队列的入队尾插
void QueuePop(Queue* pq);//队列的出队(头删)
QDatatype QueueFront(Queue* pq);//获取队列头部元素
QDatatype QueueBack(Queue* pq);//获取队列尾部元素
int QueueSize(Queue* pq);//获取队列中有效元素个数
bool QueueEmpty(Queue* pq);//判断队列是否为空
void QueueDestory(Queue* pq);//队列的销毁
2.3.2 queue.c
#includeQueue.hvoid QueueInit(Queue* pq)
{assert(pq);//判断传的是不是空指针pq-phead pq-ptail NULL;pq-size 0;//因为队列不像栈一样有一个top表示栈顶元素的下标//所以如果我们想知道这个队列的有效数据个数就必须遍历队列//由于其先进先出的特性我们默认只能访问到头元素和尾元素//所以必须访问一个头元素就出队列一次这样才能实现遍历//但是这样的代价太大了为了方便我们直接用size
}
void QueuePush(Queue* pq, QDatatype x)
{assert(pq);//入队必须从队尾入QNode* newnode (QNode*)malloc(sizeof(QNode));//创建一个新节点if (newnode NULL)//如果新节点申请失败退出程序{perror(malloc fail);}//新节点创建成功给新节点初始化一下newnode-data x;newnode-next NULL;//开始入队//如果直接尾插的话由于会用到ptail-next,所以得考虑队列为空的情况if (pq-ptail NULL)//如果为空直接把让新节点成为phead和ptail{//按道理来说如果ptail为空phead也应该为空// 但是有可能会因为我们的误操作使得phead不为空这个时候一般是我们写错的问题//所以使用assert来判断一下有问题的话会及时返回错误信息assert(pq-phead NULL);pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}void QueuePop(Queue* pq)
{assert(pq);//如果队列为空没有删除的必要assert(!QueueEmpty(pq));//队列中的出队列相当于链表的头删//如果直接头删那么如果队列只有一个有效数据的话那么我们将phead的空间释放掉但是没有将ptail给置空//这样会导致ptail成为一个野指针所以我们需要考虑只有一个节点多个节点的情况if (pq-phead-next NULL)//一个节点的情况,直接将这个节点释放并置空即可{free(pq-phead);pq-phead pq-ptail NULL;//置空防止野指针}else//多个节点的情况直接头删{QNode* next pq-phead-next;//临时指针记住下一个节点free(pq-phead);pq-phead next;//让下一个节点成为新的头}pq-size--;
}QDatatype QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//队列如果为空则不可能找得到队列头元素//队列不为空的时候直接返回phead指向的数据return pq-phead-data;
}QDatatype QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//队列如果为空则不可能找得到队尾元素//队列不为空的时候直接返回ptail指向的数据return pq-ptail-data;
}int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}bool QueueEmpty(Queue* pq)//链表为空的情况可以根据容量也可以根据ptailNULLpheadNULL
{assert(pq);return pq-phead NULL pq-ptail NULL;
}void QueueDestory(Queue* pq)
{assert(pq);//判断传的是不是空指针//要逐个节点释放QNode* pcur pq-phead;while (pcur){QNode* next pcur-next;free(pcur);pcur next;}pq-phead pq-ptail NULL;pq-size 0;
}2.3.3 mystack.h
#includeQueue.htypedef struct MyStack
{Queue q1;Queue q2;
} MyStack;
//用两个队列实现栈构建一个结构体去管理这两个队列MyStack* myStackCreate();//初始化栈
void myStackPush(MyStack* obj, int x);//压栈
int myStackPop(MyStack* obj);//出栈
int myStackTop(MyStack* obj);//获取栈顶元素
bool myStackEmpty(MyStack* obj);//判断栈是否为空
void myStackFree(MyStack* obj);//释放栈
2.3.4 mystack.c
#includeMyStack.hMyStack* myStackCreate() //返回一个MySack类型的指针
{MyStack* obj (MyStack*)malloc(sizeof(MyStack));if (obj NULL){perror(malloc fail);exit(1);}
//如果开辟成功对栈初始化相当于对栈结构体中的两个队列初始化QueueInit(obj-q1);QueueInit(obj-q2);return obj;
}void myStackPush(MyStack* obj, int x)
//压栈前必须在不为空的队列中压栈
{if (!QueueEmpty(obj-q1))//如果q1不为空压q1QueuePush(obj-q1, x);else//如果q1为空则压q2QueuePush(obj-q2, x);
}int myStackPop(MyStack* obj)
//出栈必须找到不为空的队列然后将该队列的元素倒倒另一个队列中知道只剩最后一个元素的时候就删除
{//要找到不为空的队列进行操作所以先假设一个为空一个不为空如果给个条件判断Queue* Emptyq obj-q1;Queue* NonEmptyq obj-q2;if (!QueueEmpty(obj-q1))//错了的话就认个错然后换回来{NonEmptyq obj-q1;Emptyq obj-q2;}//开始导数据while (QueueSize(NonEmptyq) 1){//将队列头的元素倒进去另一个队列在出栈QueuePush(Emptyq, QueueFront(NonEmptyq));//压栈QueuePop(NonEmptyq);//倒入一个就将非空队列出队列一个}//倒完后只剩一个数据了先记录返回值再删除int top QueueFront(NonEmptyq);QueuePop(NonEmptyq);return top;
}int myStackTop(MyStack* obj)
//找到不为空的队列然后获取队列尾的元素相当于获取栈顶元素
{if (!QueueEmpty(obj-q1))//如果q1不为空取q1队尾return QueueBack(obj-q1);else//如果q2不为空取q2队尾return QueueBack(obj-q2);
}bool myStackEmpty(MyStack* obj) //栈为空当且仅当两个队列都为空
{return QueueEmpty(obj-q1) QueueEmpty(obj-q2);
}void myStackFree(MyStack* obj)
{//释放obj前一定也要将q1和q2的空间释放了QueueDestory(obj-q1);QueueDestory(obj-q2);free(obj);//obj NULL;没用一级指针接受指针相当于值传递//要手动在main函数中置空三、用两个栈实现队列
力扣用栈实现队列 3.1 思路 3.2 代码实现
3.2.1 栈的代码
这里先把栈的声明放这里
stack.h
#pragma once
#includestdio.h
#includestdbool.h
#includestdlib.h
#includeassert.htypedef int STDataType;
//支持动态增长的栈
typedef struct Stack
{STDataType* a;int top;//栈顶int capacity;//栈容量
}Stack;void StackInit(Stack* ps);//初始化栈
void StackPush(Stack* ps, STDataType x);//入栈
void StackPop(Stack* ps);//出栈
STDataType StackTop(Stack* ps);//获取栈顶元素
int StackSize(Stack* ps);//获取栈中有效元素个数
bool StackEmpty(Stack* ps);//检测栈是否为空为空返回true
void StackDestory(Stack* ps);//销毁栈3.2.2 结构体的创建 根据前面的思路一个栈专门用来入栈一个栈专门用来出栈
typedef struct MyQueue
{Stack Pushst;//专门用来入栈Stack Popst;//专门用来出栈
} MyQueue;MyQueue* myQueueCreate();//初始化队列
void myQueuePush(MyQueue* obj, int x);//模拟入队
int myQueuePop(MyQueue* obj);//模拟出队并返回出去的头元素
int myQueuePeek(MyQueue* obj);//获取队列头元素并返回
bool myQueueEmpty(MyQueue* obj);//判断队列是否为空
void myQueueFree(MyQueue* obj);//销毁队列3.2.3 初始化队列并返回节点 初始化队列本质上就是对两个栈进行初始化
MyQueue* myQueueCreate()
{MyQueue* obj (MyQueue*)malloc(sizeof(MyQueue));if (obj NULL){perror(malloc fail);exit(1);}//对队列初始化其实就是对里面的两个栈初始化StackInit(obj-Pushst);StackInit(obj-Popst);return obj;
}3.2.4 模拟入队
入队就很简单了直接往第一个栈里面入栈就行
void myQueuePush(MyQueue* obj, int x)
{StackPush(obj-Pushst, x);
}
3.2.5 获取队列头的元素并返回
队列头的元素要在第二个栈去获取但在获取前还得确保第二个栈有元素如果没有就得先把第一个栈倒过去
int myQueuePeek(MyQueue* obj)
//获取队列头元素有两种情况
//1、一种是popst不为空直接返回其top下标的元素就行了
//2、一种是popst为空这时候需要将pushst中的数据全部倒过去再重复情况1
{if (StackEmpty(obj-Popst)){while (!StackEmpty(obj-Pushst)){//挪数据就是一边给popst入栈一边给pushst出栈StackPush(obj-Popst, StackTop(obj-Pushst));StackPop(obj-Pushst);}}return StackTop(obj-Popst);
}
3.2.6 模拟出队并返回出去的头元素
出队也要确保第二个栈不为空但其实我们有了上面这个函数直接调用一次就相当于是把我们把这个操作给完成了所以我们直接接受上面那个函数的返回值然后直接pop就行
int myQueuePop(MyQueue* obj)
{
//跟myQueuePeek一样有两种情况但是我们调用了这个函数相当于是帮我们判断过了此时直接删就可以了int top myQueuePeek(obj);StackPop(obj-Popst);return top;
}
3.2.7 判断队列是否为空
队列是否为空本质上就是两个栈是否为空
bool myQueueEmpty(MyQueue* obj)
{return StackEmpty(obj-Popst) StackEmpty(obj-Pushst);
}
3.2.8 销毁队列
队列销毁本质上就是两个栈的销毁但是要在最后把队列的结构体的释放掉
void myQueueFree(MyQueue* obj)
{StackDestory(obj-Popst);StackDestory(obj-Pushst);free(obj);//没用obj NULL;
}
注意的是这边接受obj的是一级指针相当于值传递这里置空没什么意义要在外面手动置空
3.3 全部代码
3.3.1 stack.h
#pragma once
#includestdio.h
#includestdbool.h
#includestdlib.h
#includeassert.htypedef int STDataType;
//支持动态增长的栈
typedef struct Stack
{STDataType* a;int top;//栈顶int capacity;//栈容量
}Stack;void StackInit(Stack* ps);//初始化栈
void StackPush(Stack* ps, STDataType x);//入栈
void StackPop(Stack* ps);//出栈
STDataType StackTop(Stack* ps);//获取栈顶元素
int StackSize(Stack* ps);//获取栈中有效元素个数
bool StackEmpty(Stack* ps);//检测栈是否为空为空返回true
void StackDestory(Stack* ps);//销毁栈3.3.2 stack.c
#includeStack.hvoid StackInit(Stack* ps)
{ps-a NULL;ps-top ps-capacity 0;
}void StackPush(Stack* ps, STDataType x)
{assert(ps);//判断是否需要扩容if (ps-top ps-capacity){int newcapacity ps-capacity 0 ? 4 : 2 * ps-capacity;STDataType* temp (STDataType*)realloc(ps-a, sizeof(STDataType) * newcapacity);if (temp NULL){perror(realloc fail);exit(1);}ps-a temp;ps-capacity newcapacity;}//压栈ps-a[ps-top] x;
}void StackPop(Stack* ps)
{assert(ps);//如果栈为空则没有删除的必要assert(!StackEmpty(ps));ps-top--;
}STDataType StackTop(Stack* ps)
{assert(ps);//如果栈为空不可能有栈顶元素assert(!StackEmpty(ps));return ps-a[ps-top - 1];
}int StackSize(Stack* ps)
{assert(ps);return ps-top;
}bool StackEmpty(Stack* ps)
{assert(ps);return ps-top 0;
}void StackDestory(Stack* ps)
{free(ps-a);ps-a NULL;ps-top ps-capacity 0;
}
3.3.3 myqueue.h
#includeStack.htypedef struct MyQueue
{Stack Pushst;//专门用来入栈Stack Popst;//专门用来出栈
} MyQueue;MyQueue* myQueueCreate();//初始化队列并返回节点
void myQueuePush(MyQueue* obj, int x);//模拟入队
int myQueuePop(MyQueue* obj);//模拟出队并返回出去的头元素
int myQueuePeek(MyQueue* obj);//获取队列头元素并返回
bool myQueueEmpty(MyQueue* obj);//判断队列是否为空
void myQueueFree(MyQueue* obj);//销毁队列3.3.4 myqueue.c
#includeMyQueue.hMyQueue* myQueueCreate()
{MyQueue* obj (MyQueue*)malloc(sizeof(MyQueue));if (obj NULL){perror(malloc fail);exit(1);}//对队列初始化其实就是对里面的两个栈初始化StackInit(obj-Pushst);StackInit(obj-Popst);return obj;
}void myQueuePush(MyQueue* obj, int x)
{StackPush(obj-Pushst, x);
}int myQueuePop(MyQueue* obj)
{
//跟myQueuePeek一样有两种情况但是我们调用了这个函数相当于是帮我们判断过了此时直接删就可以了int top myQueuePeek(obj);StackPop(obj-Popst);return top;
}int myQueuePeek(MyQueue* obj)
//获取队列头元素有两种情况
//1、一种是popst不为空直接返回其top下标的元素就行了
//2、一种是popst为空这时候需要将pushst中的数据全部倒过去再重复情况1
{if (StackEmpty(obj-Popst)){while (!StackEmpty(obj-Pushst)){//挪数据就是一边给popst入栈一边给pushst出栈StackPush(obj-Popst, StackTop(obj-Pushst));StackPop(obj-Pushst);}}return StackTop(obj-Popst);
}bool myQueueEmpty(MyQueue* obj)
{return StackEmpty(obj-Popst) StackEmpty(obj-Pushst);
}void myQueueFree(MyQueue* obj)
{StackDestory(obj-Popst);StackDestory(obj-Pushst);free(obj);//没用obj NULL;
}
