营销网站好不好,网站icp备案信息如何查询,做网站后端如何接业务,linux wordpress 建站教程分析#xff1a; 队列遵循先入先出的原则#xff0c;栈遵循后入先出的原则 也就是说#xff0c;使用队列实现栈时#xff0c;入队操作正常#xff0c;但是出队要模拟出栈的操作#xff0c;我们需要访问的是队尾的元素#xff1b;题目允许使用两个队列#xff0c;我们可… 分析 队列遵循先入先出的原则栈遵循后入先出的原则 也就是说使用队列实现栈时入队操作正常但是出队要模拟出栈的操作我们需要访问的是队尾的元素题目允许使用两个队列我们可以先将存有数据的队列中除队尾元素外的所有元素依次出队存入空队列中再访问原队列中的队头元素即可 1.使用两个队列构造栈 C语言中没有定义队列的结构我们需要自定义队列及其相关操作 如下结构MyStack由两个队列结构q1和q2构成 为我们创建的栈结构进行动态内存申请并进行初始化 //由两个队列构成栈结构
typedef struct {Queue q1;Queue q2;} MyStack;
//创建栈
MyStack* myStackCreate() {//myStack未具有两个队列的栈结构类型MyStack* obj (MyStack*)malloc(sizeof(MyStack));//内存开辟失败if(obj NULL){perror(malloc fail);exit(-1);}//开辟成功初始化else{QueueInit(obj-q1);QueueInit(obj-q2);}return obj;
}2.压栈操作 模拟栈的压栈操作数据正常入队即可 Note: 我们要将数据插入非空的队列保证每次都存在一个空队列可以进行数据的存储 void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(obj-q1)){QueuePush(obj-q1,x);}else{QueuePush(obj-q2,x);}}
3.移除并返回栈顶元素 模拟栈的出栈操作访问并移除的是非空队列的队尾元素 步骤将存有数据的队列中除队尾元素外的所有元素依次出队存入空队列中再访问并移除原队列中的队头元素即可如下图 上述操作后q1和q2的结构如下: 此时将队列q1中的元素相当于后入的栈顶元素先存储再出队列q1即清空队列q1供下次压栈操作使用返回存储的值即可 int myStackPop(MyStack* obj) {Queue* empty obj-q1;Queue* nonempty obj-q2;if(!QueueEmpty(obj-q1)){nonempty obj-q1; empty obj-q2; }//非空队列前n-1个入空队列并出队剩下最后一个即为栈顶元素while(QueueSize(nonempty) 1){QueuePush(empty,QueueFront(nonempty));QueuePop(nonempty);}int top QueueFront(nonempty);QueuePop(nonempty);//清空队列return top;
}
4.返回栈顶元素 栈顶元素即非空队列的队尾数据 int myStackTop(MyStack* obj) { if(!QueueEmpty(obj-q1)){return QueueBack(obj-q1);}else{return QueueBack(obj-q2);}
}
5.判断是否为空栈 myStack是由两个队列构成的栈结构当两个队列都为空时栈即为空 bool myStackEmpty(MyStack* obj) {return QueueEmpty(obj-q1) QueueEmpty(obj-q2);
}
6.空间释放 创建栈时为其动态申请了空间操作结束需要进行空间释放否则会造成内存泄漏 void myStackFree(MyStack* obj) {QueueDestroy(obj-q1);QueueDestroy(obj-q2);
} 完整参考代码如下
#includestdio.h
#includeassert.h
#includestdlib.htypedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;
}Queue;#define bool int
#define true 1
#define false 0//队列初始化
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 pq-tail NULL;
}
//队列销毁
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-head;while (cur){QNode* del cur;cur cur-next;free(del);}pq-head pq-tail NULL;
}
//数据入队
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);exit(-1);}else{newnode-data x;newnode-next NULL;}//空队列时插入if (pq-tail NULL){pq-head pq-tail newnode;}//非空队列时插入else{pq-tail-next newnode;//链接新元素pq-tail newnode;//更新队尾}
}
//数据出队
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);del NULL;}
}
//访问队头数据
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);/*if (pq-tail pq-head NULL){return true;}else{return false;}*/return pq-head NULL pq-tail NULL;
}
//求队列的大小
int QueueSize(Queue* pq)
{assert(pq);int size 0;QNode* cur pq-head;while (cur){size;cur cur-next;}return size;
}//由两个队列构成栈结构
typedef struct {Queue q1;Queue q2;} MyStack;
//创建栈
MyStack* myStackCreate() {//myStack未具有两个队列的栈结构类型MyStack* obj (MyStack*)malloc(sizeof(MyStack));//内存开辟失败if(obj NULL){perror(malloc fail);exit(-1);}//开辟成功初始化else{QueueInit(obj-q1);QueueInit(obj-q2);}return obj;
}
void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(obj-q1)){QueuePush(obj-q1,x);}else{QueuePush(obj-q2,x);}}int myStackPop(MyStack* obj) {Queue* empty obj-q1;Queue* nonempty obj-q2;if(!QueueEmpty(obj-q1)){nonempty obj-q1; empty obj-q2; }//非空队列前n-1个入空队列并出队剩下最后一个即为栈顶元素while(QueueSize(nonempty) 1){QueuePush(empty,QueueFront(nonempty));QueuePop(nonempty);}int top QueueFront(nonempty);QueuePop(nonempty);//清空队列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);
}
