• 【数据结构与算法】栈和队列

    🐱作者：一只大喵咪1201
    🐱专栏：《数据结构与算法》
    🔥格言：你只管努力，剩下的交给时间！
    图

    栈和队列

    在前面本喵已经介绍了顺序表以及链表，接下来本喵继续介绍两种新的数据结构，栈和队列。

    🍗栈

    栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

    要了解栈就必须先知道栈的俩个最主要的操作：

    1. 压栈(Push)
      图
      其中，栈底在栈创建好以后就存在了，而且不会随着栈中数据的出入而变化。
      栈顶是随着数据的进栈和出栈变化的，栈顶始终指向栈中最后进来的一个元素。
      当栈为空的时候，栈底和栈顶是重合的，当有数据压栈后，栈顶就会随之向上生长。

    2. 出栈(Pop)
      图
      在经过出栈操作后，栈的数据个数减少，栈顶也向下移动。

    压栈和出栈都是操作的栈中的最后一个元素，而栈顶始终都指向这个元素。

    所以，栈对于数据的进出遵循后进先出的原则（Last In First Out）

    图

    注意：
    这里的栈是一种数据结构，和我们之前说的系统栈不是一回事，可以理解为，这里的栈是数据结构这门课中的一种概念，而系统栈是内存管理这门课中的概念，它们名字虽然相同，但并不是一个东西。

    🥩接口实现

    同样的，栈也有很多接口，接下来本喵给大家演示一下如何用C语言实现。

    我们在前面知道了顺序表和链表俩种数据结构，绝大多数的数据结构都采用这俩种方式在内存中存储，那么，栈采用顺序表和链表哪种结构比较好呢？

    通过前面对栈的描述我们知道，压栈和出栈属于尾插和尾删，而我们通过前面的学习知道，顺序表尾插尾删的效率比单链表高很多，而且顺序表也适合高频率的访问，所以我们这里采用顺序表的结构也就是数组来实现栈。

    首先我们创建一个结构体

    typedef int STDateType;

typedef struct Stack
{
	STDateType* data;
	int top;//栈顶
	int capacity;//容量
}ST;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 变量top是记录栈顶的
    • 变量capacity是记录栈的容量的
    1. 栈的初始化
    //栈的初始化
void StackInit(ST* ps)
{
	assert(ps);

	ps->capacity = 0;//容量初始化为0
	ps->data = NULL;//顺序表为空
	ps->top = 0;//栈顶为空
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    栈是用户自己创建的结构体类型，在初始化的时候，要将栈初始化为空，此时栈中没有任何数据，所以将容量，栈顶已经数组都置为空

    1. 打印栈
    //打印栈
void StackPrint(ST* ps)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->top; i++)
	{
		printf("%d -> ", ps->data[i]);
	}
	printf("\n");
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    该接口只是为了我们在调试的时候使用方便而写的，没有太大的意义。

    1. 栈的摧毁
    //栈的摧毁
void StackDestroy(ST* ps)
{
	assert(ps);
	//释放
	free(ps->data);
	ps->data = NULL;
	//容量和栈顶置0
	ps->capacity = ps->top = 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    栈是开辟在堆上的动态内存空间，我们在使用完栈以后需要将其释放，也就是将原本栈所用的空间摧毁。

    这里有一点需要注意：

    • 接受的形参是一个结构体类型指针，该结构体变量位于栈区，不需要进行释放
    • 但是该结构体中的数组是开辟在堆区上的动态空间，该结构体中的指针只是存放着数组的起始地址
    • 所以释放的时候要将开辟在堆区上的数组释放掉。
    1. 压栈
    //压栈
void StackPush(ST* ps, STDateType x)
{
	assert(ps);
	//判断是否需要增容
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//新容量是原容量的二倍
		STDateType* tmp = (STDateType*)realloc(ps->data, sizeof(STDateType) * newcapacity);//调整动态内存空间
		//判断是否开辟成果
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->data = tmp;
		ps->capacity = newcapacity;//改变容量
	}
	ps->data[ps->top] = x;//压栈数据
	ps->top++;//栈顶加1
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    在压栈的时候，首先要判断的就是是否需要扩容，由于这里只有压栈涉及到扩容，所以本喵没有将扩容单独写成一个接口。

    扩容：

    • 每次扩容都扩大到原来容量的2倍，如果最开始容量为0，则将起始容量设置成4个元素的大小。
    • 由于初始化的时候将ps->data设为了空，所以在第一次设置初始容量的时候，realloc相当于malloc，这一点在顺序表中有详细的讲解。

    当容量足够的时候，就将数据放在栈顶的位置，栈顶向上加1。

    • 栈顶永远指向最后一个数据的下一个位置
    1. 判断栈是否为空
    //判断栈是否为空
bool StackEmpty(ST* ps)
{
	assert(ps);

	//当栈顶是0的时候，说明栈为空
	return ps->top == 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    这里我们需要详细看一下栈顶的意义。

    图
    初始化时，栈顶的初始值有俩种

    • 栈顶初始值为-1时，当有数据压栈以后，栈顶加1，值变为0，也就是当前数据是数组中的下标，此时栈顶是指向当前数据的。
    • 栈顶初始值为0时，当有数据压栈以后，栈顶加1，值变为1，也就是当前数据所在数组中下一个位置的下标，此时栈顶指向的是当前数据的下一个位置。

    我们这里采用的是第二种初始化方式，所以栈顶的值就代表着栈中数据的个数。

    这里是否会有一个疑问？这么简单的一个逻辑，直接写在代码中就行了啊，就一句话的事，为什么还要单独写一个接口呢？

    那是因为这个栈结构是我们一手写的，我们很清除知道怎么判断它是否为空，那如果是别人写的，而且栈顶的意义也和我们这里的不一样，那么此时我们就不知道怎么用一句话来判断是否为空了。
    此时就需要使用接口来判断，我们只需要知道它的参数以及结果是什么，至于到底是怎么实现的，和我们没有关系，这就是我们通常所说的高内聚，低耦合。

    1. 出栈
    //出栈
void StackPop(ST* ps)
{
	assert(ps);

	assert(!StackEmpty(ps));//确保栈是非空的

	ps->top--;//栈顶减小1
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    出栈时，直接将栈顶的值减小1就可以，不用释放该空间，因为栈顶的值已经被改变，该空间不会被访问到，或者会被覆盖掉。

    但是出栈之前必须判断一下栈是否为空，如果是空的话是无法出栈的。

    1. 取栈顶元素
    //取栈顶元素
STDateType StackTop(ST* ps)
{
	assert(ps);

	assert(!StackEmpty(ps));//确保栈不为空

	return ps->data[ps->top - 1];//取出数组中的最后一个元素
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    取栈顶元素只是获得栈顶的值，栈中的数据不会被改变，它不是出栈，相当于访问数组的最后一个元素。

    由于栈顶指向的是栈中最后一个元素的下一个位置，所以通过数组访问时，要将栈顶的值减1。

    同样需要判断栈是否为空，栈为空的时候是不能取数据的。

    1. 求栈中数据的个数
    //求栈中数据个数
int StackSize(ST* ps)
{
	assert(ps);

	return ps->top;//栈顶的大小就代表着栈中元素的个数
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    通过前面的分析我们知道，栈顶的值就表示栈中元素的个数，所以直接返回栈顶的值就可以。

    以上便是栈的实现，在学习过顺序表以后，栈的实现其实是很简单的，而且栈在定义就是规定了只有压栈和出栈俩种操作。

    🍗队列

    栈介绍完了，接下来本喵介绍一种个栈逻辑相反的数据结构——队列。

    队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。

    • 入队列：进行插入操作的一端称为队尾
    • 出队列：进行删除操作的一端称为队头

    图
    队列只能从队尾插入数据，从队头删除数据，队列具有先进先出FIFO(First In First Out) 的特点。

    队列同样有俩种可以供我门选择的实现方式，一种是用顺序表，另一种是用链表，那么使用哪种比较合适呢？

    入队列是尾插，出队列是头删，通过前面的学习我们知道，如果是用顺序表的话，在进行头删的时候，需要将删除数据后的所以数据整体向前移动一位，效率是比较低下的，所以我们这里采用链表的方式来实现队列。

    同样，如果采用单链表的话，进行尾插的时候，还要寻找链表的尾，效率也比较低，我们这里为了避免结构复杂，不使用带头双向循环链表，仍然使用单链表，再增加一个尾指针以便数据进行尾插。

    图
    空队列的时候，链表的头指针和尾指针都是指向空的。

    图
    当在队列中插入第一个元素后，头指针Front指向的是该元素，尾指针指向的也是该元素。

    图
    当有多个数据插入的时候，Front同样指向的第一个元素，也就是队列的头，而尾指针Back指向的是队列中的最后一个元素。

    图
    当有数据出队列时，尾指针保持不动，头指针指向第二个元素，第一个元素所在的节点释放掉。

    上面就是队列的整个操作过程，下面我们来实现一下它的各个接口。

    🥩接口实现

    首先我们需要创建队列的结构，由于我们使用的是链表的形式来实现队列，所以首先需要节点类型的结构体

    typedef int QDataType;

typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    这是用来存放具体数据的，是开辟在堆区上的动态空间。

    还需要一个管理队列的结构体，其中就有队列的头指针和尾指针，以及队列中元素的个数。

    typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    其中头指针永远指向队列的头，用来让数据出队列，也就是头删，位置在永远指向最后一个节点，用来插入数据，size记录队列中数据的个数。

    1. 队列的初始化
    //队列的初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	//头指针和尾指针头初始化为空
	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;//元素个数初始化为空
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    最开始队列中是没有任何元素的，所以我们将头指针和尾指针都指向空，元素个数置为0，此时还没有在堆区上创建节点。

    1. 队列的摧毁
    //队列的摧毁
void QueueDestroy(Queue* pq)
{
	assert(pq);
	//指向队列链表中的当前位置
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* del = cur;//记录删除的节点位置
		cur = cur->next;//指向下一个节点
		free(del);//释放
	}
	pq->head = pq->tail = NULL;//删除完以后将头指针和尾指针置空
	pq->size = 0;//数据个数清0
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    在使用完队列以后，必须将动态内存空间释放掉，也就是摧毁队列。
    通过指向当前节点的指针，从第一个循环到最后一个迭代着释放，最后要将头指针尾指针以及元素个数保持和初始状态一致。

    1. 队列的打印
    void QueuePrint(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	printf("head <- ");
	while (cur)
	{
		printf("%d <- ", cur->data);
		cur = cur->next;
	}
	printf("tail\n");
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    打印队列同样是为了调试的时候更加方便，只需要一个简单的迭代就可以实现。

    1. 入队列（尾插数据）
    void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	//在堆区上开辟一个新的节点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	//判断是否开辟成功
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}

	newnode->data = x;//新节点插入值
	newnode->next = NULL;//新节点的下一个指向空
	//如果插入的是第一个节点
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;//头指针和尾指针都指向第一个节点
	}
	//插入的不是第一个节点
	else
	{
		pq->tail->next = newnode;//尾指针的next指向新的节点，链接起来
		pq->tail = newnode;//尾指针指向新节点，也就是向后迭代
	}
	pq->size++;//数据个数加1
}

    • 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
    • 新节点创建成功以后，将节点中的值插入，由于插入的节点就是最后一个节点，所以将next指针指向空，保证队列的链表结构正常结束。
    • 如果插入的是第一个元素，需要将头指针和尾指针都指向该节点
    • 插入的不是第一个节点，则需要新节点和原来的链表链接起来，也就是原本的尾指针的next指向新节点，再迭代，将尾指针指向新节点。
    • 插入成功将数据个数加1

    注意
    图
    最后在新节点创建成功以后就进行复杂和next指针指向空，因为后面指针的指向关系会变的混乱。

    1. 判断队列是否为空
    //判断队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	//头指针和尾指针都指向空的时候，队列为空
	return pq->head == NULL && pq->tail == NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    当队列为空的时候，头指针和尾指针都是指向空的，和初始化状态一样。

    1. 出队列
    void QueuePop(Queue* pq)
{
	assert(pq);

	assert(!QueueEmpty(pq));//确保队列不为空

	//队列中如果仅有一个元素
	if (pq->head->next == NULL)
	{
		free(pq->head);//释放删除掉该元素
		pq->head = pq->tail = NULL;//头指针和尾指针置空
		pq->size = 0;//元素个数置0
	}
	//队列中有多个元素
	else
	{
		QNode* del = pq->head;//记录要删除的节点
		pq->head = pq->head->next;//头指针指向下一个节点
		free(del);//释放删除节点
		pq->size--;//元素个数减1
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 出队列的时候，首先要判断是队列是否为空，同样是通过判空的接口实现的
    • 队列不为空还需要判断队列中是否只有一个元素，只有一个元素且被删除以后，头指针和尾指针都需要指向空，同时个数也要置为0。
    • 如果是正常的删除，只需要是否头指针指向的节点，并且改变指向关系即可。
    1. 取队头数据
    //取队头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//防止队列为空
	return pq->head->data;//取出队头数据
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    同样要保证队列是不为空的，然后取出队首的数据，这和出队列是不一样，这里仅是获取队首的数据，并不改变队列的结构。

    1. 取队尾数据
    //取队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//防止队列为空
	return pq->tail->data;//取出队尾数据
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    和取队首数据的逻辑是一样的，只是这里操作的是尾指针。

    1. 求队列中数据个数
    int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;//直接返回个数
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    直接返回结构体中记录的个数即可。

    以上便是队列的实现过程，在学习过链表以后，队列的实现还是很简单的，在使用中，队列使用的结构不一定是链表，也可以是数组，要具体情况具体分析。

    🍗栈和队列OJ习题

    趁热打铁，我们来几个栈和队列的练习题。

    🥩1. 有效的括号

    习题链接

    题目描述：
    图
    分析：
    图

    思路：

    • 将字符串中的括号遍历
    • 左括号入栈，包括‘（’，‘{’，‘[’，这些括号
    • 右括号与栈顶比较，包括‘）’，‘}’，‘]’，这些括号
    • 每次一遇到右括号就和栈顶的进行比较，然后将栈顶中的括号出栈，以便下一对括号的比较

    代码实现：

    bool isValid(char * s){
    ST st;//创建栈
    StackInit(&st);//栈进行初始化

    while(*s)
    {
        //选出左括号
        if(*s=='('||*s=='{'||*s=='[')
        {
            StackPush(&st,*s);//入栈
        }
        //选出右括号
        else
        {
            //如果栈为空，说明匹配出现错误
            if(StackEmpty(&st))
            {
                StackDestroy(&st);//摧毁栈
                return false;//不匹配，返回假
            }
            char top = StackTop(&st);//取栈顶括号
            StackPop(&st);//出栈，删除该括号
            //判断括号是否匹配
            if((*s==')'&&top!='(')
            ||(*s=='}'&&top!='{')
            ||(*s==']'&&top!='['))
            {
                StackDestroy(&st);//摧毁栈
                return false;//不匹配，返回假
            }
        }
        s++;//指向下一个括号
    }

    //栈不为空，说明数量不匹配
    bool flag = StackEmpty(&st);
    StackDestroy(&st);//摧毁栈

    return flag;
}

    • 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

    图
    这里使用到的栈的接口就是我们上面实现好的，由于OJ练习中我们是用的C语言的，没有提供对应的接口，所以需要我们把实现好的栈结构全部复制到OJ页面上
    图
    就类似于这样，全部复制上去，我们在下面的要写代码的函数中直接运用就可以。

    注意：
    图
    括号的匹配必须是左边是左括号，右边是右括号，如果出现了左边是右括号，那么在程序中红色框内，栈中元素就是空，直接判假。

    图

    • 如果执行到最后，栈不为空，说明里面右括号没有被出栈，那么括号的数量就是不匹配的，直接返回假
    • 亦或者给的就是一个空的数组，在这里会直接返回真。

    🥩2. 用队列实现栈

    习题链接

    题目描述：
    图
    分析：
    图
    假设我们现在有一组数，1 2 3 4 5存放在队列中，如上图所示

    用这组数对比栈和队列特性

    • 栈：
      出栈时顺序是：5 4 3 2 1
      压栈后顺序是：1 2 3 4 5 6
    • 队列：
      出队列时顺序是：1 2 3 4 5
      进队列是顺序是：1 2 3 4 5 6

    我们现在要通过队列来实现栈，那么此时存在的问题就是怎么做到将队列像栈一样是先进后出的。

    我们通过俩个队列来实现：

    图
    图是上面俩个队列变化后的结果

    • 将原本队列中的数据挨个出队列后再插入另一个空队列，直到原队列中只留下一个数据
    • 将原队列中剩下的那一个数据出队列就相当于出栈，达到了先进后出的目的
    • 当有数据插入的时候，插入到这俩个队列中不为空的队列即可。

    代码实现：

    typedef struct {
    //创建俩个队列
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() {
    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));//为了不消失，开辟动态空间
    if(obj == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    //初始化俩队列
    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* NoEmpty=&obj->q2;
    //找出真正的空队列
    if(!QueueEmpty(Empty))
    {
        Empty=&obj->q2;
        NoEmpty=&obj->q1;
    }
    //搬运数据，直到非空队列只剩下一个数据
    while(QueueSize(NoEmpty)>1)
    {
        //插入数据到空队列
        QueuePush(Empty,QueueFront(NoEmpty));
        //删除非空队列中被插入的数据
        QueuePop(NoEmpty);
    }
    //拿到最后一个数据
    int Pop = QueueFront(NoEmpty);
    //出栈
    QueuePop(NoEmpty);
    return Pop;
}

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

    • 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

    图
    同样需要将我们前面实现的队列全部复制过去，直接使用我们自己写的接口就可以。
    注意：
    图
    这里我们是不知道到底哪个队列是空的，所以需要进行判断，将空的记录单独记录出来直接去使用。

    图
    这里我们用队列中数据的个数来控制将其中一个队列中只留一个数据。

    🥩3. 用栈实现队列

    习题链接

    题目描述：
    图
    分析：
    图
    创建俩个栈，一个为空，另一个将1 2 3 4按顺序压栈，结果如果栈1

    对比栈和队列的特性：

    • 栈：
      出栈时的顺序：4 3 2 1
      压栈时的顺序：1 2 3 4 5
    • 队列：
      出队列时的顺序：1 2 3 4
      进队列时的顺序：1 2 3 4 5

    现在的难点就是要做到将栈中的数据做到就像队列那样先进先出。

    图

    • 将栈1中的数据挨个出栈，并且压栈到栈2中，此时栈2中数据的顺序就反过来了
    • 出栈栈2中的数据就相当于先进先出，符合队列的特性

    那么再有数据压栈后并且出栈呢？

    图

    • 插入数据时要继续压栈到栈1中
    • 当栈2中的数据出栈完后，再将栈1的数据出栈并且压栈到栈2中，继续出栈
    • 如此就实现了队列的先进先出

    综上所述，总体思想就是，栈1负责插入数据，然后将栈1中的数据出栈并且压栈在栈2中，再将栈2出栈就能实现类似队列的先进先出。

    代码实现：

    typedef struct {
    ST pushST;
    ST popST;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));//防止消失，创建动态空间
    //初始化俩个栈，容量，栈顶都是0，数组为空
    StackInit(&obj->pushST);
    StackInit(&obj->popST);

    return obj;
}

void myQueuePush(MyQueue* obj, int x) {
    //数据插入专门用来压栈的栈中
    StackPush(&obj->pushST,x);
}
//将压栈的栈中的数据出栈到用来出栈的栈中
void PushSTTOPopST(MyQueue* obj)
{
    //如果出栈的栈中是空
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            //将数据从栈1出栈到栈2
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
}
int myQueuePop(MyQueue* obj) {
    //将数据从栈1出栈到栈2
    PushSTTOPopST(obj);
    //去栈2中栈顶的数据，也就是队列的队首数据
    int Pop=StackTop(&obj->popST);
    //删除掉栈2中栈顶的数据，也就是队列中队首数据
    StackPop(&obj->popST);
    return Pop;
}

int myQueuePeek(MyQueue* obj) {
    //将数据从栈1出栈到栈2
    PushSTTOPopST(obj);
    //去栈2中栈顶的数据
    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);
}

    • 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

    图
    同样，我们需要将上面自己实现的栈结构的代码全部复制进行，然后直接使用我们自己写的接口。

    注意：
    图
    只要使用到类似于队列的从队首出数据，或者从对数取数据，都需要调用红色框中的函数，将栈1中的数据出栈并且压栈到栈2中。

    🥩4. 设计循环队列

    习题链接

    题目描述：
    图
    分析：
    图
    该题目的意思就是要实现一个这样的循环链表，能存放数据是确定的。

    此时我们就有俩个选择，是用数组实现还是链表实现这样一个结构？虽然叫循环链表，但是本喵前面也讲过，具体用数据还是链表结构是视具体情况而定的。

    这里我们用数组来实现，因为如果使用链表的话，为了结构简单肯定是用单链表，但是单链表的话Back的前一个节点找起来又很麻烦，所以它有一定的缺陷。

    图
    当插入数据并且插满的时候，我尾Back指向最后一个数据的下一个，因为是循环链表，我们必须此时的尾再指向Front的位置。

    图
    那此时就又出现一个问题，连循环链表是空的时候，头和尾在什么位置？

    图
    为了方便，当空的时候，头和尾同样是指向同一个位置的，那么此时怎么分辨是循环链表满了还是空呢？

    一般有俩种方法，

    1. 使用size来记录个数，并且控制Back的循环
    2. 多创建一个空间来区别循环队列的满和空

    图
    这里我们采用第二种，这也是经常用的一种方法，当Back的下一个是Front的时候，说明此时链表是满的，当Back和Front是重合的时候，说明此时链表是空的。

    代码实现：

    typedef struct {
    int* data;
    int Front;
    int Back;
    int N;//这里的N代表的是空间的个数，等于最大数据的个数加1
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
    //防止函数执行结束后消失，创建在堆区上
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->data=(int*)malloc(sizeof(int)*(k+1));//创建k+1一个空间，可以存放k个数据
    //初始链表为空，所以头尾都为0
    obj->Front=0;
    obj->Back=0;
    obj->N=k+1;//这里的N代表的是空间的个数，等于最大数据的个数加1

    return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    //头和尾指向同一位置，说明循环链表为空
    return obj->Front==obj->Back;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->Back+1)%obj->N==obj->Front;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //如果已经满了，则插入失败
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    //将数据进队列，也就是从尾部插入
    obj->data[obj->Back]=value;
    obj->Back++;//尾指针迭代

    //确保循环链表成立
    obj->Back%=obj->N;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    //如果是空列表，则删除失败
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    obj->Front++;

    //确保循环成立
    obj->Front%=obj->N;
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    //如果是空列表，则取数据失败
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->data[obj->Front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    //如果是空列表，则取数据失败
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    
    //if(obj->Back==0)
        //如果Back指向0，那么尾部的数据是最后一个空间里的数据
    //    return obj->data[obj->N-1];
    //else
        //Back指向其他位置，尾部的数据是Back的前一个数据
    //    return obj->data[obj->Back-1];
    return obj->data[(obj->Back-1+obj->N)%obj->N];
}


void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->data);//释放环形链表中的数组
    free(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

    图
    注意：

    图
    这里的N是循环链表空间的个数，其大小比最多数据个数多1个，就是为了方便我们前面分析的判断是空还是满专门开辟的一个空间。

    图
    这一句代码非常的巧妙，避免了判断

    图
    因为要判断是不是满了，所以就判断Back指向的下一个是不是Front，而Back+1后是通过对N取模来和front比较的。

    如果Back不是指向满了以后的下一个空间，那么Back+1再对N取模并不会影响Back加1的值，因为它小于N。

    图
    红色框中的代码如何理解呢？
    图
    将满了的循环链表出队列一个数据，然后再进队列一个数据
    图
    Front和Back的位置就会变成图中所示。

    • 当Back的值是6的时候，已然指向了循环链表的最后一个空间
    • 当再有数据进队列的时候，Back加1机会变成7，此时就会越界访问了，必须循环到0重新开始
    • 所以在进队列以后，将Back与N取模，Back的值就变成了0，回到了0处，并且表示队列满了，队列的头Front的值是1。

    图
    红色框和蓝色框中的代码是等价的，蓝色框中容易理解，本喵来讲下红色框中是怎么实现的。

    图

    队尾的数据的下标是将Back的值减1后得到的值。

    • 当Back的值是0的时候，也就是下标为0的时候，Back-1=-1，属于越界访问了，所以此时用（Back-1+N）%N就得到了6，正好访问到的是队尾的数据。
    • 当Back的值不是0的时候，Back也就不存在越界访问的问题，此时就相当与图中的等式那样，N%N得0。

    🍗总结

    栈和队列总体来说实现起来比较简单，但是在使用中，依靠栈和队列达到目标的方法以及思想是需要重点学习的，希望对各位有所帮助。

  • 相关阅读:
    SAS学习8、9（方差分析、anova过程、相关分析和回归分析、corr过程、reg过程、多元线性回归、stepwise）
    Win11怎么重装显卡驱动程序？Win11显卡驱动怎么卸载重装？
    c语言提高学习笔记——02-c提高03day
    图书推荐管理系统Python+Django网页界面+协同过滤推荐算法
    BUG 修复预估模型
    制造业如何向数字化转型？
    python数据处理—pandas相关函数的使用(持续更新）
    基于SSM的高校宿舍寝室管理系统
    STM32+USB3300复位枚举异常的问题
    带你深入理解泛型
  • 原文地址：https://blog.csdn.net/weixin_63726869/article/details/126225127