扬帆启航于数据结构算法之雅舟旅程，悠然漫步于C++秘境——Leetcode刷题之用栈实现队列，用队列实现栈

在这里插入图片描述

在这里插入图片描述

人无完人，持之以恒，方能见真我！！！
共同进步！！

文章目录

一、用栈实现队列

题目链接：用栈实现队列

还是先来看看题目描述:

在这里插入图片描述

1.大致思路分析

题目的大致含义就是要求我们使用两个栈模拟实现一个队列，要求要支持一个队列的基本操作，这些操作大致都写在上面说明了，关键我们要构思一下怎么用两个栈实现队列的操作

我们都知道栈的特点是先进后出，而队列是先进先出，刚好是相反的，是不是可以从这个方面下手，一个栈和队列是相反的，那么两个栈反复倒腾呢？是不是就能“负负得正”？我们画图来实践一下：

题目的大致含义就是要求我们使用两个栈实现一个队列，要求要支持一个队列的基本操作，这些操作大致都写在上面说明了，关键我们要构思一下怎么用两个栈实现队列的操作

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

根据上面我们画的图例，发现我们的想法确实奏效，虽然一个栈和队列的性质刚好相反，但是经过两个栈的倒腾，刚好负负得正，实现先进先出

但是上面也只是我们的大致思路，我们只讨论了第一次入队列的情况，那么下一次我们入队列要把数据放在哪个栈中呢？

很明显就是栈1，因为栈2现在的顺序是正确的，只要正常的出栈，那么就可以模拟出队列的顺序，所以不能扰乱栈2的顺序

所以我们可以得出，栈1就是我们用来入队列，而栈2则负责出队列操作，当栈2的元素已经出完之后，我们就可以再次把栈1的所有元素再放进栈2，然后再由栈2来出队列，栈1来入队列，如此循环就基本实现了队列的功能，接下来我们就一个函数一个函数分析：

2.用栈实现队列的结构以及初始化

这个新队列的结构在题目中也已经提到，就是两个栈，所以我们定义两个栈作为这个新队列的结构，但是我们注意，根据刚刚的分析我们知道，其中一个栈用来入队列，另一个专门用来出队列，所以我们可以取stpush和stpop来进行分辨，如下：

typedef struct 
{
    ST stpush;
    ST stpop;
} MyQueue;
  • 1
  • 2
  • 3
  • 4
  • 5

初始化方法也很简单，就是我们申请一个这样的节点大小的空间，然后分别调用栈的初始化函数来对两个栈初始化，如下：

MyQueue* myQueueCreate() 
{
    myQueue* pq = (myQueue*)malloc(sizeof(myQueue));
    if(pq == NULL)
    {
        perror("malloc fail\n");
        return NULL;
    }
    STInit(&pq->stpush);//初始化栈1
    STInit(&pq->stpop); //初始化栈2
    return pq;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

3.入队列

在之前我们分析过，两个栈中stpush这个栈用来专门入数据，也就是入队列，所以我们在入队列函数中直接将数据入到stpush栈中，如下：

void myQueuePush(MyQueue* obj, int x) 
{
    STPush(&obj->stpush,x);//入栈1，入队列 
}
  • 1
  • 2
  • 3
  • 4

4.出队列并返回原队头元素

stpop栈用来专门出队列的，实现出队列的逻辑就是，如果stpop栈不为空，那么我们直接就先保存；原队头元素，然后让stpop出栈，然后返回保存的队头

但是如果stpop栈为空，我们就需要先把stpush栈中的元素全部放到stpop栈中，放完之后再进行上面的操作，如下：

int myQueuePop(MyQueue* obj) 
{ 
    if(STEmpty(&obj->stpop))//如果出队列栈为空，就循环入栈
    {
        while(!STEmpty(&obj->stpush))//将入队列栈全部移入stpop
        {
            int top = STTop(&obj->stpush);//取出栈1的栈顶元素压栈
            STPop(&obj->stpush);
            STPush(&obj->stpop,top);//压入栈2
        }
    }
    //通过上面的压栈，stpop栈中已有元素，此时可以出栈
    //栈不为空
    int top = S TTop(&obj->stpop);
    STPop(&obj->stpop);
    return top;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

5.返回队头元素

返回队头元素的逻辑跟上面的出队列操作差不多，如果stpop不为空那么直接返回栈顶元素（队头元素），如果stpop为空那么就先把stpush中的元素移动到stpop栈中，然后再去返回栈顶元素
跟上面出栈操作的唯一区别就是不用出栈，只用去取栈顶元素，如下：

int myQueuePeek(MyQueue* obj) 
{
    if(STEmpty(&obj->stpop))//如果出队列栈为空，就循环入栈
    {
        while(!STEmpty(&obj->stpush))//将入队列栈全部移入stpop
        {
            int top = STTop(&obj->stpush);//取出栈1的栈顶元素压栈
            STPop(&obj->stpush);
            STPush(&obj->stpop,top);//压入栈2
        }
    }
    return STTop(&obj->stpop);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

6.队列判空和队列销毁

我们用两个栈实现的队列要判空的话，必须保证两个栈同时为空队列才为空，否则就不是空，如下：

bool myQueueEmpty(MyQueue* obj) 
{
    return STEmpty(&obj->stpush) && STEmpty(&obj->stpop);
}
  • 1
  • 2
  • 3
  • 4

队列销毁的本质也就是销毁里面的两个栈，但是由于我们的MyQueue这个指针也是我们动态申请的，也要释放掉，然后置空，如下：

void myQueueFree(MyQueue* obj) 
{
    STDestroy(&obj->stpush);
    STDestroy(&obj->stpop);
    free(obj);
    obj = NULL;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

7.完整题解代码

那么关于栈的代码，大家就可以自行拷贝了，在这里拷贝也显得冗余了

typedef struct //定义两个栈的结构
{
   ST stpush;
   ST stpop;
} MyQueue;


MyQueue* myQueueCreate() 
{
    myQueue* pq = (myQueue*)malloc(sizeof(myQueue));
    if(pq == NULL)
    {
        perror("malloc fail\n");
        return NULL;
    }
    STInit(&pq->stpush);//初始化栈1
    STInit(&pq->stpop); //初始化栈2
}

void myQueuePush(MyQueue* obj, int x) 
{
    STPush(&obj->stpush,x);//入栈1，入队列 
}

int myQueuePop(MyQueue* obj) 
{ 
    if(STEmpty(&obj->stpop))//如果出队列栈为空，就循环入栈
    {
        while(!STEmpty(&obj->stpush))//将入队列栈全部移入stpop
        {
            int top = STTop(&obj->stpush);//取出栈1的栈顶元素压栈
            STPop(&obj->stpush);
            STPush(&obj->stpop,top);//压入栈2
        }
    }
    //通过上面的压栈，stpop栈中已有元素，此时可以出栈
    //栈不为空
    int top = S TTop(&obj->stpop);
    STPop(&obj->stpop);
    return top;
}

int myQueuePeek(MyQueue* obj) 
{
    if(STEmpty(&obj->stpop))//如果出队列栈为空，就循环入栈
    {
        while(!STEmpty(&obj->stpush))//将入队列栈全部移入stpop
        {
            int top = STTop(&obj->stpush);//取出栈1的栈顶元素压栈
            STPop(&obj->stpush);
            STPush(&obj->stpop,top);//压入栈2
        }
    }
    return STTop(&obj->stpop);
}

bool myQueueEmpty(MyQueue* obj) 
{
    return STEmpty(&obj->stpush) && STEmpty(&obj->stpop);
}

void myQueueFree(MyQueue* obj) 
{
    STDestroy(&obj->stpush);
    STDestroy(&obj->stpop);
    free(obj);
    obj = NULL;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68

二、用队列实现栈

题目链接：用队列实现栈
还是先来看看题目：

在这里插入图片描述
在这里插入图片描述

1.大致思路分析

这道题和上道题类似，就是使用两个队列实现一个栈的各种操作，这道题要比上一题难，因为在上一题中，我们的思路就是“负负得正”，通过两个栈的互相倒腾就可以还原队列的入队列出队列操作，但是这题不行，我们画个图看看：

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

根据上图的分析，我们知道了完全使用上一题的思路行不通，因为栈通过两次倒腾后，里面的元素顺序会反过来，但是队列通过两次倒腾后，里面元素的顺序还是不变

所以我们要换个思路，我们先来看看出栈的思路： 我们把数据入到队列1中，然后移动到队列2时，不全部挪过去，只留下一个，如图：

在这里插入图片描述

这个时候我们发现队列1中留下的，对应到栈上不正是我们的栈顶元素吗？我们在出栈的时候就可以把队列1中剩下的一个元素出队列，4是最后入栈的，最后第一个出栈，符合我们栈的性质

那么为了保险起见，我们再试一次，先假设我们实现的栈出栈一次，就是把4删掉，让剩下的1,2,3再来模拟一次出栈，如图：

在这里插入图片描述

此时我们发现队列2中留下的正好是新的栈顶元素，让队列2出队列就刚好对应了出栈操作，所以我们的出栈思路大致是正确的

但是我们发现，队列1和队列2是反复倒腾的，没有哪个是专门出栈，哪个专门入栈的，所以我们接下来要分清怎么判断哪个队列什么时候用来入栈，什么时候用来出栈

经过规律总结我们发现，当我们要出栈的时候，有一个队列总是空着的，另一个队列里面才装有数据，我们在操作时就是让不为空的队列将size-1个元素挪到空队列里面去，然后不为空的队列就只剩下一个元素出队列即可模拟实现出栈

那么我们入栈的时候，就是往不为空的队列中去入，所以我们在写入栈和出栈操作时最重要的就时判断出哪个队列空，哪个队列不为空，才方便进行操作，那么接下来我们就一个函数一个函数分析

2.用队列实现栈的结构和初始化

既然题目明确要求我们用两个队列实现一个栈，所以栈的结构实际上就是两个队列，如下：

typedef struct 
{
    Queue q1;//队列1
    Queue q2;//队列2
} MyStack;
  • 1
  • 2
  • 3
  • 4
  • 5

初始化也很简单，首先动态开辟一个MyStack大小的空间，然后就只需要调用队列的初始化方法分别初始化两个队列即可，如下：

MyStack* myStackCreate() 
{
    MyStack* st = (MyStack*)malloc(sizeof(MyStack));
    if(st == NULL)
    {
        perror("malloc fail\n");
        return NULL;
    }
    QueueInit(&st->q1);
    QueueInit(&st->q2);
    return st;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

3.入栈

我们刚刚分析过了，我们入栈就是往不为空的队列中去入，所以我们在入栈时只需要判断一下哪个栈不为空即可，如下：

void myStackPush(MyStack* obj, int x) 
{
    //往不是空栈的栈中放数据,如果都是空那么无所谓
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

4.出栈

我们的出栈操作刚刚也重点分析了，就是先找出哪个是空队列，哪个是非空队列，然后将非空队列中size-1个数据挪动到空队列中，然后非空队列剩下的一个元素就是我们要出栈的元素，题目要求出栈前返回栈顶元素，所以我们创建一个变量用来保存栈顶元素，最后用来返回即可，如下：

int myStackPop(MyStack* obj) 
{
    //先假设q1是空队列，q2是非空队列
    Queue* empty = &obj->q1;
    Queue* noempty = &obj->q2;
    //如果q1非空，那么q2就是空队列，q1为非空队列
    if(!QueueEmpty(&obj->q1))
    {
        empty = &obj->q2;
        noempty = &obj->q1;
    }
    //找到非空队列要移动的size-1的大小
    int sum = QueueSize(noempty) - 1;
    //找到大小后，循环移动
    while(sum--)
    {
        //取出队头元素放入空队列
        int top = QueueFront(noempty);
        QueuePop(noempty);
        QueuePush(empty,top);
    }
    //最后保存非空队列剩余的栈顶元素，就可以出栈了
    int top = QueueFront(noempty);
    QueuePop(noempty);
    return top;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

5.取栈顶元素

按照我们上面的思想，取栈顶元素其实就是取非空队列中的队尾元素，如下：

int myStackTop(MyStack* obj) 
{
    //取栈顶元素，其实就是返回非空队列的队尾元素
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

6.判空和销毁栈

只有两个队列同时为空，我们的栈才为空，如下：

bool myStackEmpty(MyStack* obj) 
{
     return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); 
}
  • 1
  • 2
  • 3
  • 4

销毁栈就只需要调用队列的销毁函数，分别销毁掉两个队列即可，不要忘了最后把整个栈的结构也销毁掉，如下：

void myStackFree(MyStack* obj) 
{
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
    obj = NULL;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

7.完整题解

typedef int QDataType;

//队列中一个节点的定义
//看起来和链表差不多
//但是要注意这里它已经变成队列的节点了
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QueueNode;


//真正使用的对列的定义
typedef struct Queue
{
	int size;
	//指向队头的指针
	QueueNode* phead;
	//指向队尾的指针
	QueueNode* ptail;
}Queue;

//队列的初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->size = 0;
	pq->phead = pq->ptail = NULL;//首尾置空
}

//队列的销毁
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* pcur = pq->phead;
	while (pcur)//循环置空
	{
		QueueNode* del = pcur;//保存释放节点
		pcur = pcur->next;
		free(del);
		del = NULL;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

//队列的节点申请
QueueNode* QueueBuyNode(QDataType x)
{
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail\n");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

//入队列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = QueueBuyNode(x);
	//如果队列中没有节点
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode; 
		pq->size++;
		return;
	}
	//队列中已有节点
	pq->ptail->next = newnode;//链接
	pq->ptail = newnode;//更新尾结点
	pq->size++;
}

//队列判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL;
}

//出队列
void QueuePop(Queue* pq)
{
	assert(!QueueEmpty(pq));
	QueueNode* next = pq->phead->next;
	free(pq->phead);
	pq->phead = next;
	pq->size--;
}

//取队头元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	return pq->phead->data;
}

//取队尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	return pq->ptail->data;
}

//队列的有效元素个数
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

typedef struct 
{
    Queue q1;//队列1
    Queue q2;//队列2
} MyStack;


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

void myStackPush(MyStack* obj, int x) 
{
    //往不是空栈的栈中放数据,如果都是空那么无所谓
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}

int myStackPop(MyStack* obj) 
{
    //先假设q1是空队列，q2是非空队列
    Queue* empty = &obj->q1;
    Queue* noempty = &obj->q2;
    //如果q1非空，那么q2就是空队列，q1为非空队列
    if(!QueueEmpty(&obj->q1))
    {
        empty = &obj->q2;
        noempty = &obj->q1;
    }
    //找到非空队列要移动的size-1的大小
    int sum = QueueSize(noempty) - 1;
    //找到大小后，循环移动
    while(sum--)
    {
        //取出队头元素放入空队列
        int top = QueueFront(noempty);
        QueuePop(noempty);
        QueuePush(empty,top);
    }
    //最后保存非空队列剩余的栈顶元素，就可以出栈了
    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);
    obj = NULL;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201

OK，那么今天的刷题也就到这里了，咱们下一篇再见啦~~

注：本文转载自blog.csdn.net的半盏茶香的文章"https://blog.csdn.net/2401_88325505/article/details/145270943"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！