建网站和建网店的区别,wordpress 关注,网站建设中哪些最重要性,wordpress去掉侧边栏文章目录前言使用两个队列实现栈1.队列接口函数引入2.栈的初始化3.向栈中插入元素4.出栈操作5.取出栈顶元素6.判断栈是否为空7.释放内存空间总结前言
本文章主要介绍栈和队列的相互转换。 使用两个队列实现栈
我们知道#xff0c;栈的特点是后进先出#xff0c;而队列的特点… 文章目录前言使用两个队列实现栈1.队列接口函数引入2.栈的初始化3.向栈中插入元素4.出栈操作5.取出栈顶元素6.判断栈是否为空7.释放内存空间总结前言
本文章主要介绍栈和队列的相互转换。 使用两个队列实现栈
我们知道栈的特点是后进先出而队列的特点是先进先出。
栈的特点 队列的特点 使用两个队列实现栈的思路是
1.向两个队列中的任一队列放入元素 2.取出元素时队列的功能是先进先出要达到后进先出需要将前面的所有元素取出存入另一个空队列中然后将剩下的最后一个元素释放掉即可。
比如 后面如果想继续插入元素的话应该将插入的元素放在非空队列中这样就实现了栈的功能。 这样实现的原因是两个队列中必有其中一个队列是空队列保证了栈的后进先出的特点。
下面给出一道题目 两个队列实现栈 这里我用c语言来实现所以先先写好队列的基本功能再将接口函数引入。
1.队列接口函数引入
typedef int QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;void QueueInit(Queue* pq);
void QueueDestroy(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 NULL;pq-tail NULL;pq-size 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-head;while (cur){QNode* del cur;cur cur-next;free(del);//del NULL;}pq-head pq-tail NULL;pq-size 0;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-data x;newnode-next NULL;if (pq-tail NULL){pq-head pq-tail newnode;}else{pq-tail-next newnode;pq-tail newnode;}pq-size;
}void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq-head-next NULL){free(pq-head);pq-head pq-tail NULL;}else{QNode* del pq-head;pq-head pq-head-next;free(del);}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-head NULL pq-tail NULL;
}// 1G 1024MB
// 1024MB 1024*1024KB
// 1024*1024KB 1024*1024*1024Byteint QueueSize(Queue* pq)
{assert(pq);/*int size 0;QNode* cur pq-head;while (cur){cur cur-next;size;}return size;*/return pq-size;
}
2.栈的初始化
MyStack* myStackCreate() {MyStack*st (MyStack*)malloc(sizeof(MyStack));QueueInit(st-q1);QueueInit(st-q2);return st;
}栈的初始化就是将两个队列进行初始化。 3.向栈中插入元素
保证其中一个队列不为空
//首先需要判断哪个队列为空可以用ifelse来判断但是这样操作冗余的所以可以使用假设
int myStackPop(MyStack*
void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(obj-q1)){QueuePush(obj-q1,x);}else{QueuePush(obj-q2,x);}
}由于无法得知哪一个队列为空则需要判断或者假设使用判断的化代码比较冗余在这里我使用假设假设第一个队列是空。 4.出栈操作
int myStackPop(MyStack* obj) {Queue*EmptyQ obj-q1;Queue*NonEmptyQ obj-q2;if(!QueueEmpty(obj-q1)){//如果q1不为空返回假就返回真进入if//意思就是我们假设错误了。EmptyQ obj-q2;NonEmptyQ obj-q1;}//来到这里已经知道哪个是空了,把所有元素导入非空队列将最后一个不导while(QueueSize(NonEmptyQ)1){QueuePush(EmptyQ,QueueFront(NonEmptyQ));QueuePop(NonEmptyQ);}int top QueueFront(NonEmptyQ);QueuePop(NonEmptyQ);return top;}5.取出栈顶元素
int myStackTop(MyStack* obj) {//取出栈顶元素//在首先的队列中我们虽然不能删除队尾元素但是我们可以取出队尾的元素if(!QueueEmpty(obj-q1)){return QueueBack(obj-q1);}else{return QueueBack(obj-q2);}
}6.判断栈是否为空
bool myStackEmpty(MyStack* obj)
{ //判断栈是否为空需要判断两个队列是否为空return QueueEmpty(obj-q1) QueueEmpty(obj-q2);
}判断栈是否为空需要判断两个队列是否为空 7.释放内存空间
void myStackFree(MyStack* obj) {QueueDestroy(obj-q1);QueueDestroy(obj-q2);free(obj);
}注意由于两个队列的维护是依靠指针所以两个队列申请的空间先释放再释放栈结构体空间 总结
本文章介绍了两个队列实现栈的方法。 使用队列实现栈和使用栈实现队列都是可以的 下篇文章介绍使用两个栈实现队列
