欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言深入探究棧的原理

 更新時(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ù)組)來實(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)你沒賦值就直接訪問時(shí)會(huì)出現(xiàn)亂碼或者報(bào)警告;

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

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

//壓棧
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
    //判斷:數(shù)據(jù)從下標(biāo)0開始,因?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í),用二倍沒變化,所以固定開辟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開辟失敗,退出!");
			exit(-1);
		}
	}
    //擴(kuò)容完,更新數(shù)據(jù);
	ps->a[ps->top] = x;
	ps->top++;
}

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

因?yàn)橛袝r(shí)候只需要訪問棧頂數(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;//注意這里是沒有數(shù)據(jù)是返回true;
}

用動(dòng)態(tà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語言深入探究棧的原理的文章就介紹到這了,更多相關(guān)C語言 棧內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

最新評(píng)論