C语言-栈和队列

🎯引言

欢迎来到HanLop博客的C语言数据结构初阶系列。在之前的文章中，我们详细介绍了链表及其操作方法。在本篇文章中，我们将深入探讨栈和队列这两种常见的数据结构。栈和队列虽然都是线性数据结构，但它们在数据的存取方式上有着显著的区别。栈是一种后进先出（LIFO, Last In First Out）的数据结构，而队列则是一种先进先出（FIFO, First In First Out）的数据结构。通过理解和掌握这两种数据结构，您将能更有效地管理数据，并为后续更复杂的数据结构和算法的学习打下坚实的基础。让我们一起开始探索栈和队列的奥秘吧！

👓栈和队列

1.栈

1.1栈的概念与结构

栈（Stack）是一种特殊的线性数据结构，它遵循“后进先出”（LIFO, Last In First Out）的原则。这意味着在栈中，最后一个被插入的数据将是第一个被取出的数据。

栈顶和栈底

栈顶和栈底是栈结构中两个重要的概念：

• 栈顶（Top）： 栈顶是指栈中最后一个被插入的元素的位置。在执行压栈（Push）和出栈（Pop）操作时，都是针对栈顶进行的。因此，栈顶是栈中唯一可以进行插入和删除操作的地方。
• 栈底（Bottom）： 栈底是指栈中第一个被插入的元素的位置。在一个空栈中，栈底和栈顶的指针都是相同的。随着新的元素不断压入栈中，栈顶的位置会发生变化，但栈底的位置始终保持不变。

图示结构:

1.2栈的实现

栈的实现主要有两种方式：

1. 数组实现： 使用数组来存储栈中的元素。用数组相较于用链表更优一些
2. 链表实现： 使用链表来存储栈中的元素。

Stack.h源码

//Stack.h文件中
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int StackDataType;
typedef struct Stack
{
	StackDataType* arr;
	int top;
	int capacity;
}Stack;

//初始栈
void StackInit(Stack* ps);

//销毁栈
void StackDestory(Stack* ps);

//入栈
void StackPush(Stack* ps, StackDataType	x);

//判断栈是否为空
bool IsEmpty(Stack* ps);

//取出栈顶元素
StackDataType StackTop(Stack* ps);

//获取链表有效个数
int StackSize(Stack* ps);

//出栈
void StackPop(Stack* ps);

Stack.c源码

#include "Stack.h"

//初始栈
void StackInit(Stack* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}

//入栈
void StackPush(Stack* ps, StackDataType	x)
{
	assert(ps);
	//检查容量

	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		StackDataType* tmp = (StackDataType*)realloc(ps->arr,sizeof(StackDataType) * newcapacity);

		if (tmp != NULL)
		{
			ps->arr = tmp;
			ps->capacity = newcapacity;
		}
		else
		{
			exit(1);
		}
	}

	ps->arr[ps->top] = x;
	ps->top++;
}
//判断栈是否为空
bool IsEmpty(Stack* ps)
{
	return ps->top == 0;
}

//出栈
void StackPop(Stack* ps)
{
	assert(ps);
	assert(!IsEmpty(ps));

	ps->top--;
}

//取出栈顶元素
StackDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!IsEmpty(ps));

	return ps->arr[ps->top - 1];
}

//获取链表有效个数
int StackSize(Stack* ps)
{
	return ps->top;
}

//销毁
void StackDestory(Stack* ps)
{
	assert(ps);
	free(ps->arr);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}

函数实现详解:

1. 初始化栈 StackInit(Stack* ps)

void StackInit(Stack* ps)
{
    assert(ps);
    ps->arr = NULL;
    ps->capacity = ps->top = 0;
}

功能

初始化栈，确保栈的所有成员变量都有合理的初始值。

实现细节

• 使用 assert(ps) 检查传入的栈指针 ps 是否为 NULL。
• 将栈的数组指针 arr 设为 NULL，表示栈中没有元素。
• 将栈的容量 capacity 和栈顶指针 top 都设为 0，表示栈是空的。

2. 入栈 StackPush(Stack* ps, StackDataType x)

void StackPush(Stack* ps, StackDataType x)
{
    assert(ps);
    // 检查容量
    if (ps->top == ps->capacity)
    {
        int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        StackDataType* tmp = (StackDataType*)realloc(ps->arr, sizeof(StackDataType) * newcapacity);

        if (tmp != NULL)
        {
            ps->arr = tmp;
            ps->capacity = newcapacity;
        }
        else
        {
            exit(1);
        }
    }

    ps->arr[ps->top] = x;
    ps->top++;
}

功能

将一个元素压入栈顶，如果栈的容量不足，则动态扩展栈的容量。

实现细节

• 使用 assert(ps) 检查传入的栈指针 ps 是否为 NULL。
• 检查栈的容量是否足够，如果栈顶指针 top 等于当前容量 capacity，表示容量已满。
• 如果容量已满，计算新的容量：如果当前容量为 0，则设为 4，否则容量翻倍。
• 使用 realloc 动态分配新的内存空间，并将原有元素复制到新空间。
• 检查 realloc 是否成功，如果成功则更新栈的数组指针 arr 和容量 capacity，否则退出程序。
• 将新元素放入栈顶位置，并更新栈顶指针 top。

3. 判断栈是否为空 IsEmpty(Stack* ps)

bool IsEmpty(Stack* ps)
{
    return ps->top == 0;
}

功能

检查栈是否为空。

实现细节

• 检查栈顶指针 top 是否为 0，如果是，则表示栈为空，返回 true，否则返回 false。

4. 出栈 StackPop(Stack* ps)

void StackPop(Stack* ps)
{
    assert(ps);
    assert(!IsEmpty(ps));

    ps->top--;
}

功能

从栈顶移除一个元素。

实现细节

• 使用 assert(ps) 检查传入的栈指针 ps 是否为 NULL。
• 使用 assert(!IsEmpty(ps)) 确保栈不为空，否则操作无效。
• 将栈顶指针 top 减一，表示移除了栈顶元素。

5. 取出栈顶元素 StackTop(Stack* ps)

StackDataType StackTop(Stack* ps)
{
    assert(ps);
    assert(!IsEmpty(ps));

    return ps->arr[ps->top - 1];
}

功能

返回栈顶元素的值，但不移除该元素。

实现细节

• 使用 assert(ps) 检查传入的栈指针 ps 是否为 NULL。
• 使用 assert(!IsEmpty(ps)) 确保栈不为空，否则操作无效。
• 返回栈顶元素，即数组中索引为 top - 1 位置的元素。

6. 获取栈中有效元素个数 StackSize(Stack* ps)

int StackSize(Stack* ps)
{
    return ps->top;
}

功能

返回栈中当前元素的个数。

实现细节

• 直接返回栈顶指针 top 的值，因为 top 指示了栈中元素的个数。

7. 销毁栈 StackDestory(Stack* ps)

void StackDestory(Stack* ps)
{
    assert(ps);
    free(ps->arr);
    ps->arr = NULL;
    ps->capacity = ps->top = 0;
}

功能

释放栈的内存，并重置栈的所有成员变量。

实现细节

• 使用 assert(ps) 检查传入的栈指针 ps 是否为 NULL。
• 使用 free 释放栈的数组指针 arr 指向的内存。
• 将 arr 设为 NULL，防止悬空指针。
• 将栈的容量 capacity 和栈顶指针 top 都设为 0，重置栈。

2.队列

2.1队列的概念与结构

队列（Queue）是一种线性数据结构，它遵循“先进先出”（FIFO, First In First Out）的原则。队列中的元素总是从队尾插入，从队头删除。换句话说，第一个插入的元素也是第一个被删除的元素。

队头和队尾

• 队头（Front）： 队头是指队列中最早插入的元素所在的位置。在执行出队（Dequeue）操作时，元素从队头移除。
• 队尾（Rear）： 队尾是指队列中最后插入的元素所在的位置。在执行入队（Enqueue）操作时，元素插入到队尾。

图示:

2.2队列的实现

队列的实现主要有两种方式：

1. 数组实现： 使用数组来存储队列中的元素。出队的时候要移动数据,时间复杂度较高不建议使用
2. 链表实现： 使用链表来存储队列中的元素。出队时间复杂度O(1),下面将会用链表的方式实现队列

Queue.h源码

//Queue.h文件中
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int QueueDataType;
typedef struct QueueNode
{
	QueueDataType x;
	struct QueueNode* next;
}QueueNode;
typedef struct Queue
{
	QueueNode* phead;
	QueueNode* ptail;
	int size;
}Queue;

//初始化队列
void QueueInit(Queue* pq);

//队列判空
bool QueueEmpty(Queue* pq);

//入队列,队尾
void QueuePush(Queue* pq, QueueDataType x);

//出队列,队头
void QueuePop(Queue* pq);

//取队头数据
QueueDataType QueueFront(Queue* pq);

//取队尾数据
QueueDataType QueueBack(Queue* pq);

//队列的有效个数
int QueueSize(Queue* pq);

定义数据类型

typedef int QueueDataType;

功能： 定义队列数据类型。
说明： 使用 typedef 将 int 类型定义为 QueueDataType，这样如果以后需要更改队列存储的数据类型，只需要修改这一行即可。

定义队列节点结构体

typedef struct QueueNode
{
    QueueDataType x;
    struct QueueNode* next;
} QueueNode;

功能： 定义队列节点结构体。
说明：

• QueueDataType x：存储节点数据。
• struct QueueNode* next：指向下一个节点的指针。

定义队列结构体

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

功能： 定义队列结构体。
说明：

• QueueNode* phead：指向队列头部节点的指针。
• QueueNode* ptail：指向队列尾部节点的指针。
• int size：记录队列中元素的个数。

Queue.c源码

//Queue.c文件中
#include "Queue.h"

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

}

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

//入队列,队尾
void QueuePush(Queue* pq, QueueDataType x)
{
	assert(pq);
	QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
	newNode->next = NULL;
	newNode->x = x;

	if (newNode == NULL)
	{
		perror("malloc fail");
		exit(1);
	}

	if ((pq->phead == NULL)&&(pq->ptail==NULL))
	{
		pq->phead = pq->ptail = newNode;
	}
	else
	{
		pq->ptail->next = newNode;
		pq->ptail = pq->ptail->next;
	}

	pq->size++;
}

//出队列,队头
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	QueueNode* del = pq->phead;
	if (pq->phead == pq->ptail)
	{
		pq->phead = pq->ptail = NULL;
		free(del);
		del = NULL;
	}
	else
	{
		pq->phead = pq->phead->next;
		free(del);
		del = NULL;
	}

	pq->size--;
}

//取队头数据
QueueDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->phead->x;
}

//取队尾数据
QueueDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->ptail->x;
}


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

函数实现详解

1. QueueInit

void QueueInit(Queue* pq)
{
    assert(pq);
    pq->size = 0;
    pq->phead = pq->ptail = NULL;
}

功能： 初始化队列，将队列的头指针和尾指针都设为 NULL，并将队列大小设为 0。
参数： Queue* pq：指向队列结构体的指针。
返回值： 无。

实现过程：

• 使用 assert 确保传入的指针不为空。
• 将队列的头指针和尾指针都设为 NULL。
• 将队列的大小设为 0。

2. QueueEmpty

bool QueueEmpty(Queue* pq)
{
    return pq->phead == NULL;
}

功能： 检查队列是否为空。
参数： Queue* pq：指向队列结构体的指针。
返回值： bool：如果队列为空，返回 true；否则返回 false。

实现过程：

• 检查队列的头指针是否为 NULL。如果是，则队列为空，返回 true；否则返回 false。

3. QueuePush

void QueuePush(Queue* pq, QueueDataType x)
{
    assert(pq);
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->next = NULL;
    newNode->x = x;

    if (newNode == NULL)
    {
        perror("malloc fail");
        exit(1);
    }

    if ((pq->phead == NULL) && (pq->ptail == NULL))
    {
        pq->phead = pq->ptail = newNode;
    }
    else
    {
        pq->ptail->next = newNode;
        pq->ptail = pq->ptail->next;
    }

    pq->size++;
}

功能： 将新元素插入到队列的尾部。
参数： Queue* pq：指向队列结构体的指针；QueueDataType x：要插入的元素。
返回值： 无。

实现过程：

• 使用 assert 确保传入的指针不为空。
• 使用 malloc 分配一个新的节点，并检查内存分配是否成功。如果分配失败，打印错误信息并退出程序。
• 将新节点的 next 指针设为 NULL，并将数据 x 存储在新节点中。
• 检查队列是否为空（头指针和尾指针都为 NULL），如果为空，将新节点设为头节点和尾节点。
• 如果队列不为空，将新节点添加到队列尾部，并更新尾指针。
• 增加队列的大小。

4. QueuePop

void QueuePop(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));

    QueueNode* del = pq->phead;
    if (pq->phead == pq->ptail)
    {
        pq->phead = pq->ptail = NULL;
    }
    else
    {
        pq->phead = pq->phead->next;
    }
    free(del);
    pq->size--;
}

功能： 删除队列头部的元素。
参数： Queue* pq：指向队列结构体的指针。
返回值： 无。

实现过程：

• 使用 assert 确保传入的指针不为空且队列不为空。
• 保存头节点的指针。
• 如果头节点和尾节点相同，将头尾指针都设为 NULL。
• 否则，将头指针指向下一个节点。
• 释放头节点的内存，并减少队列大小。

5. QueueFront

QueueDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->phead->x;
}

功能： 获取队列头部的元素，但不删除。
参数： Queue* pq：指向队列结构体的指针。
返回值： QueueDataType：队列头部的元素。

实现过程：

• 使用 assert 确保传入的指针不为空且队列不为空。
• 返回头节点的数据。

6. QueueBack

QueueDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->ptail->x;
}

功能： 获取队列尾部的元素，但不删除。
参数： Queue* pq：指向队列结构体的指针。
返回值： QueueDataType：队列尾部的元素。

实现过程：

• 使用 assert 确保传入的指针不为空且队列不为空。
• 返回尾节点的数据。

7. QueueSize

int QueueSize(Queue* pq)
{
    assert(pq);
    return pq->size;
}

功能： 获取队列中的元素个数。
参数： Queue* pq：指向队列结构体的指针。
返回值： int：队列的大小。

实现过程：

• 使用 assert 确保传入的指针不为空。
• 返回队列的大小。

🥇结语

通过本篇文章的学习，我们了解了栈和队列的基本概念、操作方法及其应用场景。栈作为后进先出的数据结构，常用于递归算法和回溯问题的解决，而队列作为先进先出的数据结构，则在任务调度和广度优先搜索中有着重要应用。希望通过本文的讲解，您能掌握栈和队列的使用技巧，并在实际编程中灵活应用。下一篇文章，我们将继续探讨更为复杂的数据结构，敬请期待！