您的当前位置：首页 leetcode解题 - #用栈实现队列 #用队列实现栈 #循环队列

leetcode解题 - #用栈实现队列 #用队列实现栈 #循环队列

来源：爱go旅游网

文章目录

前言

路漫漫其修远兮，吾将上下而求索；

一、用栈实现队列

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

显然，获取队列的队头中的数据过程：

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 的题目链接(按照上述的分析顺序)：

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文