【算法与数据结构】栈的实现详解

学习起来吧

发布于 2024-03-10 08:31:44

920

发布于 2024-03-10 08:31:44

文章被收录于专栏：学习C/++

📝栈的概念及结构

栈的概念:

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

栈的主要特点:

先进后出(LIFO, Last In First Out)。新添加的元素都放在栈顶,取出元素时也是从栈顶取出。
只允许在一端(栈顶)进行插入和删除操作。插入操作称为入栈,删除操作称为出栈。
栈内元素的访问只能是顺序访问,不能随机访问。
通常使用数组或链表来实现栈。

栈的基本操作:

- push(item): 将元素添加到栈顶。
- pop(): 弹出栈顶元素,同时删除该元素。
- peek(): 返回栈顶元素,但不删除。 
- isEmpty(): 检查栈是否为空。
- size(): 返回栈中元素的个数。

栈的结构: 使用数组实现栈时,维护一个top指针指向栈顶元素的下一个位置。入栈时将元素添加到数组top位置,并将top加1;出栈时从top位置取元素,并将top减1。使用链表实现栈时,链表的头结点指向栈顶元素。入栈添加新节点到头结点后面,出栈删除头结点。所以栈具有后进先出的特性,是一种限定只允许在一端插入和删除的线性数据结构。

🌉栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。使用数组实现栈确实具有一些优点：

内存连续性：数组在内存中是连续存储的，这使得对数组的访问速度相对较快，因为它允许缓存友好的访问模式。
尾部操作高效：数组在尾部插入或删除元素的时间复杂度为 O(1)，这使得栈的 push 和 pop 操作效率很高。

但是，使用数组实现栈也有一些限制： 4. 固定大小：数组的大小一旦确定，就不能动态扩展，如果栈需要存储的元素数量超过了数组的大小，就会导致栈溢出。 5. 动态调整的开销：当栈的大小超出数组容量时，需要重新分配更大的数组并将原始数据复制到新数组中，这会引入一定的开销。

相比，链表实现栈的优点是：

动态大小：链表可以根据需要动态扩展，不受固定大小的限制。
插入和删除操作的效率：在链表中，插入和删除操作的时间复杂度为 O(1)，不会像数组那样需要重新分配和复制数据。

但链表实现也有其缺点：

空间开销：链表中的每个节点都需要额外的指针来指向下一个节点，这会增加存储开销。
缓存不友好：由于节点在内存中不一定是连续存储的，可能会导致缓存未命中，从而降低访问速度。

因此，选择使用数组或链表实现栈取决于具体的需求和性能要求。如果需要高效的尾部操作和内存连续性，则数组实现可能更合适；而如果需要动态大小和高效的插入/删除操作，则链表实现可能更合适。

🌠栈的接口

本文将将使用动态链表实现栈：

StackCode.h

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

//方便修改
typedef int STDataType;
typedef struct Stack
{
	STDataType* _a;
	int _top;//栈顶
	int _capacity;//容量
}Stack;
//初始化栈
void StackInit(Stack* ps);
//入栈
void StackPush(Stack* ps, STDataType x);
//出栈
void StackPop(Stack* ps);
//获取栈顶元素
STDataType StackTop(Stack* ps);
//获取栈中有效元素个数
int StackSize(Stack* ps);
//检测栈是否有空，如果为空返true，如果不为空，返回false；
bool StackEmpty(Stack* ps);
//销毁栈
void StackDestroy(Stack* ps);

🌉初始化栈

//初始化栈
void StackInit(Stack* ps)
{
	assert(ps);//assert(ps)检查ps指针是否合法,防止空指针问题。
	ps->_a = NULL;//栈初始化时还未分配数组空间。
	ps->_capacity = ps->_top = 0;
}

注意：将_capacity和_top成员都设置为0。 _capacity表示栈的总容量,初始化时为0表示还未分配空间。 _top表示栈顶元素的下一个位置,作为栈的有效元素计数器。初始化时为0表示栈为空。

🌠入栈

void StackPush(Stack* ps, STDataType x)
{
	assert(ps);
	//满了，需要扩容
	if (ps->_top == ps->_capacity)//判断栈是否满了(ps->_top == ps->_capacity),如果满了需要扩容:
	{//如果_capacity为0,新容量为4,否则新容量为原容量的2倍
		int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
		STDataType* temp = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType));//使用realloc重新分配数组空间
		if (NULL == temp)
		{
			perror("realloc temp");//实际分配失败会打印错误并返回
			return;
		}

		ps->_a = temp;//扩容成功后,更新_a指针和_capacity
		ps->_capacity = newcapacity;

	}
	//将元素x赋值到栈顶位置ps->_a[ps->_top]
	ps->_a[ps->_top] = x;
	ps->_top++;
}

🌉出栈

//出栈
void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->_top--;
}

修改_top指针,就可以模拟出栈操作了。元素本身不做删除,只是修改指针来"移除"顶部元素。

🌠获取栈顶元素

//获取栈顶元素
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->_a[ps->_top - 1];
}

由于栈使用数组实现,元素位置从0开始编号，栈顶指针_top指向当前栈顶元素的下一个位置，所以实际栈顶元素的位置是_top - 1

🌉获取栈中有效元素个数

//获取栈中有效元素个数
int StackSize(Stack* ps)
{
	assert(ps);

	return ps->_top;
}

栈使用数组实现,元素从0开始插入，_top指针指向当前最后一个元素的下一个位置，所以_top值就代表当前栈中元素的个数

🌉检测栈是否为空

//检测栈是否为空，如果为空返回true，结果不为空false
bool StackEmpty(Stack* ps)
{
	assert(ps);
	if (ps->_top == 0)
		return true;
	else
		return false;
	
}

🌉销毁栈

//销毁栈
void StackDestroy(Stack* ps)
{
	assert(ps);
	ps->_a = NULL;
	ps->_capacity = ps->_top   = 0;
}

🌉Stack.c文件：

# define _CRT_SECURE_NO_WARNINGS 1
#include "StackCode.h"

//初始化栈
void StackInit(Stack* ps)
{
	assert(ps);
	ps->_a = NULL;
	ps->_capacity = ps->_top = 0;
}
//入栈
void StackPush(Stack* ps, STDataType x)
{
	assert(ps);
	//满了，需要扩容
	if (ps->_top == ps->_capacity)
	{
		int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
		STDataType* temp = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType));
		if (NULL == temp)
		{
			perror("realloc temp");
			return;
		}

		ps->_a = temp;
		ps->_capacity = newcapacity;

	}
	ps->_a[ps->_top] = x;
	ps->_top++;
}

//出栈
void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->_top--;
}
 
//获取栈顶元素
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->_a[ps->_top - 1];
}
//获取栈中有效元素个数
int StackSize(Stack* ps)
{
	assert(ps);

	return ps->_top;
}
//检测栈是否为空，如果为空返回true，结果不为空false
bool StackEmpty(Stack* ps)
{
	assert(ps);
	if (ps->_top == 0)
		return true;
	else
		return false;
	
}
//销毁栈
void StackDestroy(Stack* ps)
{
	assert(ps);
	ps->_a = NULL;
	ps->_capacity = ps->_top   = 0;
}

🌉测试文件

Test.c

#include "STackCode.h"

int main()
{
	Stack s;
	StackInit(&s);
	StackPush(&s,1);
	StackPush(&s,2);
	StackPush(&s,3);
	StackPush(&s,4);

	int top = StackTop(&s);
	printf("%d", top);
	StackPop(&s);

	StackPush(&s, 5);
	StackPush(&s, 6);

	while (!StackEmpty(&s))
	{
		int top = StackTop(&s);
		printf("%d", top);
		StackPop(&s);
	}

	StackDestroy(&s);

	return 0;
}

测试结果：