Leetcode:栈和队列的互相实现
目录
一、用两个队列实现栈
题目：
分析：
代码实现：
二、用两个栈实现队列
题目：
分析：
代码：
总结：核心就在于先进先出和后进先出之间的一个灵活变换，两个栈能够先进先出，而两个队列能够后进先出
一、用两个队列实现栈
题目：
. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。
https://leetcode.cn/problems/implement-stack-using-queues/description/
分析：
首先，我们明确队列有几个接口，初始化、入队、出队、取队头、取队尾、判空、返回有效元素个数、销毁。
题目要求只使用队列标准操作实现栈的四种操作，push、pop、top、empty,实际要求我们主要要能够实现栈存储元素后进先出的特点即可。
那如何利用两个队列实现栈的后进先出呢？
代码实现：
（注释在代码中哦，一些错误的代码我给注释掉的不用管）
//两个队列，一个装元素，另一个用来倒
typedef int QDataType;
typedef struct QListNode
{
struct QListNode* next;
QDataType data;
}QNode;
//定义一个包含队头和队尾的结构体
typedef struct Queue
{
QNode* front;
QNode* rear;
int size;//标记队列中元素个数
}Queue;
void QueueInit(Queue* q)
{
assert(q);
/*QNode* tem = (QNode*)malloc(sizeof(QNode));
if (tem == NULL)
{
perror("malloc");
return;
}*/
q->front = q->rear = NULL;
//q->front->next = NULL;
//q->front->data = 0;
q->size = 0;
}
//通过尾插在队尾入队列
void QueuePush(Queue* q,QDataType x)
{
assert(q);
QNode* tem = (QNode*)malloc(sizeof(QNode));
if (tem == NULL)
{
assert("malloc");
return;
}
if (q->front == NULL)//第一个节点
{
q->front = q->rear = tem;
q->front->data = x;
tem->next=NULL;//别忘了tem的next置空
}
else//第二及以后节点
{
q->rear->next = tem;
q->rear = tem;
q->rear->next = NULL;
q->rear->data = x;
}
q->size++;
// tem->next = NULL;
// tem->data = x;
// if (q->rear == NULL) {
// q->front = q->rear = tem;
// } else {
// q->rear->next = tem;
// q->rear = tem; // 更新tail的指向
// }
// q->size++; // push一下节点个数++
}
//通过头删实现在队头出队列
void QueuePop(Queue* q)
{
assert(q);
assert(q->front);//头指针不为空才存在删
QNode* tem = q->front;
q->front = q->front->next;
if (q->front == NULL)
q->rear = NULL;//避免尾指针变成野指针
free(tem);
q->size--;
}
//获取队列头部元素
QDataType QueueFront(Queue* q)
{
assert(q);
assert(q->front);
return q->front->data;
}
//获取队列尾部元素
QDataType QueueBack(Queue* q)
{
assert(q);
assert(q->rear);
return q->rear->data;
}
//获取队列中有效元素个数
int QueueSize(Queue* q)
{
assert(q);
return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
bool QueueEmpty(Queue* q)
{
if (q->size == 0)
return 1;
else
return 0;
}
//销毁队列
void QueueDestroy(Queue* q)
{
assert(q);
while(q->front)
{
QNode* tem=q->front;
q->front=q->front->next;
free(tem);
}
q->rear=NULL;
q->size=0;
//assert(pq);
// QNode* cur = pq->front;
// while (cur)
// {
// QNode* next = cur->next;
// free(cur);
// cur = next;
// }
// pq->front = pq->rear = NULL;
// pq->size = 0;
}
//上面都是队列的接口，因为此处是用C语言实现，所以得写一下
//接下来才是栈的实现
typedef struct {
Queue q1;//定义两个队列
Queue q2;
} MyStack;
// typedef struct Stack
// {
// int* arr;
// int top;
// int capacity;
// }
//初始化
//在本题由于栈的4种操作的实现完全依赖于队列，对栈的初始化就是对两个队列的初始化
MyStack* myStackCreate() {
MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
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);
}
//出栈
//关键在于找到空队列，将不为空队列的前size-1个元素导到空队列，剩下的那1个元素则头删，从而实现栈的后进先出
int myStackPop(MyStack* obj) {
//假定q1为空队列
Queue* Empty=&obj->q1;
Queue* No_Empty=&obj->q2;
if(!QueueEmpty(Empty))//假定错误则调换
{
Empty=&obj->q2;
No_Empty=&obj->q1;
}
//找到了空队列和不为空队列，接下来实现不为空队列的前size-1个元素导到空队列
while(QueueSize(No_Empty)>1)
{
int tem=QueueFront(No_Empty);
QueuePush(Empty,tem);//先将非空队列的元素压到空队列
QueuePop(No_Empty);//再头头删掉它
}
//不为空队列的最后一个元素删除和返回
int tem=QueueFront(No_Empty);
QueuePop(No_Empty);
return tem;
}
//取栈顶元素
int myStackTop(MyStack* obj) {
// //假定q1为空队列
// Queue* Empty=&obj->q1;
// Queue* No_Empty=&obj->q2;
// if(!QueueEmpty(Empty))//假定错误则调换
// {
// Empty=&obj->q2;
// No_Empty=&obj->q1;
// }
// //找到了空队列和不为空队列，接下来实现不为空队列的前size-1个元素导到空队列
// while(QueueSize(No_Empty)>1)
// {
// int tem=QueueFront(No_Empty);
// QueuePush(Empty,tem);
// QueuePop(No_Empty);
// }
// //不为空队列的最后一个元素返回
// int tem=QueueBack(No_Empty);
// //QueuePop(No_Empty);
// return tem;
if(!QueueEmpty(&obj->q1))
return QueueBack(&obj->q1);
else
return QueueBack(&obj->q2);
}
//判空
bool myStackEmpty(MyStack* obj) {
if(QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2))
return true;
else
return false;
//return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
//销毁栈
//即销毁掉两个队列
void myStackFree(MyStack* obj) {
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
}
二、用两个栈实现队列
题目：
. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/implement-queue-using-stacks/description/
分析：
与上面的思路类似，不同之处在于栈的的特点是后进先出，要实现队列的先进先出的话，除了要将后进的size-1个元素导到另一个栈，将最先进的元素通过出栈pop删除，为了以后能够继续重复此操作，还要再将导过去的元素再导回来。
注意在本题实现队列的出队pop时，最关键的就在于还要导回去！！！！
代码：
typedef int STDataType;
typedef struct Stack
{
STDataType* arr;
int top;//栈中元素个数
int capacity;//栈容量
}Stack;
//扩容函数
void Exp(Stack* p)
{
if (p->capacity == p->top)
{
int new_capacity = p->capacity == 0 ? 4 : p->capacity * 2;//三目运算
STDataType* tem = (STDataType*)realloc(p->arr, new_capacity * sizeof(STDataType));//注意是p->arr，不是p
if (tem == NULL)//对返回值判断
{
perror("realloc");
exit(1);
}
p->capacity = new_capacity;
p->arr = tem;
}
}
//初始化栈
void InitStack(Stack* p)
{
assert(p);
p->arr = NULL;
p->top = 0;
p->capacity = 0;
}
//入栈
void PushStack(Stack* p, STDataType x)
{
assert(p);
Exp(p);
p->arr[p->top] = x;//元素入栈顶
p->top++;
}
//出栈
void PopStack(Stack* p)
{
assert(p);
assert(p->top > 0);//有元素才能出
p->top--;
}
//取栈顶元素
STDataType TopStack(Stack* p)
{
assert(p);
assert(p->top > 0);
return p->arr[p->top - 1];//top相当于size，而数组下标是从0开始的
}
//获取栈中有效元素个数
int SizeStack(Stack* p)
{
assert(p);
return p->top;
}
//判空
bool EmptyStack(Stack* p)
{
assert(p);
//确实栈中元素为0则为true,否则为false
return !p->top;
}
void DestroyStack(Stack* p)
{
assert(p);
if (p->arr)//arr非空指针时才存在释放问题
{
free(p->arr);//释放掉动态申请的内存
p->arr = NULL;//置空
p->capacity = p->top = 0;
}
}
//以上都是栈的接口
//接下来才是用栈实现队列
typedef struct {
Stack s1;//定义两个栈
Stack s2;
} MyQueue;
//对队列的初始化即对两个栈的初始化
MyQueue* myQueueCreate() {
MyQueue* tem=(MyQueue*)malloc(sizeof(MyQueue));
InitStack(&tem->s1);
InitStack(&tem->s2);
return tem;//不要忘了返回！！！
}
//同样，始终保持一个栈为空，而另一个不为空,往不为空的栈压
void myQueuePush(MyQueue* obj, int x) {
if(!EmptyStack(&obj->s1))
PushStack(&obj->s1,x);
else
PushStack(&obj->s2,x);
}
//队列的头删
//
int myQueuePop(MyQueue* obj) {
assert(obj);
//assert((!EmptyStack(&obj->s1) || !EmptyStack(&obj->s2));//两个栈都为空就不存在后面问题
//假设
Stack* Empty=&obj->s1;
Stack* No_Empty=&obj->s2;
if(!EmptyStack(Empty))//假设错误调换
{
Empty=&obj->s2;
No_Empty=&obj->s1;
}
//实现头删
//1.找到先进的元素
while(SizeStack(No_Empty)>1)
{
int tem=TopStack(No_Empty);//取栈顶元素
PopStack(No_Empty);//删除栈顶元素
PushStack(Empty,tem);//压入另一个空栈
}
//2。删除
int tem=TopStack(No_Empty);
PopStack(No_Empty);
//3.将在另一个栈中的元素导回去，以便下次头删
while(!EmptyStack(Empty))
{
int tem=TopStack(Empty);
PopStack(Empty);
PushStack(No_Empty,tem);
}
return tem;
}
//返回队列开头元素
int myQueuePeek(MyQueue* obj) {
assert(obj);
//assert((!EmptyStack(&obj->s1) || !EmptyStack(&obj->s2));//两个栈都为空就不存在后面问题
if(!EmptyStack(&obj->s1))
return (&obj->s1)->arr[0];
else
return (&obj->s2)->arr[0];
}
//判空
bool myQueueEmpty(MyQueue* obj) {
return EmptyStack(&obj->s1) && EmptyStack(&obj->s2);
}
void myQueueFree(MyQueue* obj) {
assert(obj);//销毁栈即销毁队列
DestroyStack(&obj->s1);
DestroyStack(&obj->s2);
}
总结：核心就在于先进先出和后进先出之间的一个灵活变换，两个栈能够先进先出，而两个队列能够后进先出
（栈和队列还不是很清楚的铁铁可以看我前面博客哦）