文章导读

栈和队列的基本实现

mizuki 2025年12月25日 41

引言

栈和队列作为数据结构的基础，这篇文章将对栈和队列的基本实现进行具体讲解，并对其进行实现

栈的基本实现

前言

在具体实现栈的函数前，我们要先创建出栈的结构体，所以我们要搞清楚结构体的类型，通过前面的学习，我们有链表和顺序表可以供我们选择，我们可以根据栈的特点来进行选择

栈的特点

1.后进先出，如图（包括栈顶栈底的位置）：

2.只允许在固定的一端进行删除和插入，也就是只能在栈顶进行这些操作

结构体选择

因为只用对栈顶进行删除和插入，我们就可以通过最后一个元素来进行分析

首先是插入，无论是顺序表还是链表，插入都能够顺利的做到，并且相比之下，链表更节省空间，那我们就要选择链表吗？

再看删除，删除了栈顶的元素后，我们要返回上一个元素，但是对于单链表来说（不考虑双链表，因为有两个指向地址，也会浪费空间，不考虑），找到上一个元素是很困难的，而对于顺序表来说，只需要找到上一个下标就可以了，所以我们使用顺序表作为他的结构体

结构体具体内容

首先一个指针数组，一个容量元素是必要的，又因为这里我们只用调用栈顶的函数，我们就创建一个与栈顶有关的元素，也就是尾结点

栈的结构体具体实现如下：

//给数据类型命名
typedef int DataType;

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

栈的初始化

首先与顺序表一样，我们要先初始化存放数据的指针，也就是扩容并且赋值NULL，然后对容量赋值0

不同的是，我们要对栈顶（top）赋值多少呢，我们的目的是通过‘ ’top ‘’找到栈顶元素，此时我们有两个选择

1.对栈顶赋值-1，这样就可以直接指向栈顶元素，因为刚刚初始化时，是没有存放元素的，因为栈顶不会指向任何元素，例如当已经存放一个元素时，top = 0，下标对应的就是栈顶的元素了

2.对栈顶赋值0，此时我们要找到栈顶元素就要通过‘ top-1 ’来找到栈顶元素，但是相对方便的是，我们也可以把’ top ’作为有效元素，可以更好的判断容量是否足够

而在这里我选择的是将top赋值为0，如果你想用第一种方法实现的话，也可以自己尝试

栈的初始化具体实现如下：

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

销毁栈

学会初始化栈后，我们先把销毁栈学习一下

其实与销毁顺序表的方式是一样的，先释放指针，再将两个值赋值为0，具体实现如下：

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

入栈（向栈中插入元素）

1.在执行插入元素前，我们要先判断容量是否足够，但是与之前的顺序表实现不同的是，这里我们不用再单独写一个判断是否需要扩容的函数，因为在栈的实现中只有一次与插入有关的函数，所以直接将判断是否需要扩容的函数写进去就可以了

2.判断扩容后，我们要做的就是赋值，因为我初始化的top元素是0，所以以此类推top元素将一直指向栈顶元素的后一位，我们直接将top作为下标进行赋值就可以了

3.赋值完成后，我们就要对top元素进行+1的处理，使它始终指向栈顶元素的下一个

入栈的具体实现如下：

// 入栈
void StackPush(Stack* ps, DataType data)
{
	assert(ps);
	//判断是否需要扩容
	if (ps->capacity == ps->top)
	{
		int newcapacity = (ps->capacity == 0) ? 4 : ps->capacity * 2;
		DataType* tmp = (DataType*)realloc(ps->data,newcapacity * sizeof(DataType));
		if (tmp == NULL)
		{
			perror("malloc:");
			return;
		}
		ps->data = tmp;
		ps->capacity = newcapacity;
	}
	ps->data[ps->top] = data;
	ps->top++;
}

如果关于扩容这一块有问题的话，可以看这篇顺序表的实现的文章：

出栈（删除栈顶的一个元素）

首先我们要判断此栈是否为空，这关乎函数是否还能继续进行下去

然后直接将top–就可以了，很简单对吧

出栈的具体实现如下：

获取栈顶元素

通过之前的分析，top-1指向的下标就是栈顶元素，直接返回下标为‘ top-1 ’的元素就可以了

具体实现如下：

返回有效元素个数

因为我初始化的top就是0，所以top元素的大小其实就是有效元素的大小，这里也体现了top初始化为0的好处

具体实现如下：

判断栈是否为空

其实就是判断是否存在有效元素，我们可以通过top元素来判断，当top == 0时，栈就为空

这里我们要返回一个bool值，巧妙的运用一个条件判断式来进行返回，如果条件成立就会返回true，反之则返回false

具体实现如下：

所有需要实现的函数如下，可以仔细对照这些函数进行练习实现

包含的头文件

队列的基本实现

前言

与栈相同，在实现队列前，我们要先了解队列的特点，并且选择适合它的结构体

队列的特点

1.先进先出

2.从队头出，从队尾入

队列的结构体选择

通过队列的特点我们可以知道，我们只会从队头出数据，从队尾插入数据，所以需要一个头节点和一个尾节点，而队列中不会出现要删除尾节点的情况，所以为了节省空间，我们就可以选择用链表来实现队列

结构体的具体事项

因为我们已经选择了链表，所以结构体中要包含一个指向下一个节点的指针，一个存数据的元素，但是这个结构体是不能直接当作队列的结构体使用的，因为队列的结构体需要包含一个头节点和一个尾节点，所以这个结构体只能作为队列的结构体,也就是说，我们要在结构体内再嵌套一个结构体

具体实现如下;