栈的介绍与实现

时间:2024-10-05 22:21:17

一. 概念与结构

:⼀种特殊的线性表,其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶,另⼀端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out的原则。

压栈:栈的插⼊操作叫做进栈/压栈/⼊栈,入数据在栈顶

出栈:栈的删除操作叫做出栈。出数据也在栈顶

栈的实现⼀般可以使⽤数组或者链表实现,相对⽽⾔数组的结构实现更优⼀些。因为数组在尾上插⼊数据的代价相对较小。

数组尾插时间复杂度:O(1) 链表尾插时间复杂度:O(N)

二.栈的实现

ps:由于栈的底层是数组,因此其结构实现与之前讲到的顺序表大致类似,在学习时可以进行类

比记忆。 

stack.h

程序相关接口如下:

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{
	STDataType* arr;
	STDataType capacity;
	STDataType top;
}ST;

//初始化和销毁
void STInit(ST*);
void STDestroy(ST*);


//栈顶---入数据,出数据
void StackPush(ST*, STDataType);
void StackPop(ST*);

//判空
bool StackEmpty(ST*);

//取栈顶元素
STDataType StackTop(ST*);


//获取栈中有效元素个数
int STSize(ST*);

test.c

程序相关测试代码如下: 

#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"
void STTest01()
{
	ST st;
	STInit(&st);
	
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	StackPush(&st, 5);

	
	//StackPop(&st);
	//StackPop(&st);
	//StackPop(&st);
	//StackPop(&st);
	//StackPop(&st);
	// 
	
	printf("size: %d\n", STSize(&st));
	
	while (!StackEmpty(&st))
	{
		STDataType data = StackTop(&st);
		printf("%d ", data);
		StackPop(&st);
	}
	printf("\n");
	
	printf("size: %d\n", STSize(&st));

}
int main()
{
	STTest01();
	return 0;
}

栈的初始化

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

分析:

1.首先对传入的指针进行断言检查

2.将数组置为空,容积和首元素位置置于0。

需注意:此处的top表示队头元素的下一个。

栈的销毁

void STDestroy(ST*ps)
{
	assert(ps);
	if (ps->arr)
		free(ps->arr);
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

分析:

1.首先对传入的指针进行断言检查

2.释放指针并置为空,再将容积和队头元素位置置为0。

栈顶插入数据——压栈/入栈

void StackPush(ST* ps, STDataType x)
{
	assert(ps);

	//空间是否足够
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = 2 * newcapacity;
	}
	ps->arr[ps->top++] = x;
}

分析:

1.首先assert断言指针是否为空,并判断空间是否足够

2.如果需要增容,一般按2倍或者3倍扩容,避免频繁增容或者说增容过多导致的时间和空间销毁。

3.增容后,直接在栈顶处赋值即可。、

栈顶删除数据——出栈

与入栈之前需检查是否扩容原理类似,出栈之前需要检查栈是否为空。

bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

分析:由于我们在之前已经提到,top表示栈顶数据位置的下一个,因此当栈为空时,top是否为0就是判断依据。

void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	--ps->top;
}

分析:直接让top--即可,即使后续再有数据插入,也会直接覆盖原先已经删除的值。

输出栈顶数据

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->arr[ps->top-1];
}

分析:top表示栈顶数据的下一个,因此直接返回top-1的数据即可。

注意:切勿把top-1写成top--,否则相当于不仅输出了栈顶数据,还进行了一次出栈。

输出栈的元素个数

int STSize(ST* ps)
{
	return ps->top;
}

分析:top除了表示栈顶数据的下一个外,还可以直接表示元素个数,这与数组下标直接契合。

逐个输出栈中元素

while (!StackEmpty(&st))
	{
		STDataType data = StackTop(&st);
		printf("%d ", data);
		StackPop(&st);
	}
	printf("\n");

分析:取临时变量分别接收栈顶元素,输出后再删除栈顶元素,直至栈为空跳出循环即可。

三.完整代码

stack.c如下

#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"
void STInit(ST* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}

void STDestroy(ST*ps)
{
	assert(ps);
	if (ps->arr)
		free(ps->arr);
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

void StackPush(ST* ps, STDataType x)
{
	assert(ps);

	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = 2 * newcapacity;
	}
	ps->arr[ps->top++] = x;
}


bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	--ps->top;
}



STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->arr[ps->top-1];
}



int STSize(ST* ps)
{
	return ps->top;
}

相关文章