L20.【LeetCode笔记】用栈实现队列(方法2)(★详解★)

目录

1.实现方法

过程详解

1.执行push 1->push 2->push 3->push 4

2.执行第一个pop

 3.执行第二个pop

4.执行push 5->push 6

​编辑

 5.执行pop->pop->pop

代码实现

队列创建函数myQueueCreate

入队函数myQueuePush

出队函数myQueuePop

返回队列开头元素的函数myQueuePeek

判断队列是否为空的函数myQueueEmpty

队列销毁函数myQueueFree

2.提交结果

---

解决L19.【LeetCode笔记】用栈实现队列(方法1)遗留未讲的方法2

1.实现方法

过程详解

实现方法和方法1有较大的不同,一个栈用于入(push)数据,另一个栈(pop)用于出数据

对于"push 1->push 2->push 3->push 4->pop->pop->push 5->push 6->->pop->pop->pop"过程画图分析

初始化时两个栈都为空,随便选一个压入数据

1.执行push 1->push 2->push 3->push 4

2.执行第一个pop

按队列的性质,需要pop 1,则需要将2,3,4拿出放到另一个栈中

 3.执行第二个pop

按队列的性质,需要pop 2,此时直接对右侧栈pop

4.执行push 5->push 6

此时不能将5和6压入第二个栈,会改变队列的顺序,因此需要压入左侧的栈

 5.执行pop->pop->pop

前两个pop将3和4出队

最后一次pop需要将5和6压入右侧的栈才能以正确的顺序出队

通过分析,可以得出方法2的核心在:一个栈用于入数据,另一个栈用于出数据

代码实现

由过程详解可知,可以专门定义一个栈用于入数据,另一个栈用于出数据

typedef struct 
{ST pushst;ST popst;
} MyQueue;

队列创建函数myQueueCreate

MyQueue* myQueueCreate()
{MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));if (obj==NULL){perror("malloc");return NULL;}STInit(&obj->pushst);STInit(&obj->popst);return obj;
}

入队函数myQueuePush

void myQueuePush(MyQueue* obj, int x) 
{STPush(&obj->pushst,x);
}

出队函数myQueuePop

这里要分类讨论,由"过程详解"可知,要判断栈popst是否为空,如果为空,需要将pushst的数据(前提是有数据,因此还要再做一次判断,即嵌套判断)全部拿过来,记录栈顶元素后再pop

int myQueuePop(MyQueue* obj) 
{if (STEmpty(&obj->popst)){while(!STEmpty(&obj->pushst)){STPush(&obj->popst,STTop(&obj->pushst));STPop(&obj->pushst);}}int front=STTop(&obj->popst);STPop(&obj->popst);return front;
}

返回队列开头元素的函数myQueuePeek

和myQueuePop类似,返回popst的栈顶元素,如果popst为空,则将需要将pushst的数据拿过来

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);
}

这里myQueuePop的第二种写法,让代码更简洁

int myQueuePop(MyQueue* obj)
{int front=myQueuePeek(obj);STPop(&obj->popst);return front;
}

注意:使用myQueuePeek前要声明否则报错!!!

判断队列是否为空的函数myQueueEmpty

当两个栈都为空时,队列才为空

bool myQueueEmpty(MyQueue* obj) 
{return STEmpty(&obj->pushst) && STEmpty(&obj->popst);
}

队列销毁函数myQueueFree

malloc是怎么开辟的,那队列就是怎么销毁的

结构图

void myQueueFree(MyQueue* obj) 
{STDestory(&obj->pushst);STDestory(&obj->popst);free(obj);
}

2.提交结果