一、什么是堆疊

二、堆疊的實作

1.每個模塊

代碼如下：

//堆疊中存盤的資料型別為進行重命名
//為什么要重命名？
//因為如果以后想將存盤資料的內容改為char或者double等其他型別的話，只需在這里該一次就可以，
//而不必代碼中的每一處都改，減少了不必要的麻煩，提高了代碼的可讀性
typedef int STDataType;

typedef struct Stack
{
	STDataType* a;//這里用一個指標指向堆疊的地址
	int top;		// 堆疊頂
	int capacity;  // 容量 
}Stack;
// 初始化堆疊 
void StackInit(Stack* ps);
// 入堆疊 
void StackPush(Stack* ps, STDataType data);
// 出堆疊 
void StackPop(Stack* ps);
// 獲取堆疊頂元素 
STDataType StackTop(Stack* ps);
// 獲取堆疊中有效元素個數 
int StackSize(Stack* ps);
// 檢測堆疊是否為空，如果為慷訓傳非零結果，如果不為慷訓傳0 
bool StackEmpty(Stack* ps);
// 銷毀堆疊 
void StackDestroy(Stack* ps);

2.每個模塊的實作

代碼如下：

// 初始化堆疊 
void StackInit(Stack* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}
// 入堆疊 
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	if (ps->capacity == ps->top)//判斷堆疊堆疊是否滿了，如果滿了將進一步擴容
	{
		int newcapacity = ps->capacity == 0 ? 4 : (ps->capacity) * 2;//這里應當考慮capacity為0的特殊情況，如果capacity不為0，就將原來的容量擴2倍
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(int)*newcapacity);
		if (!tmp)//如果擴容失敗就給提示資訊并例外終止程式
		{
			printf("realloc fail\n");
			exit(-1);//exit(0)表示正常終止程式，相反exit(-1)表示例外終止程式
		}
		ps->a = tmp;//擴容成功，就講tmp賦給a
		ps->capacity = newcapacity;//capacity也要更新
	}
	ps->a[ps->top++] = data;//等價于ps->a[ps->top] = data;
	                        //ps->top++;
}
// 出堆疊 
void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));//通常情況下，這里的出堆疊和下面的獲取堆疊頂元素都需要判斷堆疊是否為空，因為堆疊里面都沒有元素了，還怎么出堆疊或者獲取堆疊頂元素，           
	                          //我們這里暴力一點，直接斷言
	                          //如果想溫柔一點解決，也可以這樣 if(StackEmpty(ps))
	                          //                               {
	                          //                                  printf("Stack Empty\n");
	                          //                                  return; 直接回傳
    ps->top--;  //我們只需要將top減1，就可以達到洗掉資料的效果，下一次插入資料的時候，這個資料 
                //就會被新的資料覆寫
}
// 獲取堆疊頂元素 
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];//top位置是下一個存盤資料的位置，所以這里要減1，
	                          //注意這里不是ps->top--,如果這么做，表示取了堆疊頂元素并將其洗掉
}
// 獲取堆疊中有效元素個數 
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;//top位置是下一個存盤資料的位置，因為陣列是從下標為0開始計算的，
	                   //所以直接回傳top，不需要減1
}
// 檢測堆疊是否為空，如果為慷訓傳非零結果，如果不為慷訓傳0 
bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}
// 銷毀堆疊 
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);//釋放指標a指向的空間，因為a指向的空間都是動態開辟出來的，所以要手動釋放
	a = NULL;//將a置為NULL，防止被解參考，導致程式崩潰
	ps->capacity = ps->top = 0;
}

3測驗程式

代碼如下：

void test()
{
	Stack ST;
	StackInit(&ST);
	StackPush(&ST, 1);
	StackPush(&ST, 2);
	StackPush(&ST, 3);
	StackPush(&ST, 4);//入堆疊4次
	printf("%d\n", StackSize(&ST));//列印堆疊里存放資料的個數
	StackPush(&ST, 5);
	StackPush(&ST, 6);//再入堆疊2次
	printf("%d\n", StackSize(&ST));
	StackPop(&ST);//將最后一個元素出堆疊
	StackPush(&ST, 7);//將7入堆疊，此時堆疊中的資料6將被7覆寫
	while (!StackEmpty(&ST))//列印堆疊里的資料，直到堆疊為空為止
	{
		printf("%d ", StackTop(&ST));
		StackPop(&ST);//如果不將最后一個資料出堆疊，top不會變，將一直列印最后一個元素，導致死回圈
	}
	printf("\n");

	StackDestroy(&ST);//釋放空間
}

int main()
{
	test();

	return 0;
}

測驗：

畫圖分析：

總結

我們這次使用順序表來實作堆疊，不過相對于順序表，用鏈表實作相對較麻煩，
在堆疊的實作當中，有入堆疊，出堆疊等7個模塊，在實作入堆疊時，我們需要考慮容量是否需要擴容，也要進一步考慮capacity是否為的特殊情況，在出堆疊時，我們要考慮堆疊內是否還有資料，如果沒有資料(沒有資料還在進行出堆疊，是不符合常理的，就例如沒有錢還要去超市買東西一樣)，我們該如何解決這種問題，
其實在生活中，堆疊這種資料結構應用是十分廣泛的,
例如堆疊可以應用于括號匹配、行編輯器、運算式求值、演算法優先文法等編譯程式中，