温州科技网站建设,搜讯网站建设,多语言企业网站源码,竞价推广渠道文章目录 一、队列实现栈的特点分析 1、1 具体分析 1、2 整体概括 二、队列模拟实现栈代码的实现 2、1 手撕 队列 代码 queue.h queue.c 2、2 用队列模拟实现栈代码 三、总结 #x1f64b;♂️ 作者#xff1a;Ggggggtm #x1f64b;♂️ #x1f440; 专栏#xff1… 文章目录 一、队列实现栈的特点分析 1、1 具体分析 1、2 整体概括 二、队列模拟实现栈代码的实现 2、1 手撕 队列 代码 queue.h queue.c 2、2 用队列模拟实现栈代码 三、总结 ♂️ 作者Ggggggtm ♂️ 专栏数据结构与算法、高频面试问题 标题用队列模拟栈 ❣️ 寄语与其忙着诉苦不如低头赶路奋路前行终将遇到一番好风景 ❣️ 我们上篇文章讲述了用两个栈实现队列 用过对上篇文章的学习后我们再去学用两个队列实现栈就变得相对来说容易了很多。本篇文章会对用两个队列实现栈进行详解希望会对你有所帮助。 一、队列实现栈的特点分析
1、1 具体分析 队列和栈在插入数据时队列是从队尾进行插入栈是从栈顶插入。但是他们的删除数据是不同的。我们知道队列的特点是先新先出 删除数据是在对头进行删除栈的特点是先进后出也就是在栈顶进行删除。 当我们用队列实现栈时最根本的也是最重要的是需要解决删除的问题。我们用队列实现栈时在队列中的删除就不是删除对头的元素了我们需要根据栈的特点进行删除也就是我们需要删除的是队尾的元素。 操作时首先我们先往队列中插入元素。注意我们插入元素时应该往不为空的队列中插入元素如果两个队列都为空我们可以随意往一个队列中插入元素。为什么要往不为空的队列中插入元素呢我们先接着往下看。我们是用队列模拟栈此时我们想要删除的是栈顶的元素也就是队尾的元素。我们需要把前size-1个元素移动到另一个空的对列中然后再删除队列中的最后一个元素也就是队尾元素。 这也是我们为什么插入元素时要往不为空的队列中插入的原因。因为我们需要一个空的队列进行来回导元素从而达到删除队尾元素的目的。这时插入操作和删除操作我们都是可以用队列去模拟实现出栈的效果了。插入和删除重复上面的操作就可以。 1、2 整体概括 通过我们上面的分析用队列模拟实现栈和用栈模拟队列的思路大同小异。我们看用队列模拟栈的整体思路 插入时往不为空的队列插入。第一次插入时两个队列都为空此时随便插入一个队列即可。删除时需要把不为空的队列中的元素前size-1个元素导入到空队列中。然后再删除剩下的一个元素。返回栈顶的元素也就是返回队尾的元素。二、队列模拟实现栈代码的实现 我们这里用c语言实现所以还要手撕一个队列的代码。当然C容器中有队列可以直接用。大家熟悉思路后可以用其它语言做一下本题OJ链接用队列实现栈 - OJ链接LeetCode。 2、1 手撕 队列 代码
queue.h
typedef int QDataType;typedef struct QNode
{struct QNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
queue.c
void QueueInit(Queue* pq)
{assert(pq);pq-head pq-tail NULL;pq-size 0;
}
void QueueDestory(Queue* pq)
{assert(pq);QNode* cur pq-head;while (cur){QNode* next cur-next;free(cur);cur next;}pq-head pq-tail NULL;pq-size 0;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* tmp (QNode*)malloc(sizeof(QNode));if (tmp NULL){perror(malloc failed);exit(-1);}tmp-next NULL;tmp-data x;if (pq-head pq-tail pq-head NULL){pq-head pq-tail tmp;}else{pq-tail-next tmp;pq-tail tmp;}pq-size;
}
void QueuePop(Queue* pq)
{assert(pq);assert(pq-head ! NULL);if (pq-head-next NULL){free(pq-head);pq-head pq-tail NULL;}else{QNode* next pq-head-next;free(pq-head);pq-head next;}pq-size--;
}
2、2 用队列模拟实现栈代码
typedef int QDataType;typedef struct QNode
{struct QNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
void QueueInit(Queue* pq)
{assert(pq);pq-head pq-tail NULL;pq-size 0;
}
void QueueDestory(Queue* pq)
{assert(pq);QNode* cur pq-head;while (cur){QNode* next cur-next;free(cur);cur next;}pq-head pq-tail NULL;pq-size 0;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* tmp (QNode*)malloc(sizeof(QNode));if (tmp NULL){perror(malloc failed);exit(-1);}tmp-next NULL;tmp-data x;if (pq-head pq-tail pq-head NULL){pq-head pq-tail tmp;}else{pq-tail-next tmp;pq-tail tmp;}pq-size;
}
void QueuePop(Queue* pq)
{assert(pq);assert(pq-head ! NULL);if (pq-head-next NULL){free(pq-head);pq-head pq-tail NULL;}else{QNode* next pq-head-next;free(pq-head);pq-head next;}pq-size--;
}QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-head-data;
}
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-tail-data;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}typedef struct
{Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate()
{MyStack* st(MyStack*)malloc(sizeof(MyStack));if(stNULL)return false;QueueInit(st-q1);QueueInit(st-q2);return st;
}void myStackPush(MyStack* obj, int x)
{if(QueueSize(obj-q1)!0){QueuePush(obj-q1,x);}else{QueuePush(obj-q2,x);}
}int myStackPop(MyStack* obj)
{Queue* tmpobj-q1;Queue* notmpobj-q2;if(QueueSize(notmp)0){tmpobj-q2;notmpobj-q1;}while(QueueSize(notmp)1){QueuePush(tmp,QueueFront(notmp));QueuePop(notmp);}QDataType resQueueFront(notmp);QueuePop(notmp);return res;
}int myStackTop(MyStack* obj)
{if(QueueSize(obj-q1)!0)return QueueBack(obj-q1);elsereturn QueueBack(obj-q2);
}bool myStackEmpty(MyStack* obj)
{return QueueEmpty(obj-q1) QueueEmpty(obj-q2);
}void myStackFree(MyStack* obj)
{QueueDestory(obj-q1);QueueDestory(obj-q2);free(obj);
}三、总结 以上就是整个用队列模拟实现栈的整个过程主要是利用空队列删除队尾的元素。我们应该熟练掌握用队列模拟实现栈和用栈模拟实现队列两者都是面试中的高频题目。本篇文章的讲解就到这里希望以上对容对对你有所帮助感谢阅读ovo~
