快捷導(dǎo)航

C語(yǔ)言中棧的結(jié)構(gòu)和函數(shù)接口的使用示例

更新時(shí)間：2023年02月14日 11:31:57 作者：[Pokemon]大貓貓

這篇文章主要介紹了C語(yǔ)言中棧的結(jié)構(gòu)和函數(shù)接口的使用，類似很多軟件都有撤銷的操作，這其實(shí)就是用棧這種方法來(lái)實(shí)現(xiàn)的，當(dāng)然不同的軟件具體實(shí)現(xiàn)代碼會(huì)有差異，不過(guò)原理大多都是一樣的

一、棧的結(jié)構(gòu)

棧：一種操作受限的線性表，只允許在線性表的一端進(jìn)行插入和刪除操作，進(jìn)行插入刪除的一端稱作棧頂，另一端稱之為棧底

通過(guò)動(dòng)態(tài)順序表的實(shí)現(xiàn)，可以發(fā)現(xiàn)在對(duì)數(shù)組進(jìn)行尾插尾刪時(shí)效率很高，因此棧可以用數(shù)組實(shí)現(xiàn)，將數(shù)組的尾部作為棧頂，結(jié)構(gòu)如下：

通過(guò)單鏈表的實(shí)現(xiàn)，可以發(fā)現(xiàn)在對(duì)鏈表進(jìn)行頭插頭刪時(shí)效率很高，因此也可以用鏈表來(lái)實(shí)現(xiàn)，將單鏈表的頭結(jié)點(diǎn)作為棧頂，結(jié)構(gòu)如下：

綜合考慮：數(shù)組的實(shí)現(xiàn)方法更優(yōu)，本篇以數(shù)組的方式介紹棧的結(jié)構(gòu)和函數(shù)接口

//棧的元素類型
typedef int StackDataType;
//棧的結(jié)構(gòu)
typedef struct Stack
{
	StackDataType* a;	//存放元素的數(shù)組
	int top;	//指向棧頂元素的下一個(gè)位置
	int capacity;	//容量
}Stack;

二、棧的函數(shù)接口

1. 初始化和銷毀

初始時(shí)給棧分配一些空間，并將 top置為 0，代表指向棧頂元素的下一個(gè)位置

初始化函數(shù)如下：

void StackInit(Stack* ps)
{
	assert(ps);
	//開辟空間
	ps->a = (StackDataType*)malloc(sizeof(StackDataType) * 4);
	if (ps->a == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	ps->top = 0;
	ps->capacity = 4;
}

棧是動(dòng)態(tài)開辟的，不用時(shí)需要銷毀

銷毀函數(shù)如下：

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

2. 入棧和出棧

入棧：在棧頂插入元素，當(dāng)空間不夠時(shí)需要擴(kuò)容

入棧函數(shù)如下：

void StackPush(Stack* ps, StackDataType x)
{
	assert(ps);
	//空間不夠時(shí)，需要擴(kuò)容
	if (ps->top == ps->capacity)
	{
		StackDataType* tmp = (StackDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(StackDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
	//top 指向棧頂元素的下一個(gè)位置，因此 top 先插入數(shù)據(jù)，然后再自增
	ps->a[ps->top] = x;
	ps->top++;
}

出棧：刪除棧頂元素

出棧函數(shù)如下：

void StackPop(Stack* ps)
{
	assert(ps);
	//棧為空時(shí)不能刪除，這里直接調(diào)用判空函數(shù)
	assert(!StackEmpty(ps));	
	ps->top--;
}

3. 訪問(wèn)棧頂元素以及判空和元素個(gè)數(shù)

返回棧頂元素函數(shù)如下：

StackDataType StackTop(Stack* ps)
{
	assert(ps);
	//棧為空時(shí)不能取棧頂元素，這里直接調(diào)用判空函數(shù)
	assert(!StackEmpty(ps));
	//top 指向棧頂元素的下一個(gè)，所以需要-1
	return ps->a[ps->top - 1];
}

判空函數(shù)如下：

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

元素個(gè)數(shù)函數(shù)如下：

size_t StackSize(Stack* ps)
{
	assert(ps);
	//top 即為元素個(gè)數(shù)
	return ps->top;
}

到此這篇關(guān)于C語(yǔ)言中棧的結(jié)構(gòu)和函數(shù)接口的使用示例的文章就介紹到這了,更多相關(guān)C語(yǔ)言棧的結(jié)構(gòu)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: