L18.【LeetCode笔记】用队列实现栈(★逐帧解析各个函数的实现★)

目录

1.题目

代码模板

2.分析

知识回顾

分析

详解队列的push和pop

因此出栈总结为

 代码逐步实现

1.结构体的写法

2.创建栈myStackCreate函数

常见的错误写法

正确写法

解释QueueInit(&pst->q1);的参数为什么这样写

3.入栈函数myStackPush

4.出栈函数myStackPop

麻烦的写法

5.栈顶函数myStackTop

6.栈空判断函数myStackEmpty

7.栈的内存释放函数myStackFree

三个结构体之间的关系图

3.整合的代码

4.提交结果

1.题目

https://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 。

注意：

• 你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
• 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示：

• 1 <= x <= 9
• 最多调用100 次 push、pop、top 和 empty
• 每次调用 pop 和 top 都保证栈不为空

进阶：你能否仅用一个队列来实现栈。

代码模板

typedef struct {
    
} MyStack;


MyStack* myStackCreate() {
    
}

void myStackPush(MyStack* obj, int x) {
    
}

int myStackPop(MyStack* obj) {
    
}

int myStackTop(MyStack* obj) {
    
}

bool myStackEmpty(MyStack* obj) {
    
}

void myStackFree(MyStack* obj) {
    
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/

2.分析

知识回顾

98.【C语言】数据结构之队列

分析

详解队列的push和pop

读题可知:要将两个队列视为栈使用,要满足栈的性质

例如先后push 1,2,3,4,可画图为,注:由队列的性质只能在队尾插入

当要pop时,要先让4出队,则需要让原先的队列做出改变,使4在队头,能最先出队,这样第二个队列(空队列)就能派上用场了

做法:将1,2,3先临时保存在空队列中,(注意待4被pop后,这里不用将1,2,3再恢复回原来的队列,只要满足一个为空队列,另一个为非空队列即可),最后size--

画图为:

由于之前在文章中写过队列的增删查改,因此这里直接借用过来,合理接入LeetCode给的函数中

因此出栈总结为

1.保持一个队列为空,另外一个队列存储数据

2.先将前面的数据临时存储至空队列,再出栈

 代码逐步实现

1.结构体的写法

注意到LeetCode提供的结构体有点特别,是匿名结构体

typedef struct {
    
} MyStack;

由于要实现两个队列,因此要将它们写入匿名结构体中,将两个队列整体视作栈

因此写为

//直接借用98.【C语言】数据结构之队列文章的代码
typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

//接入LeetCode的代码
typedef struct
{
    Queue q1;
    Queue q2;
}MyStack;

2.创建栈myStackCreate函数

注意到LeetCode提供的myStackCreate函数没有参数,返回值为结构体指针变量,因此就要在函数中手动开辟空间并初始化创建结构体

常见的错误写法

MyStack* myStackCreate() 
{
    MyStack st;
    return &st;   
}

函数返回时,栈区的局部变量会发生销毁,导致出现野指针,因此需要在堆区上开辟空间,可以使用malloc函数

正确写法

在myStackCreate嵌入QueueInit函数

MyStack* myStackCreate() 
{
    MyStack* pst=(MyStack*)malloc(sizeof(MyStack));
    if (pst==NULL)
    {
        perror("malloc");
        return NULL;
    }
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    return pst;
}

解释QueueInit(&pst->q1);的参数为什么这样写

1.不能写成QueueInit(MyStack->q1);或者QueueInit(&MyStack->q1);MyStack不是指针,为结构体

2.不能写成QueueInit(pst->q1);

pst->q1访问的是结构体成员变量,不是指针类型,因此不行

3.能不能写成QueueInit(&(pst->q1));?这和QueueInit(&pst->q1);有区别吗?

没有区别,->优先级高于&

4.特别提醒 !!!

不要将QueueInit(&pst->q1);看成QueueInit( (&pst) ->q1);!!!

3.入栈函数myStackPush

直接向非空队列尾插,如果都是非空,随便选一个尾插

这里需要借助之前写过的空队列检查函数QueueEmpty

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}

void myStackPush(MyStack* obj, int x) 
{
    if (!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}

4.出栈函数myStackPop

算法分析:入栈后,两个队列为空和非空,要先找到空和非空队列,再执行出栈(移除并返回top值)

麻烦的写法

//如果q1为非空队列,执行......,否则执行......
if (!QueueEmpty(&obj->q1))
{
    //......
}
else
{
    //......
}

这样会有重复的代码,不够简洁

优化策略:先假定q1为空队列,q2为非空队列,再检验假设,如果不正确就调整,代码写为

int myStackPop(MyStack* obj) 
{
    Queue* empty=&obj->q1;
    Queue* noempty=&obj->q2;
    if (!QueueEmpty(&obj->q1))
    {
        empty=&obj->q2;
        noempty=&obj->q1;
    }
    //......
    
}

移除队列分析

设非空队列有多个节点.其节点个数为size,则要将前size-1个节点临时存储到空队列,显然是个循环,则循环可执行的条件为QueueSize(noempty)>1

循环的内容为:先QueuePush后QueuePop

        QueuePush(empty,QueueFront(noempty));
        QueuePop(noempty);

再将仅剩的节点pop(注意要先保存节点的值,以备返回)

因此代码为

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

int myStackPop(MyStack* obj) 
{
    Queue* empty=&obj->q1;
    Queue* noempty=&obj->q2;
    if (!QueueEmpty(&obj->q1))
    {
        empty=&obj->q2;
        noempty=&obj->q1;
    }
    
    while(QueueSize(noempty)>1)
    {
        QueuePush(empty,QueueFront(noempty));
        QueuePop(noempty);
    }
    int top=QueueFront(noempty);
    QueuePop(noempty);
    return top;
}

5.栈顶函数myStackTop

不需要挪动元素,直接调用QueueBack函数即可,返回非空(这里需要做判断)队列的栈顶元素(是队尾)

int myStackTop(MyStack* obj) 
{
    if (!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }   
}

6.栈空判断函数myStackEmpty

栈为空表明两个队列都为空,直接调用QueueEmpty函数即可

bool myStackEmpty(MyStack* obj) 
{
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

7.栈的内存释放函数myStackFree

注意free的顺序,这里很容易出错!!!,画结构体图会很容易分析

三个结构体之间的关系图

QueueNode、Queue和匿名结构体(这里假设q1为非空队列,q2为空队列)

按什么顺序释放内存?

不能先释放队列,否则会形成野指针

正确顺序:模拟队列的链表(&obj->q1和&obj->q2,可以直接借用之前写过的QueueDestroy函数)-->匿名结构体(obj)

void QueueDestroy(Queue* 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;
}

3.整合的代码

typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

typedef struct
{
    Queue q1;
    Queue q2;
}MyStack;

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

void QueuePush(Queue* pq, QDataType x)
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	
	if (pq->head == NULL)
	{
		assert(pq->tail == NULL);
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}

int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

void QueueDestroy(Queue* 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;
}

MyStack* myStackCreate() 
{
    MyStack* pst=(MyStack*)malloc(sizeof(MyStack));
    if (pst==NULL)
    {
        perror("malloc");
        return NULL;
    }
    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);
    }
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head != NULL);

	QNode* next = pq->head->next;
	free(pq->head);
	pq->head = next;
	if (pq->head == NULL)
		pq->tail = NULL;
	pq->size--;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq); 
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

int myStackPop(MyStack* obj) 
{
    Queue* empty=&obj->q1;
    Queue* noempty=&obj->q2;
    if (!QueueEmpty(&obj->q1))
    {
        empty=&obj->q2;
        noempty=&obj->q1;
    }
    
    while(QueueSize(noempty)>1)
    {
        QueuePush(empty,QueueFront(noempty));
        QueuePop(noempty);
    }
    int top=QueueFront(noempty);
    QueuePop(noempty);
    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);
}

4.提交结果