C語言超詳細講解棧的實現及程式碼

2022-04-11 13:01:03

前言

棧的概念

棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行資料插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的資料元素遵守後進先出LIFO（Last In First Out）的原則。有點類似於手槍彈夾，後壓進去的子彈總是最先打出，除非槍壞了。
壓棧：棧的插入操作叫做進棧/壓棧/入棧。（入資料在棧頂）
出棧：棧的刪除操作叫做出棧。（出資料也在棧頂）

注意：

1、函數呼叫也有棧，這兩個棧有區別嗎？

當然有區別。函數呼叫會呼叫棧幀，記憶體裡頭也有一個棧，程式執行起來時要執行函數，函數裡頭的區域性變數、引數、返回值等等都要存在函數棧幀裡頭。

這兩個棧沒有任何關聯，一個是資料結構中的棧。另一個是作業系統中記憶體劃分的一個區域，叫做棧，用來函數呼叫時，建立棧幀。雖然本質上沒有任何關聯，但都符合後進先出的規則。

2、假設入棧順序為：1 2 3 4，那麼出棧順序一定為：4 3 2 1 嗎？

當然不是。雖說規則上明確後進先出，可這是相對而言的，如果說它每進一個再出一個，然後再繼續壓棧，那不同樣符合後進先出的規則嗎。就如同上例，你說它出棧順序為1 2 3 4 都不足為奇，每進一個出一個再進，同樣符合規則。類似的入棧兩個再出再進再出也是可以的，好比如2 1 4 3。

棧的結構

棧的實現

建立棧結構

Stack.h 檔案：

//建立棧結構
typedef int STDataType;
typedef struct Stack
{
	STDataType* a; //儲存資料
	int top; //棧頂的位置
	int capacity; //容量
}ST;

初始化棧

思想：

初始化還是相對比較簡單的，學了之前的順序表，初始化棧就很輕鬆了

Stack.h 檔案：

//初始化棧
void StackInit(ST* ps);

Stack.c 檔案：

//初始化棧
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

注意：

這裡初始化的時候將top置為0是有意圖的。首先，由上文建立棧結構時已經標註了，top是用來記錄棧頂的位置，既然是棧頂的位置，那當top初始化為0時，我們可以直接將資料放入棧中，隨後top++，但是當top初始化為-1時，top首先要++才能放入資料，因為資料不可能在負數不屬於棧的位置上放入。下圖演示過程：

本文以 top = 0 範例

銷燬棧

思想：

動態開闢的記憶體空間一定要釋放，free置空即可，並把其餘資料置0。

Stack.h 檔案：

//銷燬棧
void StackDestory(ST* ps);

Stack.c 檔案：

//銷燬棧
void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}

入棧

思路：

前文已經強調了top初始化為0，那麼理應直接壓入資料，並把top++，不過在這之前，得判斷空間是否夠，當top=capacity的時候，棧就滿了，那麼就需要realloc擴容。

Stack.h 檔案：

//壓棧
void StackPush(ST* ps, STDataType x);

Stack.c 檔案：

//壓棧
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//如果棧滿了，考慮擴容
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //檢測容量
		ps->a = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
		if (ps->a == NULL)
		{
			printf("realloc failn");
			exit(-1);
		}
		ps->capacity = newcapacity; //更新容量
	}
	ps->a[ps->top] = x;//將資料壓進去
	ps->top++;//棧頂上移
}

出棧

思路：

在你出棧之前，要確保top不為空，而top不為空的條件就是top>0，所以還要斷言top>0，隨後，直接將棧頂位置下移--即可。跟順序表的思想大同小異。

Stack.h 檔案：

//出棧
void StackPop(ST* ps);

Stack.c 檔案：

//出棧
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}

獲取棧頂元素

思路：

首先要搞清楚誰才是棧頂元素，是top位置還是top-1位置？很顯然是top-1的位置才是棧頂元素，因為在前文初始化的時候已經明確指出top為0，當時壓棧時直接放入資料的，此時第一個資料下標為0，隨後++top再壓入其它資料，由此可見，棧頂元素即下標top-1的位置。

Stack.h 檔案：

//存取棧頂資料
STDataType StackTop(ST* ps);

Stack.c 檔案：

//存取棧頂資料
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1]; //top-1的位置才為棧頂的元素
}

獲取棧中有效元素個數

思想：

上文講到下標top-1才是棧頂元素，那麼是不是說總共就是top-1個元素呢？當然不是，這裡跟陣列下標一樣的思想，元素個數應該就是top個，直接返回即可。

Stack.h 檔案：

//有效元素個數
int StackSize(ST* ps);

Stack.c 檔案：

//有效元素個數
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

檢測棧是否為空

思路：

當top的值為0時即為空，return直接返回即可

Stack.h 檔案：

//判空
bool StackEmpty(ST* ps);

Stack.c 檔案：

//判空
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0; //如果top為0，那麼就為真，即返回
}

Test.c 檔案：

void TestStack()
{
	ST st;
	StackInit(&st);
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	printf("n");
	StackDestory(&st);
}

效果如下：

總程式碼

Stack.h 檔案

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
 
//建立棧結構
typedef int STDataType;
typedef struct Stack
{
	STDataType* a; //儲存資料
	int top; //棧頂的位置
	int capacity; //容量
}ST;
 
//初始化棧
void StackInit(ST* ps);
 
//銷燬棧
void StackDestory(ST* ps);
 
//壓棧
void StackPush(ST* ps, STDataType x);
 
//出棧
void StackPop(ST* ps);
 
//判空
bool StackEmpty(ST* ps);
 
//存取棧頂資料
STDataType StackTop(ST* ps);
 
//有效元素個數
int StackSize(ST* ps);

Stack.c 檔案

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//初始化棧
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}
 
//銷燬棧
void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}
 
//壓棧
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//如果棧滿了，考慮擴容
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //檢測容量
		ps->a = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
		if (ps->a == NULL)
		{
			printf("realloc failn");
			exit(-1);
		}
		ps->capacity = newcapacity; //更新容量
	}
	ps->a[ps->top] = x;//將資料壓進去
	ps->top++;//棧頂上移
}
//出棧
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}
 
//判空
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0; //如果top為0，那麼就為真，即返回
}
 
//存取棧頂資料
STDataType StackTop(ST* ps)
{
	assert(ps);
	return ps->a[ps->top - 1]; //top-1的位置才為棧頂的元素
}
 
//有效元素個數
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

Test.c 檔案

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void TestStack()
{
	ST st;
	StackInit(&st);
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	printf("n");
	StackDestory(&st);
}
int main()
{
	TestStack();
	return 0;
}

到此這篇關於C語言超詳細講解棧的實現及程式碼的文章就介紹到這了,更多相關C語言棧的實現內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！