首页 最新 热门 推荐

  • 首页
  • 最新
  • 热门
  • 推荐

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

  • 25-03-07 15:41
  • 3964
  • 7326
blog.csdn.net

在这里插入图片描述

在这里插入图片描述

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

文章目录

  • 一、用栈实现队列
    • 1.大致思路分析
    • 2.用栈实现队列的结构以及初始化
    • 3.入队列
    • 4.出队列并返回原队头元素
    • 5.返回队头元素
    • 6.队列判空和队列销毁
    • 7.完整题解代码
  • 二、用队列实现栈
    • 1.大致思路分析
    • 2.用队列实现栈的结构和初始化
    • 3.入栈
    • 4.出栈
    • 5.取栈顶元素
    • 6.判空和销毁栈
    • 7.完整题解

一、用栈实现队列

题目链接:用栈实现队列

还是先来看看题目描述:

在这里插入图片描述

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"。版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。如有侵权,请联系我们删除。
复制链接
复制链接
相关推荐
发表评论
登录后才能发表评论和回复 注册

/ 登录

评论记录:

未查询到任何数据!
回复评论:

分类栏目

后端 (14832) 前端 (14280) 移动开发 (3760) 编程语言 (3851) Java (3904) Python (3298) 人工智能 (10119) AIGC (2810) 大数据 (3499) 数据库 (3945) 数据结构与算法 (3757) 音视频 (2669) 云原生 (3145) 云平台 (2965) 前沿技术 (2993) 开源 (2160) 小程序 (2860) 运维 (2533) 服务器 (2698) 操作系统 (2325) 硬件开发 (2492) 嵌入式 (2955) 微软技术 (2769) 软件工程 (2056) 测试 (2865) 网络空间安全 (2948) 网络与通信 (2797) 用户体验设计 (2592) 学习和成长 (2593) 搜索 (2744) 开发工具 (7108) 游戏 (2829) HarmonyOS (2935) 区块链 (2782) 数学 (3112) 3C硬件 (2759) 资讯 (2909) Android (4709) iOS (1850) 代码人生 (3043) 阅读 (2841)

热门文章

106
编程语言
关于我们 隐私政策 免责声明 联系我们
Copyright © 2020-2025 蚁人论坛 (iYenn.com) All Rights Reserved.
Scroll to Top