C語(yǔ)言深入探究棧的原理

更新時(shí)間：2021年11月03日 14:43:57 作者：i_Crave

一種特殊的線性表，其只允許在固定的一端進(jìn)行插入和刪除元素操作。進(jìn)行數(shù)據(jù)插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數(shù)據(jù)元素遵守后進(jìn)先出LIFO（Last In First Out）的原則

棧

壓棧：棧的插入操作叫做進(jìn)棧/壓棧/入棧，入數(shù)據(jù)在棧頂。

出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂。

棧的實(shí)現(xiàn)

棧的實(shí)現(xiàn)一般可以使用數(shù)組或者鏈表實(shí)現(xiàn)，相對(duì)而言數(shù)組的結(jié)構(gòu)實(shí)現(xiàn)更優(yōu)一些。因?yàn)閿?shù)組在尾上插入數(shù)據(jù)的代價(jià)比較小。如下圖：

下面用順序表（數(shù)組）來(lái)實(shí)現(xiàn)棧；

建立一個(gè)順序表結(jié)構(gòu)：

typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; //表示棧頂
int capacity;//表示容量，當(dāng)容量滿時(shí)，擴(kuò)容；
}ST;

創(chuàng)建一個(gè)結(jié)構(gòu)體變量：ST st；在傳數(shù)據(jù)之前要先初始化；不然當(dāng)你沒(méi)賦值就直接訪問(wèn)時(shí)會(huì)出現(xiàn)亂碼或者報(bào)警告；

//初始化
void StackInit(ST* ps)
{
	assert(ps);//斷言，保證傳進(jìn)來(lái)的非空；
	ps->a = NULL;//先將順序表指針指向空；
	ps->top = 0;//棧頂位置表示0位置；
	ps->capacity = 0;//容量為0；
}

接下來(lái)就是向棧內(nèi)傳數(shù)據(jù)（壓棧），要傳結(jié)構(gòu)體地址和要傳的數(shù)據(jù)；

//壓棧
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
    //判斷：數(shù)據(jù)從下標(biāo)0開(kāi)始，因?yàn)閜ot表示該插入的棧頂?shù)奈恢茫彩菈簵５膫€(gè)數(shù)
    //一次插入一個(gè)數(shù)據(jù)，所以數(shù)據(jù)數(shù)量與總?cè)萘肯嗤瑫r(shí)，就需要擴(kuò)容
	if (ps->top == ps->capacity)
	{
		//擴(kuò)容，擴(kuò)二倍
        //使用三目運(yùn)算符判斷，當(dāng)是第一次擴(kuò)容時(shí)，用二倍沒(méi)變化，所以固定開(kāi)辟4個(gè)空間；
		int retcapa = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* ret = (STDataType*)realloc(ps->a, sizeof(STDataType)*retcapa);
		if (ret != NULL)
		{
			ps->a = ret;
			ps->capacity = retcapa;
		}
		else
		{
			printf("realloc開(kāi)辟失敗，退出！");
			exit(-1);
		}
	}
    //擴(kuò)容完，更新數(shù)據(jù)；
	ps->a[ps->top] = x;
	ps->top++;
}

有壓棧就有出棧；出棧用兩個(gè)接口。1.返回棧頂數(shù)據(jù) 2.出棧

因?yàn)橛袝r(shí)候只需要訪問(wèn)棧頂數(shù)據(jù)不需要出棧，如果想出棧又想返回?cái)?shù)據(jù)，就先調(diào)用1，再調(diào)用2；

//返回棧頂元素；
STDataType StackTop(ST* ps)
{
	assert(ps);
 
    //直接斷言要求棧中必須要有數(shù)據(jù)；
	assert(ps->top > 0);
 
	return ps->a[ps->top - 1];
}
 
//出棧，順序表直接把下標(biāo)減一即可
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}

有時(shí)候還需要返回棧中元素

//返回棧中元素個(gè)數(shù)；
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

在一些復(fù)雜結(jié)構(gòu)中要直接調(diào)用查看棧中是否有數(shù)據(jù)，判斷棧是否為空；

//判斷棧中元素是否為空，返回布爾類型
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;//注意這里是沒(méi)有數(shù)據(jù)是返回true;
}

用動(dòng)態(tài)開(kāi)辟的空間就必須手動(dòng)釋放

//釋放；順序表釋放頭指針即可
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

看一下如何調(diào)用的：

int main()
{
	ST st;
	StackInit(&st);
 
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 4);
	StackPush(&st, 5);
	StackPush(&st, 7);
	
    printf("%d\n",StackTop(&st));
	
    StackPop(&st);
	StackPush(&st, 8);
	
	printf("%d\n",StackTop(&st));
    StackPop(&st);
 
	StackDestroy(&st);
	return 0;
}

到此這篇關(guān)于C語(yǔ)言深入探究棧的原理的文章就介紹到這了,更多相關(guān)C語(yǔ)言棧內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: