海宁网站网站建设,网站做友情链接,做行业网站广告能赚多少钱,网上书城网站开发的数据字典分享一首歌曲吧#xff0c;希望在枯燥的刷题生活中带给你希望和勇气#xff0c;加油#xff01; 题目#xff1a;
请你仅使用两个队列实现一个后入先出#xff08;LIFO#xff09;的栈#xff0c;并支持普通栈的全部四种操作#xff08;push、top、pop 和 empty#…分享一首歌曲吧希望在枯燥的刷题生活中带给你希望和勇气加油 题目
请你仅使用两个队列实现一个后入先出LIFO的栈并支持普通栈的全部四种操作push、top、pop 和 empty。
实现 MyStack 类
void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元素。int top() 返回栈顶元素。boolean empty() 如果栈是空的返回 true 否则返回 false 。
题解
首先自己实现一个队列粘贴复制过去
注意这道题目队列的实现方法不同不会影响题目只要是个队列先进先出那么不管你是双向还是结构不同都不会影响题目的实现。
#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.htypedef int DataType;
typedef struct Queue
{DataType data;struct Queue *next;
}Queue;typedef struct Q
{Queue* head;Queue* tail;int size;
}Q;void Init(Q *qq);
void Destroy(Q* qq);
void QueuePush(Q* qq, DataType x);
void QueuePop(Q* qq);
DataType GetQueueFrontNum(Q* qq);
DataType GetQueueBackNum(Q* qq);
bool Empty(Q* qq);
int Size(Q* qq);void Init(Q* qq)
{assert(qq);qq-head NULL;qq-tail NULL;qq-size 0;
}void QueuePush(Q* qq, DataType x)
{assert(qq);Queue* temp (Queue*)malloc(sizeof(Queue));if (temp NULL){perror(malloc fail);exit(-1);}temp-data x;temp-next NULL;if (qq-tail NULL)qq-head qq-tail temp;else{qq-tail-next temp;qq-tail temp;}qq-size;
}void QueuePop(Q* qq)
{assert(qq);assert(!Empty(qq));if (qq-head qq-tail){free(qq-head);qq-head qq-tail NULL;}else{Queue* next qq-head-next;free(qq-head);qq-head next;}qq-size--;
}DataType GetQueueFrontNum(Q* qq)
{assert(qq);assert(!Empty(qq));return qq-head-data;
}DataType GetQueueBackNum(Q* qq)
{assert(qq);assert(!Empty(qq));return qq-tail-data;
}bool Empty(Q* qq)
{assert(qq);return qq-size 0;
}void Destroy(Q* qq)
{assert(qq);Queue *cur qq-head;while(cur){Queue *next cur-next;free(cur);cur next;}qq-head qq-tail NULL;qq-size 0;
}int Size(Q* qq)
{assert(qq);return qq-size;
}
剩下的就是题目接口
typedef struct {Q q1;Q q2;
} MyStack;
MyStack* myStackCreate()
{MyStack *st (MyStack*)malloc(sizeof(MyStack));Init(st-q1);Init(st-q2);return st;
}
void myStackPush(MyStack* obj, int x)
{if(!Empty(obj-q1)){QueuePush(obj-q1,x);}else{QueuePush(obj-q2,x);}
}int myStackPop(MyStack* obj)
{Q *empty obj-q1;Q *obempty obj-q2;if(!Empty(obj-q1)){empty obj-q2;obempty obj-q1;}int sz Size(obempty) - 1;for(int i0; isz; i){QueuePush(empty,GetQueueFrontNum(obempty));QueuePop(obempty);}int num GetQueueFrontNum(obempty);QueuePop(obempty);return num;
}
int myStackTop(MyStack* obj)
{if(!Empty(obj-q1)){return GetQueueBackNum(obj-q1);}else{return GetQueueBackNum(obj-q2);}
}
bool myStackEmpty(MyStack* obj)
{return (obj-q1)-size 0 (obj-q2)-size 0;
}void myStackFree(MyStack* obj)
{Destroy(obj-q1);Destroy(obj-q2);free(obj);
}
