化妆品网站建设,网站右键禁止,天津协会网站建设,江苏建设工程交易中心网站目录
225. 用队列实现栈
题目
思路 代码
232. 用栈实现队列
题目 思路
代码 225. 用队列实现栈
225. 用队列实现栈 - 力扣#xff08;LeetCode#xff09;https://leetcode.cn/problems/implement-stack-using-queues/description/
题目 请你仅使用两个队列实现一个后…
目录
225. 用队列实现栈
题目
思路 代码
232. 用栈实现队列
题目 思路
代码 225. 用队列实现栈
225. 用队列实现栈 - 力扣LeetCodehttps://leetcode.cn/problems/implement-stack-using-queues/description/
题目 请你仅使用两个队列实现一个后入先出LIFO的栈并支持普通栈的全部四种操作push、top、pop 和 empty。 实现 MyStack 类 void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元素。int top() 返回栈顶元素。boolean empty() 如果栈是空的返回 true 否则返回 false 。 示例 思路
两个队列每次要删除数据时把不删除的数据先导到另一个队列留下的数据刚好从队头开始删除。。入队列时入不为空的队列。出队列时不为空队列的前N-1个数据倒入空队列中剩下的就在队头方便删除。
图示 代码
//链式结构表示队列
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;//队列的结构
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Que;
//初始化队列
void QueueInit(Que* pq);
//销毁队列
void QueueDestroy(Que* pq);
//队尾入队列
void QueuePush(Que* pq, QDataType x);
//队头出队列
void QueuePop(Que* pq);
//获取队列队头元素
QDataType QueueFront(Que* pq);
//获取队列队尾元素
QDataType QueueBack(Que* pq);
//检测队列是否为空如果为空返回非零结果如果非空返回0
bool QueueEmpty(Que* pq);
//检测队列中有效元素个数
int QueueSize(Que* pq);void QueueInit(Que* pq)
{assert(pq);pq-head pq-tail NULL;pq-size 0;
}void QueueDestroy(Que* 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(Que* 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(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));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(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-head-data;
}QDataType QueueBack(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-tail-data;
}bool QueueEmpty(Que* pq)
{assert(pq);return pq-head NULL;
}int QueueSize(Que* pq)
{assert(pq);return pq-size;
}typedef struct {Que q1;Que q2;
} MyStack;MyStack* myStackCreate() {MyStack* pst(MyStack*)malloc(sizeof(MyStack));QueueInit(pst-q1);QueueInit(pst-q2);return pst;
}void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(obj-q1)){QueuePush(obj-q1,x);}else{QueuePush(obj-q2,x);}
}int myStackPop(MyStack* obj) {Que* emptyobj-q1;Que* nonEmptyobj-q2;if(!QueueEmpty(obj-q1)){nonEmptyobj-q1;emptyobj-q2;}while(QueueSize(nonEmpty)1){QueuePush(empty,QueueFront(nonEmpty));QueuePop(nonEmpty);}int topQueueFront(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);free(obj);
} 232. 用栈实现队列
232. 用栈实现队列 - 力扣LeetCodehttps://leetcode.cn/problems/implement-queue-using-stacks/description/
题目 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作push、pop、peek、empty 实现 MyQueue 类 void push(int x) 将元素 x 推到队列的末尾int pop() 从队列的开头移除并返回元素int peek() 返回队列开头的元素boolean empty() 如果队列为空返回 true 否则返回 false 示例 思路 两个栈分别为pushst和popstpushst负责插入popst负责删除。插入时往pushst插入。要删除时先将pushst中的元素一个一个移出往popst中导入再从栈顶删除实现先入先出。再要插入时往pushst插入再要删除时先检测popst里面是否还有元素还有就等popst里面删完了再把pushst导入popst继续删。 popst的栈顶相当于队头pushst的栈顶相当于队尾。 图示 代码
#includestdio.h
#includeassert.h
#includestring.h
#includestdlib.h
#includestdbool.h// 下面是定长的静态栈的结构实际中一般不实用所以我们主要实现下面的支持动态增长的栈
//静态栈
typedef int STDataType;
#define N 10
typedef struct Stack
{STDataType _a[N];int _top; // 栈顶
}Stack;//动态栈 支持动态增长的栈
typedef int STDataType;
typedef struct stack
{STDataType* a;int top;//栈顶int capacity;//容量
}ST;//初始化栈
void STInit(ST* ps);
//销毁栈
void STDestroy(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//获取栈顶元素
STDataType Sttop(ST* ps);
//获取栈中有效元素
int STSize(ST* ps);
//检测栈中是否为空
bool STEmpty(ST* ps);//̬ջʼ
void STInit(ST* ps)
{assert(ps);ps-a NULL;ps-capacity 0;//ps-top 0;//ջ
}
//
void STDestroy(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-top ps-capacity 0;
}
//
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps-top ps-capacity){int newCapacity ps-capacity 0 ? 4 : ps-capacity * 2;STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType) * newCapacity);if (tmp NULL){perror(realloc fail);exit(-1);}ps-a tmp;ps-capacity newCapacity;}ps-a[ps-top] x;ps-top;
}//ɾ
void STPop(ST* ps)//, STDataType x
{assert(ps);assert(ps-top 0);--ps-top;
}STDataType STTop(ST* ps)
{assert(ps);assert(ps-top 0);return ps-a[ps-top - 1];
}int STSize(ST* ps)
{assert(ps);return ps-top;
}bool STEmpty(ST* ps)
{assert(ps);return ps-top 0;
}typedef struct {ST pushst;ST popst;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj(MyQueue*)malloc(sizeof(MyQueue));STInit(obj-pushst);STInit(obj-popst);return obj;
}void myQueuePush(MyQueue* obj, int x) {STPush(obj-pushst,x);//直接往pushst插入
}int myQueuePop(MyQueue* obj) {int frontmyQueuePeek(obj);STPop(obj-popst);return front;
}int myQueuePeek(MyQueue* obj) {if(STEmpty(obj-popst)){//倒数据while(!STEmpty(obj-pushst)){STPush(obj-popst,STTop(obj-pushst));STPop(obj-pushst);}}return STTop(obj-popst);
}bool myQueueEmpty(MyQueue* obj) {return STEmpty(obj-popst)STEmpty(obj-pushst);
}void myQueueFree(MyQueue* obj) {STDestroy(obj-popst);STDestroy(obj-pushst);free(obj);
}
