目录
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.提交结果
