濮阳网站建设熊掌号,网站开发培训费,广州越秀网站建设,江苏建设信息网证书查询力扣 225 用队列实现栈
题目描述
请你仅使用两个队列实现一个后入先出#xff08;LIFO#xff09;的栈#xff0c;并支持普通栈的全部四种操作#xff08;push、top、pop 和 empty#xff09;。
实现 MyStack 类#xff1a;
void push(int x) 将元素 x 压入栈顶。int…力扣 225 用队列实现栈
题目描述
请你仅使用两个队列实现一个后入先出LIFO的栈并支持普通栈的全部四种操作push、top、pop 和 empty。
实现 MyStack 类
void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元素。int top() 返回栈顶元素。boolean empty() 如果栈是空的返回 true 否则返回 false 。 思路分析
关于栈的功能见于是基础的数据结构且如果知道队列的功能也一定会知道栈的功能这里不过多赘述直接上思路
基于栈后进先出而队列先进先出的特点我们可以定义两个队列
这里先描述出栈的实现假设一个队列里已经放好了值为1234按照队列出队的话先取到1但如果出栈的话就需要取到4这里另外一个队列就派上用场了我们可以将队尾前的所有元素出队并进入到另一个队列里最后剩下的就是需要出栈的元素此时我们在去原队列的队头元素即可。
接下来到入栈的实现关键在于应该入哪个队如果两队为空随便一个但接下来的话如果要方便上述出栈的实现我们就需要入队到不为空的队列。
紧接着是返回栈顶元素我们已经知道队尾就是我们出栈的元素所以这里直接返回队列的队尾元素即可。
判断栈为空直接检测两个队列是否同时为空即可。
力扣不提供队列的实现代码我们需要自己实现
完整代码
队列的实现代码
typedef int QueueDataType;typedef struct QuNode
{QueueDataType data;struct QuNode* next;
}QuNode;typedef struct Queue
{QuNode* phead;QuNode* ptail;int size;
}Queue;// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QueueDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QueueDataType QueueFront(Queue* q);
// 获取队列队尾元素
QueueDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空如果为空返回非零结果如果非空返回0
int QueueEmpty(Queue* q);
//打印队列
void QueuePrint(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);// 初始化队列
void QueueInit(Queue* q)
{assert(q);q-phead NULL;q-ptail NULL;q-size 0;
}
// 队尾入队列
void QueuePush(Queue* q, QueueDataType data)
{assert(q);//创建结点QuNode* newnode (QuNode*)malloc(sizeof(QuNode));if (newnode NULL){perror(malloc fail);return;}newnode-data data;newnode-next NULL;//插入if (q-ptail NULL){q-phead q-ptail newnode;}else{q-ptail-next newnode;q-ptail newnode;}q-size;
}// 队头出队列
void QueuePop(Queue* q)
{assert(q);assert(q-phead);QuNode* del q-phead;q-phead q-phead-next;free(del);del NULL;if (q-phead NULL){q-ptail NULL;}q-size--;
}// 获取队列头部元素
QueueDataType QueueFront(Queue* q)
{assert(q);assert(q-phead);return q-phead-data;
}
// 获取队列队尾元素
QueueDataType QueueBack(Queue* q)
{assert(q);assert(q-ptail);return q-ptail-data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{assert(q);return q-size;
}
// 检测队列是否为空如果为空返回非零结果如果非空返回0
int QueueEmpty(Queue* q)
{assert(q);if (q-phead NULL){return 1;}else{return 0;}
}// 销毁队列
void QueueDestroy(Queue* q)
{assert(q);QuNode* cur q-phead;while (cur){QuNode* next cur-next;free(cur);cur next;}q-phead q-ptail NULL;q-size 0;
}//打印队列
void QueuePrint(Queue* q)
{assert(q);QuNode* cur q-phead;while (cur-next!NULL){printf(%d , cur-data);cur cur-next;}
}
实现代码
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* pst, int x) {if(QueueEmpty(pst-q1))//找出不为空的队列将元素入队{QueuePush(pst-q2,x);}else{QueuePush(pst-q1,x);}}int myStackPop(MyStack* pst) {Queue* emptypst-q1;//假设法假设q1为空后面再判断一下结果不对再反过来Queue* noneemptypst-q2;if(QueueEmpty(pst-q2)){emptypst-q2;noneemptypst-q1;}while(QueueSize(noneempty)1)//将出栈元素前的所有元素出队进入到空队列中{QueuePush(empty,QueueFront(noneempty));QueuePop(noneempty);}int topQueueFront(noneempty);//取到出栈元素QueuePop(noneempty);return top;}int myStackTop(MyStack* pst) {if(QueueEmpty(pst-q1))//返回不为空队列的队尾元素{return QueueBack(pst-q2);}else{return QueueBack(pst-q1);}}bool myStackEmpty(MyStack* obj) {return QueueEmpty(obj-q1)QueueEmpty(obj-q2);}void myStackFree(MyStack* obj) {QueueDestroy(obj-q1);QueueDestroy(obj-q2);free(obj);objNULL;}
