leetcode解题 - #用栈实现队列 #用队列实现栈 #循环队列
文章目录
前言
一、用栈实现队列
1、分析
2、代码如下:
二、用队列实现栈
1、分析:
三、循环队列
1、分析
2、代码如下:
总结
前言
路漫漫其修远兮,吾将上下而求索;
一、用栈实现队列
1、分析
我们先简单回顾一下栈和队列的基础知识;
栈,是一个数据在一端进、出的数据结构,满足后进先出原则;入栈出栈均在栈顶,如下图所示:
由于栈的结构的特殊性,利用数组实现(也可以使用单链表实现,头结点当作栈顶,但是由于数组的CPU高速缓存命中率更高(相较于单链表),故而用数组实现栈更好);
队列,是一个在固定一端进数据,固定一端出数据的数据结构,满足先进先出的原则;入队列在队头,出队列在队尾,如下图所示:
队列用单链表来实现(用数组实现势必会出现挪动数据的情况,效率低下;队列可以用单链表实现也可以用双链表实现,但是能用单链表实现就用单链表实现,能节约一点空间就节约一点空间);
所要实现的接口函数如下:
用栈实现队列,即用一个一端进出的结构来实现一个固定一端进固定一端出的结构;假设这两个栈分别为st1 与 st2 ,如下图所示:
如果想要将数据1 2 3 ,push到栈(后进先出)中,那么取出来的数据也一定是栈顶的元素3;但对于队列(先进先出)而言,pop 的数据应该是 1;对于栈,应该将栈st1 中的数据依次(从栈顶开始)push 进 st2 中,然后pop st2 中的数据(st2 中栈顶的数据)便是队列所要出数据的顺序;
也就是说将数据放入另外一个栈中该表该数据的顺序,在此栈中pop 数据的顺序才是队列中pop 数据的顺序;
在两栈中一个有数据一个没有数据的情况下(例如上述的例子中),插入数据的时候应该选择哪一个呢?
倘若在push 1 2 3 之后再pop 一次,然后再push 4 5 进入,再将数据全部pop 出,那么“队列”pop数据的顺序为1 2 3 4 5;
经过上图的分析,push 4 5 的时候肯定是不会放在有数据的栈(准确来说是“翻转”过数据的栈中)中的(因为会打乱数据pop的顺序),显然我们可以将栈分功能命名,假设st1 为pushst , st2 为 popst
于是在push 、pop的便有了一下的逻辑:
- 1、push 数据时,将数据放在pushst 中
- 2、pop数据时,先看popst 中是否有数据,popst 中有数据的话先pop它里面的数据;如果popst 为空,但还要pop 数据,便可以将pushst 中的数据(从栈顶开始)“翻转”放到popst 中(注:由于题干中已经说明了不会传空,故而此处没有考虑pushst 中没有数据的情况)
显然,获取队列的队头中的数据过程:
- 1、先看popst 中为不为空,popst 不为空的话,那么该“队列”的队头的数据为popst 的栈顶中的数据
- 2、如果popst 中不为空,那么该“队列”的队头的数据为pushst 中栈底的数据,由于实现栈的时候并没有得到栈底数据的接口函数,故而此处需要转换;既然popst 中为空,完全可以将pushst 中的数据(从栈顶开始)push 放入popst 中,然后popst 栈顶中的数据便为该“队列”的队头的数据;
2、代码如下:
//栈的类型的声明 - 栈用数组实现
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top ;
int capacity;
}ST;
//初始化
void StackInit(ST* pst)
{
assert(pst);
pst->a = NULL;
pst->top = pst->capacity=0;
}
//入栈
void StackPush(ST* pst, STDataType x)
{
assert(pst);
//确保空间足够
if(pst->top == pst->capacity)
{
int newcapacity = pst->capacity==0 ? 4: 2*pst->capacity;
STDataType* tmp = (STDataType *)realloc(pst->a , newcapacity* sizeof(STDataType));
if(tmp==NULL)
{
perror("StackPush realloc");
exit(-1);
}
pst->a = tmp;
pst->capacity = newcapacity;
}
//放置、处理细节
pst->a[pst->top++] = x;
}
//出栈
void StackPop(ST* pst)
{
assert(pst);
assert(pst->top);
pst->top--;
}
//获取栈顶的数据
STDataType StackTop(ST * pst)
{
assert(pst);
assert(pst->top);
return pst->a[pst->top-1];
}
//判空
bool StackEmpty(ST* pst)
{
assert(pst);
return pst->top == 0;
}
//获得栈中数据的个数
int StackSize(ST* pst)
{
assert(pst);
return pst->top;
}
//销毁
void StackDestroy(ST* pst)
{
//释放所有动态开辟的空间
free(pst->a);
pst->a = NULL;
pst->top = pst->capacity = 0;
}
//两个栈实现队列
typedef struct {
ST pushst;
ST popst;
} MyQueue;
//初始化
MyQueue* myQueueCreate()
{
MyQueue * obj = (MyQueue*)malloc(sizeof(MyQueue));
StackInit(&(obj->pushst));
StackInit(&(obj->popst));
return obj;
}
//push
void myQueuePush(MyQueue* obj, int x)
{
StackPush(&(obj->pushst),x);
}
//pop
int myQueuePop(MyQueue* obj)
{
//先判断popst 中有没有数据,为空的话需要将pushst 中的数据push 放入popst 中
if(StackEmpty(&(obj->popst)))
{
while(!StackEmpty(&(obj->pushst)))
{
StackPush(&(obj->popst),StackTop(&(obj->pushst)));
StackPop(&(obj->pushst));
}
}
int top = StackTop(&(obj->popst));
StackPop(&(obj->popst));
return top;
}
//获取“队头”的数据
int myQueuePeek(MyQueue* obj)
{
//先判断popst 中有没有数据,为空的话需要将pushst 中的数据push 放入popst 中
if(StackEmpty(&(obj->popst)))
{
while(!StackEmpty(&(obj->pushst)))
{
StackPush(&(obj->popst),StackTop(&(obj->pushst)));
StackPop(&(obj->pushst));
}
}
int top = StackTop(&(obj->popst));
return top;
}
//判空
bool myQueueEmpty(MyQueue* obj)
{
return (StackEmpty(&(obj->pushst)) && StackEmpty(&(obj->popst)));
}
//销毁
void myQueueFree(MyQueue* obj)
{
//销毁所有动态开辟的空间
StackDestroy(&(obj->pushst));
StackDestroy(&(obj->popst));
free(obj);
obj = NULL;
}
二、用队列实现栈
1、分析:
用队列实现栈,即让先进先出的结构变为后进先出的结构;
我们先来看一下所要实现的接口函数有哪些:
直接来分析:
当要push 1 2 3 的时候,栈中pop数据的顺序为: 3 2 1 ,而队列中pop 数据的顺序为 1 2 3 ,如下图:
如上图所示,想要让队列中的数据pop 的顺序与栈中的数据一致就得让队列中队尾前的数据全部push 到另外一个队列中;由于队列先进先出的特点,数据在队列之间倒来倒去并不会改变数据的顺序,故而每次pop均会进行上述的操作;
如果又要push 数据应该放在哪一个队列中呢?
- 显然,push 的数据放在已经有数据的队列中是比较合适的,倘若两队列均没有数据,任意选择一个放入即可;
由于队列结构的特性,多次挪动数据并不会改变数据的顺序,于是乎想要满足栈的pop 就得pop 队列的队尾,即将队尾前面的数据均push 到另外一个队列中,然后再将原本队尾的数据走到该队列的队头的位置,最后再pop ;如此便可;
获取栈顶的数据:栈顶的数据相当于队列中队尾的数据,先找到不为空的队列直接获取其队尾的数据即可;
2、代码如下:
//队列 - 用单链表实现
//队列的结点的类型声明
typedef int QDataType;
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QNode;
//维护队列的变量
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
//初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = pq->ptail = NULL;
pq->size =0;
}
//销毁
void QueueDestroy(Queue* pq)
{
//释放所有动态开辟的空间 - 结点
QNode* pcur = pq->phead;
while(pcur)
{
QNode* next = pcur->next;
free(pcur);
pcur = next;
}
//置空、置为初始值
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
//入队列
void QueuePush(Queue* pq , QDataType x)
{
assert(pq);
//开辟结点的空间
QNode* newnode = (QNode* )malloc(sizeof(QNode));
if(newnode==NULL)
{
perror("QueuePush malloc");
exit(-1);
}
newnode->data = x;
newnode->next =NULL;
//相当于单链表的尾插,需要分情况讨论
if(pq->phead==NULL)
{
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
//出队列
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->phead);
//由于此处多定义了一个变量,于是也要分情况讨论
if(pq->phead->next ==NULL)//只有一个结点的情况
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else{
QNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
pq->size--;
}
//获取队头的数据
QDataType QueueFront( Queue* pq)
{
assert(pq && pq->phead);
return pq->phead->data;
}
//获取队尾的数据
QDataType QueueBack(Queue* pq)
{
assert(pq && pq->ptail);
return pq->ptail->data;
}
//队列中数据的个数
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
//判空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->size == 0;
}
//两个队列实现栈
typedef struct {
Queue q1;
Queue q2;
} MyStack;
//初始化
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->q2) , x);
}
else
{
QueuePush(&(obj->q1) , x);
}
}
//出栈
int myStackPop(MyStack* obj)
{
//将有数据的队列中的前size-1 个数据push 到另外一个队列中
//然后在pop 原来哪个队尾的数据
//假设法
QNode* empty = &(obj->q1);
QNode* nonempty = &(obj->q2);
if(QueueEmpty(&(obj->q2)))
{
empty = &(obj->q2);
nonempty = &(obj->q1);
}
while(QueueSize(nonempty)>1)
{
//push
QueuePush(empty , QueueFront(nonempty));
//pop
QueuePop(nonempty);
}
int top = QueueFront(nonempty);
QueuePop(nonempty);
return top;
}
//获取栈顶的数据
int myStackTop(MyStack* obj)
{
QNode* empty = &(obj->q1);
QNode* nonempty = &(obj->q2);
if(QueueEmpty(&(obj->q2)))
{
empty = &(obj -> q2);
nonempty = &(obj->q1);
}
return QueueBack(nonempty);
}
//判空
bool myStackEmpty(MyStack* obj)
{
return QueueEmpty(&(obj->q1))&&QueueEmpty(&(obj->q2));
}
//销毁
void myStackFree(MyStack* obj)
{
//释放所有动态开辟的空间
QueueDestroy(&(obj->q1));
QueueDestroy(&(obj->q2));
free(obj);
obj = NULL;
}
三、循环队列
1、分析
对于此题,我们首先需要思考,该循环队列用什么实现合适;
我们先来思考能否用链表实现;必然是会用到循环链表(仅使用单链表实现循环队列是非常麻烦的,因为单链表中的结点(假设该结点存在上一结点与下一结点)只能找到下一结点,找该结点的上一结点是非常麻烦的;当然,可以使用双链表来实现,但是此处还是先考虑"简单、节约空间"的结构是否能解决此问题),循环链表中的尾结点中的next 指向头结点;
(假设用单向循环链表来实现会使用到两个变量phead 与 ptail 分别指向循环队列中的头和尾)
假设题干要求循环队列有 k 个空间,那么我们需要创建多少个结点?
如果就创建k个结点,队列空与满的时候,phead 与 ptail 均会指向同一块空间,不好区分;于是此处有两种方法来解决这个问题:
- 1、方法一:再设置一个变量size 记录队列中数据的个数;
- 那么当 phead == ptail 并且 size 为0 的时候,该队列为空;
- 当phead == ptail 而 size 等于 k 时,该队列为满;
- 2、方法二:多开辟一个结点的空间;
- 当phead == ptail 的时候,该队列为空;
- 当 ptail->next == phead 的时候,该队列为满;
假设此处采用的方法二,多开辟一个空间的形式;
- 那么队列为空,当phead == ptail 时;
- 队列为满,当 ptail->next = phead 时;
- “入队列”(尾插):先判断队列是否还有空间可以存下数据,如果队列不为空,便可以将数据存放在ptail 所指向的结点中,然后ptail 往后走;
- “出队列”(头删):先判断该队列中是否有数据可以出,如果有数据可以出,那么直接让phead 指向下一个结点便可,无需处理空间中的数据;
- 获取队列中队头的数据,就是指针phead 指向的空间中的数据;
- 获取队列中队尾的数据,为ptail 所指向结点的前一个结点中的数据;单链表结构存在的缺陷:不能以时间复杂度为O(1)的方式找到该结点的前一个结点,可以利用循环时间复杂度为O(N);
想要处理找ptail 前一个结点的问题也不难,
- 方式一:利用循环遍历查找,时间复杂度位O(N),效率不高
- 方式二:在每个指针中再增加一个变量用来指向前一个结点,即单向循环链表变成双向循环链表;
我们更倾向于用空间换时间,方式二可以待选,在此之前我们再来分析一下数组是否可以实现循环队列;
如何让数组体现循环?
- 同样此处需要两个“指针” head 与 tail 分别记录“头”的下标与“尾下一空间”的下标;那么循环就得在下标上动手;
同样的,如果题干要求循环队列有 k 个存放数据的空间
那么我们需要创建多少个空间来存放数据?
1、方法一:再设置一个变量size 记录队列中数据的个数;
- 那么当 head == tail 并且 size 为0 的时候,该队列为空;
- 当 head == tail 而 size 等于 k 时,该队列为满;
2、方法二:多开辟一个空间(即总空间有 k+1 个);
- 当head == tail 的时候,该队列为空;
- 当 (tail + 1)%(k+1) == head 的时候,该队列为满;
注:此处需要考虑“回绕”的问题;
为何多开辟一块空间之后,判满的条件为:(tail + 1)% (k+1) == head ?
- 因为多开辟出来了一块空间,那么当该队列满的时候,tail 会指向一块空的空间(tail 指向尾数据的下一个空间),而tail 所指向的这块空间的下一空间为 head 所指向的空间,即 tail + 1 = head ,但是由于存在”回绕“的问题,即 tail 可能指向该数组最后一个空间上,那么 tail + 1 便存在越界的风险,如果该队列为满,那么head 一定指向下标为0 的空间,故而判满条件为:(tail + 1)% (k+1) == head;
当然,还有一种理解方式,tail 永远指向尾数据的下一空间,故而多开辟一块空间,可以作为tail 的缓冲空间进行判断;当tail 走在所开辟空间的最后一个空间的时候,如果tail 还要往前走是要回到下标为0的空间处的,而数组的下标是从0开始的,即有效数据有k 个,会开辟k+1 个空间,那么最后一个空间的下标为 k ,想要让指向下标为k 的tail 向前走一步又回到下标为0的空间去,显然tail = (tail+1)%(k+1); 思考判满也同理,tail(tail 此时指向的空间中没有数据,即尾数据的下一个空间) 先前走一个空间如果遇到head ,那便说明该队列满了,由于tail 存在回绕的情况,故而需要对tail 进行处理,即 (tail+1)%(k+1) == head; 则说明满了;
假设此处也是采用方式二来解决问题:
- 那么判断队列为空:head == tail ;
- 判断队列满: (tail + 1)% (k+1) == head ;
- “入队列”(尾插):先判断队列是否还有空间可以存下数据,如果队列不为空,便可以将数据存放在tail 所指向的空间中,然后tail 往后走(此处需要解决tail回绕的问题, 即 tail = (tail+1)%(k+1));
- “出队列”(头删):先判断该队列中是否有数据可以出,如果有数据可以出,那么直接让head 指向下一个空间便可(此处也需要解决head回绕的问题, 即 head = (head+1)%(k+1)),无需处理空间中的数据;
- 获取队列中队头的数据,首先判断“队列中是否有数据”,队尾数据就是指针head 指向的空间中的数据;
- 获取队列中队尾的数据,首先判断“队列中是否有数据”,队头数据为tail 所指向结点的前一个空间中的数据(此处需要解决tail 回绕的问题 , 即 [(tail-1) + (k+1)]%(k+1) 为tail 指向空间的前一个空间的下标);
相较而言,此处可以使用数组来解决循环队列的问题,故而该题底层便使用数组来解决;
2、代码如下:
//循环队列使用数组实现更好
typedef struct {
int * a;
int head;
int tail;
int k;
} MyCircularQueue;
//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
return obj->head == obj->tail;
}
//判满
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
return (obj->tail+1)%(obj->k+1)==obj->head;
}
MyCircularQueue* myCircularQueueCreate(int k) {
//为循环队列这个封装的结构体开辟空间
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
//为循环队列中底层存储数据的数组开辟空间
obj->a = (int*)malloc(sizeof(int)*(k+1));
//初始化
obj->head = obj->tail = 0;
obj->k = k;
return obj;
}
//入队列
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{
//判断空间是否足够
if(myCircularQueueIsFull(obj))
return false;
//将数据放在tail 所指向的空间中
obj->a[obj->tail]=value;
//tail 向后走,并且解决回绕的问题
obj->tail = (obj->tail+1)%(obj->k+1);
return true;
}
//出队列
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
//判空
if(myCircularQueueIsEmpty(obj))
return false;
//head 向前走并且处理回绕的问题
obj->head = (obj->head+1)%(obj->k+1);
return true;
}
//获取队头的数据
int myCircularQueueFront(MyCircularQueue* obj)
{
//判空
if(myCircularQueueIsEmpty(obj))
return -1;
return obj->a[obj->head];
}
//获取队尾的数据
int myCircularQueueRear(MyCircularQueue* obj)
{
//判空
if(myCircularQueueIsEmpty(obj))
return -1;
return obj->a[(obj->tail-1+obj->k+1)%(obj->k+1)];
}
//销毁
void myCircularQueueFree(MyCircularQueue* obj)
{
//释放所有动态开辟的空间
free(obj->a);
free(obj);
}
注意:
1、在leetcode 中接口函数的实现其底层可能并没有对函数进行声明,如果所要实现的接口函数会调用下面将要实现的接口函数,要将所要被调用的接口函数放在前面,因为函数的实现相当于一次特殊的函数声明;
2、在leetcode 中使用动态开辟空间的函数(malloc、calloc、realloc)可以不进行判空操作,大概率均不会开辟空间失败,故而此处没有进行判空的处理,加上判空的处理也完全没有问题;
总结
三道leetcode 的题目链接(按照上述的分析顺序):
OJ链接https://leetcode.cn/problems/implement-queue-using-stacks/OJ链接https://leetcode.cn/problems/implement-stack-using-queues/OJ链接https://leetcode.cn/problems/design-circular-queue/