C語言深入探究棧的原理

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

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

棧

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

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

棧的實現(xiàn)

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

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

建立一個順序表結構：

typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; //表示棧頂
int capacity;//表示容量，當容量滿時，擴容；
}ST;

創(chuàng)建一個結構體變量：ST st；在傳數(shù)據(jù)之前要先初始化；不然當你沒賦值就直接訪問時會出現(xiàn)亂碼或者報警告；

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

接下來就是向棧內傳數(shù)據(jù)（壓棧），要傳結構體地址和要傳的數(shù)據(jù)；

//壓棧
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
    //判斷：數(shù)據(jù)從下標0開始，因為pot表示該插入的棧頂?shù)奈恢?，也是壓棧的個數(shù)
    //一次插入一個數(shù)據(jù)，所以數(shù)據(jù)數(shù)量與總容量相同時，就需要擴容
	if (ps->top == ps->capacity)
	{
		//擴容，擴二倍
        //使用三目運算符判斷，當是第一次擴容時，用二倍沒變化，所以固定開辟4個空間；
		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);
		}
	}
    //擴容完，更新數(shù)據(jù)；
	ps->a[ps->top] = x;
	ps->top++;
}

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

因為有時候只需要訪問棧頂數(shù)據(jù)不需要出棧，如果想出棧又想返回數(shù)據(jù)，就先調用1，再調用2；

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

有時候還需要返回棧中元素

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

在一些復雜結構中要直接調用查看棧中是否有數(shù)據(jù)，判斷棧是否為空；

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

用動態(tài)開辟的空間就必須手動釋放

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

看一下如何調用的：

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;
}

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

您可能感興趣的文章: