devbox
AllinToyou
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构】有关栈和队列相互转换问题

作者：AllinToyou | 2024-05-27 19:30:51

赞

踩

【数据结构】有关栈和队列相互转换问题

文章目录

用队列实现栈

Leetcode-225 用队列实现栈
在这里插入图片描述

思路

建立队列的基本结构并实现队列的基本操作

这部分这里就不多说了，需要的可以看笔者的另一篇博客
【数据结构】队列详解(Queue)
就简单带过一下需要实现的功能

#define _CRT_SECURE_NO_WARNINGS 1

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#include<stdbool.h>

typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType val;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);

// 队尾插入
void QueuePush(Queue* pq, QDataType x);
// 队头删除
void QueuePop(Queue* pq);

// 取队头和队尾的数据
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);

//获取队列长度
int QueueSize(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);



  • 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

使用两个队列实现
一个空的来实现操作，一个装数据来存储

我们以几个简单操作来理解一下

  • 栈的以队列实现的基本结构及初始化

因为队列的结构及功能是初始化的条件，在上一步中我们已经实现完成了
所以关于栈的结构只需要一个能够存储两个队列的结构体就行了

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;

  • 1
  • 2
  • 3
  • 4

对于栈的初始化，因为我们要实现离开初始化操作后，两个队列和栈都需要存在，所以我们需要使用malloc为其创建内存

而两栈也是需要额外开辟空间的，这同样是在第一步中完成，这里笔者就不多说了，同样也是由malloc来创建内存的

MyStack* myStackCreate() {
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    return pst;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 尾插

因为要进行一系列操作，所以我们必须确保其中的一个队列为空。在这个基础上，我们可以对已有数据的队列进行操作，去实现功能。

所以我们就只需要判断两个队列中哪个为空，往另一个不为空的队列里加数据就行了

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
  • 尾删

作为一个栈，我们需要实现的是先进后出，所以这里是尾删，关于尾删，我们的想法应该是利用队列中带有的尾插操作，将有数据的队列的数据一个个传到空队列中，最后一个传出的数据就是我们要删的数

我们可以理解下图为尾插过5个数的队列
在这里插入图片描述
利用队列的尾插及头删操作，每将队列1的队头尾插给队列2后，头删队列1，知道队列1仅剩一个数据，两个队列的状态就会如下
在这里插入图片描述
此时我们需要做的是利用队列中自带的取队头数据操作，就可以获得栈所需的栈顶元素，

栈顶对应队尾

然后就是需要理解的重点，我们可以发现如果把上图队列1的队头删除后，队列2就是进行尾删的队列1，这样就实现了栈顶删除的操作

如此一来，也呼应了刚刚我们尾插中，找不为空的队列进行尾插的操作

实现

整个队列实现栈的操作中最难理解的就是尾插和尾删的联系与衔接，这两者的关系一旦理清，别的就是信手拈来，这里笔者就不赘述了，跟栈的原始操作大同小异，代码就放在下面了

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
typedef int QDataType;
typedef struct QueueNode {
    struct QueueNode* next;
    QDataType val;
} 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) {
    assert(pq);

    QNode* cur = pq->phead;
    while (cur) {
        QNode* next = cur->next;
        free(cur);
        cur = 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("malloc newnode fail");
    }
    newnode->val = x;
    newnode->next = NULL;

    if (pq->ptail == NULL) {
        pq->phead = newnode;
        pq->ptail = newnode;
    } else {
        pq->ptail->next = newnode;
        pq->ptail = newnode;
    }
    pq->size++;
}
// 队头删除
void QueuePop(Queue* pq) {
    assert(pq);
    assert(pq->size != 0);

    if (pq->size == 1) {
        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);
    assert(pq->phead);
    return pq->phead->val;
}
QDataType QueueBack(Queue* pq) {
    assert(pq);
    assert(pq->ptail);
    return pq->ptail->val;
}

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* pst = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    return pst;
}

//尾插
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* notempty = &obj->q2;
    if (!QueueEmpty(&obj->q1)) {
        empty = &obj->q2;
        notempty = &obj->q1;
    }

    while (QueueSize(notempty) > 1) {
        QueuePush(empty, QueueFront(notempty));
        QueuePop(notempty);
    }
    int top = QueueFront(notempty);
    QueuePop(notempty);

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

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);

 * int param_2 = myStackPop(obj);

 * int param_3 = myStackTop(obj);

 * bool param_4 = myStackEmpty(obj);

 * myStackFree(obj);
*/

  • 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

用栈实现队列

Leetcode-232 用栈实现队列

在这里插入图片描述

思路

同理，先实现栈的结构设计及相关操作

关于用栈实现队列，我们要做的不同方向是，利用两个栈实现，这两个栈不想上面一样，通过判空来使用，而是直接进行分区，一个用来输入，一个用来输出

栈的相关实现，看笔者的另一篇博客也一样，这里也不多说了

【数据结构】栈详解

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

// 初始化和销毁
void STInit(ST* pst);
void STDestroy(ST* pst);

// 入栈  出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);

// 取栈顶数据
STDataType STTop(ST* pst);

// 判空
bool STEmpty(ST* pst);
// 获取数据个数
int STSize(ST* pst);


  • 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
  • 初始化

同样，我们需要做的也是利用内存分配的方法来实现队列和两个栈的基本结构

初始化两个栈ininin和outoutout，出队直接就往ininin压栈，出队先检查outoutout里面有没有元素，有的话outoutout的栈顶就是队首，否则就先把ininin里面的元素弹出压入到outoutout中。这样就能保证outoutout的栈顶始终都是队首，ininin的栈顶始终都是队尾。


typedef struct {
    ST instack;
    ST outstack;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&pq->instack);
    STInit(&pq->outstack);
    return pq;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 尾插及头删

在上面我们提到过了，我们需要建立一个输入栈和一个输出栈，所以关于尾插，没什么好多讲的，就往输入队列里一直加新元素就行了

至于头删这就很关键了，我们用图来理解，假设尾插几个数据后队列如下
在这里插入图片描述

因为头删我们需要拿到的数据是A，所以我们利用栈的尾插将每个数据插到输出栈中，即
在这里插入图片描述

此时A在栈顶我们可以提取出来或者删除

如果只是一般逻辑的话，我们大可将这个输出栈的数据倒回输入栈，然后重复原来操作，这其实是可以的，但是这会大大提高原来的时间复杂度，从而降低效能

那么怎么改呢

假设我们不倒回，而是直接往输入栈中加入数据，其实可以发现，输出栈的栈底其实连着的输入栈的栈底，即

在这里插入图片描述
因此，我们不用再倒回输出栈，只需要在需要利用栈顶元素时判断输出栈是否为空，如果为空就将输入栈的数据补充给输出栈就行了

实现

typedef int STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

// 初始化和销毁
void STInit(ST* pst);
void STDestroy(ST* pst);

// 入栈  出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);

// 取栈顶数据
STDataType STTop(ST* pst);

// 判空
bool STEmpty(ST* pst);
// 获取数据个数
int STSize(ST* pst);

// 初始化和销毁
void STInit(ST* pst)
{
	assert(pst);

	pst->a = NULL;
	// top指向栈顶数据的下一个位置
	pst->top = 0;

	// top指向栈顶数据
	//pst->top = -1;

	pst->capacity = 0;
}

void STDestroy(ST* pst)
{
	assert(pst);

	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}

// 入栈  出栈
void STPush(ST* pst, STDataType x)
{
	assert(pst);

	// 扩容
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		pst->a = tmp;
		pst->capacity = newcapacity;
	}

	pst->a[pst->top] = x;
	pst->top++;
}

void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);

	pst->top--;
}


// 取栈顶数据
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);

	return pst->a[pst->top - 1];
}

// 判空
bool STEmpty(ST* pst)
{
	assert(pst);

	return pst->top == 0;
}

// 获取数据个数
int STSize(ST* pst)
{
	assert(pst);

	return pst->top;
}

//初始化两个栈ininin和outoutout，出队直接就往ininin压栈，出队先检查outoutout里面有没有元素，有的话outoutout的栈顶就是队首，否则就先把ininin里面的元素弹出压入到outoutout中。这样就能保证outoutout的栈顶始终都是队首，ininin的栈顶始终都是队尾。
typedef struct {
    ST instack;
    ST outstack;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&pq->instack);
    STInit(&pq->outstack);
    return pq;
}

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

void inTOout(MyQueue* obj)
{
    while(!STEmpty(&obj->instack))
    {
        STPush(&obj->outstack, STTop(&obj->instack));
        STPop(&obj->instack);
    }
}
int myQueuePop(MyQueue* obj) {
    if(STEmpty(&obj->outstack))
    {
        inTOout(obj);
    }
    int ret = STTop(&obj->outstack);
    STPop(&obj->outstack);
    return ret;
}

int myQueuePeek(MyQueue* obj) {
    if(STEmpty(&obj->outstack))
    {
        inTOout(obj);
    }
    int ret = STTop(&obj->outstack);
    return ret;
}

bool myQueueEmpty(MyQueue* obj) {
    return STEmpty(&obj->instack) && STEmpty(&obj->outstack);
}

void myQueueFree(MyQueue* obj) {
    STDestroy(&obj->instack);
    STDestroy(&obj->outstack);
    free(obj);
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/

  • 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
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/633662
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号