栈和队列LeetCode精彩题目讲解

建议大家最好在电脑上观看。

       OK，好的，未来公司的高级程序员们，你们好，今天我来带着大家一起来研究一下几道栈和队列相关的题目，我们往下看。

一.用队列来实现栈：题目具体的信息如下图所示：

       好了，相信大家都已经看完了，那么，不管大家呢是有思路还是没有思路，现在，我就来为大家讲解一下这道经典的栈和队列有关的题目，虽然现在可能不太会，没事别急，只要看完我下面的分析和讲解之后，相信大家绝对对这道题目有了一个很好的分析。不多说了，精彩来了。

       1.思路分析：

       用队列来实现栈这道题目实际上就是让你使用两个队列来实现一个栈，也就是说，让你使用两个先进先出的结构去实现一个先进后出的结构，当我往队列中插入1，2，3，4这四个元素之后，在栈中也要插入这四个数据，当我从队列中删除1这个数据的时候，我也要从栈中将这个对应的数据删除。那么，这道题具体要咋实现，请看下图。

       通过上图我们可以看到，我们向栈中插入了1，2，3，4这四个元素，因为我们想通过队列来实现栈，因此，相对应的，我们也要在队列中插入相应的元素，好的，没错，这样我们就插入完成了，那么，此时大家不妨想一想，如果此时我想要删除掉栈中的一个元素呢？想要删掉栈中的一个元素，那么，就是将栈中的最后一个进来的元素给删掉，也就是将4这个元素给删掉，因为我们是通过队列来实现栈，因此，在栈中删除一个元素，那么相对应的，在队列中也要将对应的元素删除掉，既然我们在栈中删除掉的元素是最后一个进来的元素4，在队列中也要将4这个元素给删除掉，但是队列的特点是先进后出，照这样的话，那么4这个元素按照道理应该是最后一个被删除的，咋办呢？

       接下来，就来给大家讲解一下具体的解题方法：在这道题目中，我们有两个队列，那么我们可以将两个队列都利用起来，我们在执行删除操作的时候，可以先将前三个元素也就是1，2，3这三个元素从第一个队列中依次取出来，依次取出来之后，再将它们依次放到另一个空队列中去，最后再将第一个队列中的4这个元素给删除掉就可以了，综上所述，我们可以明确的了解到，当我们删除元素的时候，必须将这个元素前面的所有元素都放到另一个空的队列中去，只有这样操作，才能在保证在前几个元素不被消除的情况下，将最后一个进入栈的元素给删除掉，以上就是对于栈的删除部分的全部讲解。

       以上两段是对栈的删除部分的操作，那么现在我们来看一下向栈中插入元素是我们应该如何去插，在这里，我们紧接着上述操作进行，如果我们要往栈中在插入一个5这个元素，那么相应的在队列中我们应该往哪一个队列里面插，OK，这里，我们需要简单的进行一个讨论，假如说，我们把5这个元素往空的队列中去插，如下图所示：

此时，我们大家可以明显的从图中看到5已经插入到了另一个空队列中，那此时在删除一个元素，那豪无疑问，肯定是5这个元素被删除，咋删？若使用我们上述的方法肯定是不行，不信的话你可以再看一看上述所描述的方法，别急，既然不能插入到另一个空队列中，那么我们就只能插入到这个不是空的队列中了，如下图所示：

通过上图我们可以看到，将5这个元素插入到不为空的队列中时，我们再想删除一个元素时，也是将前size-1个元素一一将其从其所在的对列中拿出来，并将其在一一放到另一个为空的队列中，这样的话，就可以和前面讲的方法对应上。

       综上所述：我们在这道题里面是用到的方法是，当我们想向队列中插入元素时，将元素插入到不为空的队列当中去，删除元素时，将前size-1个元素一一将其从其所在的对列中拿出来，并将其在一一放到另一个为空的队列中，这样就可完成这道题的一系列操作。

       2.题目实现：

       (1).定义队列：

       既然题目中让我们使用队列来实现栈，首先我们要定义一个栈，代码如下所示：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int QDataType;
// 链式结构：表示队列 
typedef struct QListNode
{
	struct QListNode* _next;
	QDataType _data;
}QNode;
// 队列的结构 
typedef struct Queue
{
	QNode* _front;
	QNode* _rear;
	int _size;
}Queue;
// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);
// 初始化队列 
void QueueInit(Queue* q)
{
	q->_rear = NULL;
	q->_front = NULL;
	q->_size = 0;
}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newQNode = (QNode*)malloc(sizeof(QNode));
	if (newQNode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newQNode->_next = NULL;
	newQNode->_data = data;
	if (q->_rear == NULL)
	{
		q->_front = q->_rear = newQNode;
	}
	else
	{
		q->_rear->_next= newQNode;
		q->_rear = newQNode;
	}
	q->_size++;
}
// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->_size!=0);
	if (q->_front->_next == NULL)
	{
		free(q->_front);
		q->_front = q->_rear = NULL;
	}
	else
	{
		QNode* cur = q->_front->_next;
		free(q->_front);
		q->_front = cur;
	}
	q->_size--;
}
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->_front);
	return q->_front->_data;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->_rear);
	return q->_rear->_data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
	assert(q);
	return q->_size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	assert(q);
	return q->_front == NULL && q->_rear == NULL;
}
// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->_front;
	while (cur)
	{
		QNode* next = cur->_next;
		free(cur);
		cur = next;
	}
	q->_front = NULL;
	q->_rear = NULL;
	q->_size = 0;
}

（温馨提示：上面关于队列实现的一些代码如果大家看不懂的话，可以看我前面发的一些博客，就有队列相关部分的知识。）

       (2).实现题目中的相关操作：

       ①.因为这里是使用两个队列来实现栈，所以这里我们定义两个队列，并将它们都放在一个结构体中（方便传参）：

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->q1), x);
    }    
    else
    {
        QueuePush(&(obj->q2), x);
    }
}

       ④.删除元素，并返回要被删除的元素：

int myStackPop(MyStack* obj) 
{
    Queue*empty=&(obj->q1);      //  }在这里我们采用假设法来找到不为空的那个队列
    Queue*unempty=&(obj->q2);    //  }假设法：就是我们先假设其中一个是我们想要的，  
    if(!QueueEmpty(&(obj->q1)))  //  }另一个不是，在判断其中一个是否满足我们我们
    {                            //  }所假设的内容，若是，则无影响，否则，将他们
        unempty=&(obj->q1);      //  }两个交换即可。
        empty=&(obj->q2);        //  }
    }                            //  }
    while(QueueSize(unempty)>1)
    {
        QueuePush(empty,QueueFront(unempty));//将unempty中的每一个元素都放在empty里面
        QueuePop(unempty);//删除掉unempty中的一个元素
    }
    int top=QueueFront(unempty);
    QueuePop(unempty);
    return top;
}

       ⑤.获取栈顶元素，也就是队列中的最后一个元素：

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

      ⑥.判空：

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

       ⑦.销毁队列：

void myStackFree(MyStack* obj) 
{
    QueueDestroy(&(obj->q1));
    QueueDestroy(&(obj->q2));
    free(obj);
    obj=NULL;
}

       接下来，我们来给大家讲解今天的第二道精彩题目：

二.用栈来实现队列：题目具体的信息如下图所示：

       1.思路分析：用栈来实现队列这道题实际上就是使用两个栈来实现一个队列的功能，也就是说，使用两个先进后出的结构来实现一个先进先出的结构，好的，话不多说，我们现在就来实现。

如上图所示，我们先开始向队列中插入元素，我们先向队列中插入1，2，3，4这四个元素，那么，相应的在栈中也要插入这四个元素，因为两个栈都是空，所以我们在第一次插入的时候一般插入到第一个栈中，如下图所示：

插入完后，紧接着，我们试着删除一个元素，因为是要实现队列，所以我们在这里要删除的是1这个元素，那么相应的，在栈中我们也要将1这个元素删除掉，要想在两个栈中将1这个元素给删除掉就只能将前size-1个元素分别从栈中拿出来，并一一将其放到另一个栈中，然后再将原来的栈中剩下的1这个元素给删掉就可以了，OK，同志们，重点来了，如果此时我还想再插入一个元素，往哪插？相信此刻很多的同学的第一反应都是往另一个空栈中去插，但是同学们去想一想，如果插在另一个空栈中的话，那按照逻辑，我下一个要删除的元素应该是2这个元素，但是事实却不是这样的，如果我们再删除2这个元素呢，按照我们上面的逻辑，栈中就应该变成这个样子了，我再删除一个元素，你会发现问题就来了，按照正常的思路来说，队列中下一个要删除的元素应该是3这个元素，按照我们的逻辑，栈中下一个要被删除的元素是5，这很明显对应不上，所以，从第二次插入元素开始我们就不能在另一个空栈中插，因为只有两个栈，这个不行，我们就只能插入到另一个栈中了，经过我们的实验，发现这种方法是完全可以的。

       综上所述，我们有两个栈，我们为其中一个栈起名叫outstack(出栈)，另一个叫pushstack(入栈)，当我们插入元素时，将插入的元素一律放在outstack栈中，我们删除元素的时候就将前size-1个元素分别从pushstack栈中拿出来，并一一将其放到outstack栈中，然后再将原来的pushstack栈中剩下的1这个元素给删掉，删除后，我们再将所有的元素分别从outstack栈中拿出来，并一一将其放回到原来的pushstack栈中即可。

       2.题目实现：

       (1).定义队列：

既然题目中让我们使用队列来实现栈，首先我们要定义一个栈，代码如下所示：

// 支持动态增长的栈
 
typedef int STDataType;
 
typedef struct Stack
 
{
 
    STDataType* _a;
 
    int _top;
 
    int _capacity;
 
}Stack;
 
// 初始化栈
 
void StackInit(Stack* ps);
 
// 入栈
 
void StackPush(Stack* ps, STDataType data);
 
// 出栈
 
void StackPop(Stack* ps);
 
// 获取栈顶元素
 
STDataType StackTop(Stack* ps);
 
// 获取栈中有效元素个数
 
int StackSize(Stack* ps);
 
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
 
int StackEmpty(Stack* ps);
 
// 销毁栈
 
void StackDestroy(Stack* ps);
 
// 初始化栈
 
void StackInit(Stack* ps)
 
{
 
    assert(ps);
 
    ps->_a = NULL;
 
    ps->_capacity = 0;
 
    ps->_top = 0;//top指向的是栈顶元素的下一个位置
 
}
 
// 入栈
 
void StackPush(Stack* ps, STDataType data)
 
{
 
    assert(ps);
 
    if (ps->_capacity == ps->_top)
 
    {
 
        int _newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
 
        STDataType* tmp =(STDataType*)realloc(ps->_a,sizeof(STDataType) * _newcapacity);
 
        if (tmp == NULL)
 
        {
 
            perror("realloc fail");
 
            return;
 
        }
 
        ps->_a = tmp;
 
        ps->_capacity = _newcapacity;
 
    }
 
    ps->_a[ps->_top] = data;
 
    ps->_top++;
 
}
 
// 出栈
 
void StackPop(Stack* ps)
 
{
 
    assert(ps);
 
    assert(ps->_top > 0);
 
    ps->_top--;
 
}
 
// 获取栈顶元素
 
STDataType StackTop(Stack* ps)
 
{
 
    assert(ps);
 
    assert(ps->_top > 0);
 
    return ps->_a[ps->_top-1];
 
}
 
// 获取栈中有效元素个数
 
int StackSize(Stack* ps)
 
{
 
    assert(ps);
 
    return ps->_top;
 
}
 
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
 
int StackEmpty(Stack* ps)
 
{
 
    assert(ps);
 
    if (ps->_top == 0)
 
    {
 
        return 1;
 
    }
 
    else
 
    {
 
        return 0;
 
    }
 
}
 
// 销毁栈
 
void StackDestroy(Stack* ps)
 
{
 
    assert(ps);
 
    free(ps->_a);
 
    ps->_a = NULL;
 
    ps->_capacity = 0;
 
    ps->_top = 0;
 
}

       (2).实现题目中的相关操作：

       ①.因为这里是使用两个栈来实现队列，所以这里我们定义两个栈，并将它们都放在一个结构体中（方便传参）：

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

       ②.对结构体中的元素进行初始化操作：

MyQueue* myQueueCreate() {
 
    MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));
 
    StackInit(&(obj->popst));
 
    StackInit(&(obj->pushst));
 
    return obj;
 
}

       ③.插入一个元素：

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

       ④.删除掉一个元素，并返回删除元素的值：

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

       ⑤.返回队列开头的元素，也就是返回栈底元素，（注意：这里只是返回，不需要将它删除）。

int myQueuePeek(MyQueue* obj) {
 
    if(StackEmpty(&(obj->popst)))
 
    {
 
        while(!StackEmpty(&(obj->pushst)))
 
        {
 
            STDataType top=StackTop(&(obj->pushst));
 
            StackPop(&(obj->pushst));
 
            StackPush(&(obj->popst), top);
 
        }
 
    }
 
    return StackTop(&(obj->popst));
 
}

       ⑥.判空：

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

       

       接下来，我们来给大家讲解今天的第三道，也就是最后一道精彩题目：

三.设计循环队列：题目具体的信息如下图所示：

       这道题目相较于前两道题目来说难度更上一个档次。

       但是不要紧，今天我来给大家慢慢的分析一下这道题目，这道题的意思其实就是说，设计一个循环队列，这个循环队列的空间是固定的（这里以4个空间为例展开讲解），我们每向我们设计的队列中插入一个元素，那么队列中对应的空间就会少一个，当这个队列中的空间全部都装满的时候，此时，我们就无法向这个队列中再去插入元素了，唯一的方法就是删除掉队列中的第一个元素，将新的元素插入到此队列中的第一个位置即可，再插入一个元素，再删除掉第二个元素的位置，将其插入到第二个元素的位置，以此类推。

       在这道题中，我们使用数组来实现循环队列，为什么不使用单链表？其实在这里使用单链表也是可以的，但是在这道题中，之所以使用数组而不是使用单链表是因为单链表在这里有点太麻烦，这只是相较于本题而言，数组我们可以通过下标快速的访问到其中的元素，换成单链表的话，则需要进行循环来实现对元素的访问，鉴于种种原因，我们确定使用数组，那么我们就来探讨一下

当数组中的空间都被插满元素时，就如上图所示，我来为大家提供一种解决这道题目的方法，我们先定义两个指针，一个指向首元素，另一个指向尾部元素的下一个位置（方便记录数组中的元素个数，因为数组中的元素下标是从0开始的），那么，既然这样的话，我们应该怎么判断数组时空的状态还是满的状态呢？

这是空的情况，

这是满的情况（因为是循环链表，因此尾指针指向第一个位置），通过两幅图片我们可知，当我们建立4个空间的时候，是无法去判断数组是空的还是满的，因此，建立4个空间的方法行不通，那么我们可以尝试一下建立5个空间（这里虽然是开创了5个空间，但是最多只能存放4个元素）？如下图所示：

这是数组中满的情况，(tail+1)%5==head;

这是数组中空的情况，tail==head;经过我们这样的一通操作后，数组中满的情况和空的情况就可以被很好的区分开来了（当然，这里其实也不需要再建立一个空间，还可以使用size来记录数组中的元素个数，逻辑与上文是一样的，大家感兴趣的话可以试着操作一下），接下来我们就可以去实现题目了。

       ①.定义一个结构体，将一些必要的变量全部都放入到其中：

typedef struct {
 
    int head;//定义一个头指针（数组下标）
 
    int tail;//定义一个尾指针（数组下标）
 
    int k;//这里的k是指数组的空间大小，我们要建立的是k+1的数组空间，这里只是简单的表示一下。
 
    int*a;
 
} MyCircularQueue;

       ②.进行结构体中的变量的初始化操作：

MyCircularQueue* myCircularQueueCreate(int k) {
 
    MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
 
    obj->head=0;
 
    obj->tail=0;
 
    obj->k=k;
 
    obj->a=(int*)malloc(sizeof(int)*(k+1));
 
    return obj;
 
}

       ③.判空操作：

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
 
    return obj->head==obj->tail;
 
}

       ④.判满操作：

bool myCircularQueueIsFull(MyCircularQueue* obj) {
 
    return (obj->tail+1)%(obj->k+1)==(obj->head);
 
}

       ⑤.向循环队列插入一个元素，如果成功插入则返回真：

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
 
    if(myCircularQueueIsFull(obj))
 
    {
 
        return false;
 
    }//首先要判满，如果数组是满的，则无法插入元素
 
    obj->a[obj->tail]=value;
 
    obj->tail++;
 
    (obj->tail)%=(obj->k+1);//如果插入的位置是数组中的最后一个空间，则尾指针需要移动到数组中第一个位置（循环队列）。
 
    return true;
 
}

       ⑥.从循环队列中删除一个元素，如果成功删除则返回真：

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
 
    if(myCircularQueueIsEmpty(obj))
 
    {
 
        return false;
 
    }//首先要判空，如果数组是空的，则无法删除元素
 
    obj->head++;
 
    obj->head%=(obj->k+1);//如果删除的位置是数组中的第一一个空间的元素，则尾指针需要移动到数组中最后一个位置（循环队列）。
 
    return true;
 
}

       ⑦.从队首获取元素，如果队列为空，返回 -1 ：

int myCircularQueueFront(MyCircularQueue* obj) {
 
    if(myCircularQueueIsEmpty(obj))
 
    {
 
        return -1;
 
    }//要想获得队首的元素，得判断队首有没有元素，也就是为不为空。
 
    else
 
    {
 
        int front=obj->a[obj->head];
 
        return front;
 
    }
 
}

       ⑧.获取队尾元素，如果队列为空，返回 -1 ：

int myCircularQueueRear(MyCircularQueue* obj){
 
    if(myCircularQueueIsEmpty(obj))
 
    {
 
        return -1;
 
    }//要想获得队尾的元素，得判断队尾有没有元素，也就是为不为空。
 
    else
 
    {
 
        int rear=obj->tail==0?obj->a[obj->k]:obj->a[obj->tail-1];//看尾指针是否尾指针是否在数组中第一个元素的位置，若是的话，则最后一个元素在数组中最后一个空间的位置。
 
        return rear;
 
    }
 
}

       ⑨.队列的销毁：

void myCircularQueueFree(MyCircularQueue* obj) {
 
    free(obj->a);
 
    free(obj);
 
}

       最后，如果大家还有什么疑问的话，可以在评论区发言，谢谢大家的支持。