【数据结构与算法】栈的实现（附源码）

2024-01-23 14:03:03 浏览数 (1)

一.栈的概念和结构

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

其实用链表和数组都可以实现栈，但栈底就相当于链表的头，数组的第一个元素，栈顶就相当与链表的尾，数组的最后一个元素，当我们进行压栈或是出栈操作时，链表就需要找到尾，所以时间复杂度为O（N），而数组则是O（1），所以这里选择用数组实现栈比较好。 用数组实现的话，就和前面的顺序表类似了。

二.接口实现

A.初始化 Stackinit 销毁 Stackdestroy

1.Stackinit

1.这里数组的初始化就和顺序表那里是一样的了，需要用到动态内存管理的函数，如果不懂的话，建议去补一下这一块的知识哦； 2.这个top用来记录实时数据的数量，和顺序表那里的 sz 是一样的，但注意： <1> 如果初始化成0，那么这个 top 就指的是栈顶的下一个位置； <2> 如果初始化成-1，那么这个 top 就指的是栈顶的位置； 3.初始化容量，这由你自己决定。

代码语言：javascript复制
void Stackinit(Stack* ps)
{
	assert(ps);

	ps->arr = (STdatatype*)malloc(sizeof(STdatatype) * MR_CAP);
	if (ps->arr == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	ps->top = 0;   //表示的是栈顶的下一个位置
	ps->capacity = MR_CAP;   //默认容量
}
2.Stackdestroy

这个非常简单，直接看代码吧。

代码语言：javascript复制
void Stackdestroy(Stack* ps)
{
	assert(ps);

	free(ps->arr);
	ps->arr = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

B.插入 Stackpush 删除 Stackpop

1.Stackpush

在插入前，我们需要判断容量是否已满，若已满，则需要扩容。

代码语言：javascript复制
void Stackpush(Stack* ps, STdatatype x)
{
	assert(ps);
	if (ps->top == ps->capacity)   //判断是否已满
	{
		STdatatype* tmp = (STdatatype*)realloc(ps->arr, 2 * sizeof(STdatatype) * ps->capacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->arr = tmp;
		ps->capacity *= 2;
	}
	ps->arr[ps->top] = x;
	ps->top  ;   //数据入栈后，实时数据数量加1
}
2.Stackpop

删除前要注意栈是否为空，若为空则不能进行删除操作； 删除就是使 top 减1。

代码语言：javascript复制
void Stackpop(Stack* ps)
{
	assert(ps);
	assert(ps->top);   //判断栈是否为空

	ps->top--;  //删除数据
}

C.出栈 Stacktop

出栈前需要判断栈是否为空，为空则无数据可出栈； 因为前面初始化的 top 是0，所以栈顶数据的下标是 top-1 ，如果初始化的 top 是-1，那么栈顶数据的下标则是 top 。

代码语言：javascript复制
STdatatype Stacktop(Stack* ps)
{
	assert(ps);
	assert(ps->top);  //判断栈是否为空
	return ps->arr[ps->top - 1];  //栈顶数据的下标是 top-1
}

D. 栈的有效元素 Stacksize 判空 Stackempty

1.Stacksize

1.若初始化的 top 是0，则 top 就是栈的有效元素个数； 2.若初始化的 top 是-1，则 top 1 为栈的有效元素个数。

代码语言：javascript复制
int Stacksize(Stack* ps)
{
	assert(ps);

	return ps->top;
}
2.Stackempty

1.如果 top 是0，则为空，返回 true； 2.如果 top 不是0，则不为空，返回 false 。

代码语言：javascript复制
bool Stackempty(Stack* ps)
{
	assert(ps);

	return ps->top == 0;  //如果 top ==0 ，则这句代码为真，返回 true；反之，返回 false
}

三.源码

Stack.h
代码语言：javascript复制
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

#define MR_CAP 5

typedef int STdatatype;

typedef struct Stack
{
	STdatatype* arr;
	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);

bool Stackempty(Stack* ps);

void Stackdestroy(Stack* ps);
Stack.c
代码语言：javascript复制
#include "Stack.h"

void Stackinit(Stack* ps)
{
	assert(ps);

	ps->arr = (STdatatype*)malloc(sizeof(STdatatype) * MR_CAP);
	if (ps->arr == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	ps->top = 0;
	ps->capacity = MR_CAP;
}

void Stackpush(Stack* ps, STdatatype x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		STdatatype* tmp = (STdatatype*)realloc(ps->arr, 2 * sizeof(STdatatype) * ps->capacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->arr = tmp;
		ps->capacity *= 2;
	}
	ps->arr[ps->top] = x;
	ps->top  ;
}

void Stackpop(Stack* ps)
{
	assert(ps);
	assert(ps->top);

	ps->top--;
}

STdatatype Stacktop(Stack* ps)
{
	assert(ps);
	assert(ps->top);
	return ps->arr[ps->top - 1];
}

int Stacksize(Stack* ps)
{
	assert(ps);

	return ps->top;
}

bool Stackempty(Stack* ps)
{
	assert(ps);

	return ps->top == 0;
}

void Stackdestroy(Stack* ps)
{
	assert(ps);

	free(ps->arr);
	ps->arr = NULL;
	ps->top = 0;
	ps->capacity = 0;
}
test.c
代码语言：javascript复制
#include "Stack.h"

void testStack()
{
	Stack st;

	Stackinit(&st);

	int i = 0;
	for (i = 1; i <= 8; i  )
	{
		Stackpush(&st, i);
	}
	printf("%dn ", Stacksize(&st));
	/*while (!Stackempty(&st))
	{
		printf("%d  ", Stacktop(&st));
		Stackpop(&st);
	}*/
	printf("n");
	Stackdestroy(&st);
}

int main()
{
	testStack();

	return 0;

}
ps 数据 数据结构与算法 数组 源码

0 人点赞