建设网站时seo标题,wordpress 运费模板下载,广东东莞1例新冠状,上海市人力资源网官网问题描述#xff1a; 请你仅用两个队列实现一个后入先出#xff08;LIFO#xff09;的栈#xff0c;并支持普通队列的全部四种操作#xff08;push、top、pop和empty#xff09;。 实现MyStack类#xff1a; void push(int x) 将元素x压入栈顶。int pop()移除并返回栈顶…问题描述 请你仅用两个队列实现一个后入先出LIFO的栈并支持普通队列的全部四种操作push、top、pop和empty。 实现MyStack类 void push(int x) 将元素x压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的返回true否则返回false。 解题思路 1. 入数据往不为空的队列入
2. 出数据把不为空的队列数据导入为空直至只剩最后一个
解决本题之前要先将队列的各类接口函数准备好队列的接口函数我上一篇中提到了喔
#includestdio.h
#includestdbool.h
#includeassert.h
#includestdlib.h
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;//删除数据和插入数据需要记录头结点和尾结点
typedef struct Queue
{QNode* head;QNode* tail;
}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);
//取数据的个数
int QueueSize(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);void QueueInit(Queue* pq)
{assert(pq);pq-head pq-tail NULL;
}
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;//返回初始状态
}
//队尾入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){printf(malloc fail\n);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;}}
//队头出
void QueuePop(Queue* pq)
{assert(pq);assert(pq-head);//断言队列是否为空为空就不可删除会有野指针if (pq-head-next NULL)//当只有一个节点时tail可能为野指针tail指向已释放的空间pq-tail NULL;QNode* next pq-head-next;free(pq-head);pq-head next;}
//取队头的数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq-head);return pq-head-data;
}
//取队尾的数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq-head);return pq-tail-data;
}
//取数据的个数
int QueueSize(Queue* pq)
{assert(pq);int size 0;QNode* cur pq-head;while (cur){size;cur cur-next;}return size;
}
//判断队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-head NULL;
}
通过队列创建栈
typedef struct
{Queue q1;Queue q2;
}MyStack;
MyStack* myStackCreate()
{MyStack* ps (MyStack*)malloc(sizeof(MyStack));if (ps NULL){printf(malloc fail\n);exit(-1);}QueueInit(ps-q1);//对队列进行初始化QueueInit(ps-q2);return ps;
}
在栈顶添加数据
添加数据时要在不为空的队列里添加
void myStackPush(MyStack* obj, int x)
{if (!QueueEmpty(obj-q1)){QueuePush(obj-q1,x);}else{QueuePush(obj-q2, x);}
}
从栈顶处删除数据并返回第一个数据
int myStackPop(MyStack* obj)
{Queue* emptyQ obj-q1;Queue* nonemptyQ obj-q2;if (!QueueEmpty(obj-q1)){emptyQobj-q2;nonemptyQobj-q1;}//倒数据while (QueueSize(nonemptyQ) 1){//将不空的队列的头拷贝至空队列中QueuePush(emptyQ, QueueFront(nonemptyQ));QueuePop(nonemptyQ);//删除头数据}int top QueueFront(nonemptyQ);QueuePop(nonemptyQ);//删除最后一个数据实现了后进先出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)
{QueueDestory(obj-q1);QueueDestory(obj-q2);free(obj);
}
整体代码
#includestdio.h
#includestdbool.h
#includeassert.h
#includestdlib.h
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;//删除数据和插入数据需要记录头结点和尾结点
typedef struct Queue
{QNode* head;QNode* tail;
}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);
//取数据的个数
int QueueSize(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);void QueueInit(Queue* pq)
{assert(pq);pq-head pq-tail NULL;
}
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;//返回初始状态
}
//队尾入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){printf(malloc fail\n);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;}}
//队头出
void QueuePop(Queue* pq)
{assert(pq);assert(pq-head);//断言队列是否为空为空就不可删除会有野指针if (pq-head-next NULL)//当只有一个节点时tail可能为野指针tail指向已释放的空间pq-tail NULL;QNode* next pq-head-next;free(pq-head);pq-head next;}
//取队头的数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq-head);return pq-head-data;
}
//取队尾的数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq-head);return pq-tail-data;
}
//取数据的个数
int QueueSize(Queue* pq)
{assert(pq);int size 0;QNode* cur pq-head;while (cur){size;cur cur-next;}return size;
}
//判断队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-head NULL;
}
typedef struct
{Queue q1;Queue q2;
}MyStack;
MyStack* myStackCreate()
{MyStack* ps (MyStack*)malloc(sizeof(MyStack));if (ps NULL){printf(malloc fail\n);exit(-1);}QueueInit(ps-q1);QueueInit(ps-q2);return ps;
}
void myStackPush(MyStack* obj, int x)
{if (!QueueEmpty(obj-q1)){QueuePush(obj-q1,x);}else{QueuePush(obj-q2, x);}
}
//删除数据且返回栈顶
int myStackPop(MyStack* obj)
{Queue* emptyQ obj-q1;Queue* nonemptyQ obj-q2;if (!QueueEmpty(obj-q1)){emptyQobj-q2;nonemptyQobj-q1;}//倒数据while (QueueSize(nonemptyQ) 1){//将不空的队列的头拷贝至空队列中QueuePush(emptyQ, QueueFront(nonemptyQ));QueuePop(nonemptyQ);//删除头数据}int top QueueFront(nonemptyQ);QueuePop(nonemptyQ);//删除最后一个数据实现了后进先出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)
{QueueDestory(obj-q1);QueueDestory(obj-q2);free(obj);
}
