1.堆疊的概念

堆疊：一種特殊的線性表，其只允許再固定的一段進行插入和洗掉元素操作，進行資料插入和洗掉操作的一端稱為堆疊頂，另一端成為堆疊底，堆疊中的資料元素遵循后進先出LIFO(Last In First Out)的原則，

壓堆疊（push）：堆疊的插入操作叫做進堆疊/壓堆疊/入堆疊，入堆疊資料在堆疊頂，

出堆疊（pop）：堆疊的洗掉操作叫做出堆疊，出資料也在堆疊頂，

2.堆疊實作

2.1堆疊結構

typedef int StackDataType;
typedef struct Stack
{
	StackDataType* data;
	int top;
	int capacity;
}Stack;

Stack:堆疊，

SListDataType:指堆疊中存放的資料型別，只需要改動typedef int SListDataType 中的int就能改變堆疊中存放的資料型別，

data：堆疊資料空間指標

top：堆疊頂，

capacity：堆疊空間大小，

2.2堆疊功能實作

檔案：SList.c

2.2.1堆疊初始化

void StackInit(Stack* pst)						//堆疊初始
{
	StackDataType* tmp = (StackDataType*)malloc(sizeof(StackDataType) * 4);
	assert(tmp);
	pst->data = tmp;
	pst->top = 0;
	pst->capacity = 4;							//堆疊初始空間為4（為了后續擴容方便）
}

2.2.2壓堆疊

void StackPush(Stack* pst, StackDataType x)		//壓堆疊
{
	assert(pst);

	if (pst->capacity == pst->top)				//判斷堆疊是否已滿
	{
		int new_capacity = pst->capacity * 2;
		StackDataType* new_data;
		new_data = (StackDataType*)realloc(pst->data, new_capacity *sizeof(StackDataType));
		assert(new_data);
		pst->data = new_data;
		pst->capacity = new_capacity;
	}

	pst->data[pst->top] = x;
	pst->top++;
}

2.2.3出堆疊

void StackPop(Stack* pst)						//出堆疊
{
	assert(pst);
	assert(pst->data);
	if (pst->top == 0)			//判斷堆疊中是否還有資料
		exit(-1);
	pst->top--;					//直接讓堆疊頂減一即可
}

2.2.4堆疊頂位置

StackDataType StackTop(Stack* pst)				//找堆疊頂
{
	assert(pst);
	assert(pst->data);
	return pst->data[pst->top - 1];
}

2.2.5判斷堆疊是否為空

bool StackEmpty(Stack* pst)						//判堆疊空
{
	assert(pst);
	if (pst->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

2.2.6堆疊大小

?int StackSize(Stack* pst)						//堆疊大小
{
	assert(pst);
	assert(pst->data);
	return pst->top;
}

?

2.2.7堆疊銷毀

void StackDestroy(Stack* pst)					//堆疊銷毀
{
	assert(pst);
	free(pst->data);
	pst->data = NULL;
	pst->top = 0;
	pst->capacity = 0;
}

2.3堆疊頭檔案

檔案："Stack.h"

#pragma once                                    //防止重定義

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>                               //頭檔案包含
#include<malloc.h>
#include<stdbool.h>
#include<assert.h>

typedef int StackDataType;                      //型別定義

typedef struct Stack                            //堆疊結構
{
	StackDataType* data;
	int top;
	int capacity;
}Stack;

void StackInit(Stack* pst);						//堆疊初始
void StackDestroy(Stack* pst);					//堆疊銷毀
void StackPush(Stack* pst, StackDataType x);	//壓堆疊
void StackPop(Stack* pst);						//出堆疊
StackDataType StackTop(Stack* pst);				//找堆疊頂
bool StackEmpty(Stack* pst);					//判堆疊空
int StackSize(Stack* pst);						//堆疊大小

2.4堆疊功能測驗

檔案："test.c"

#include"Stack.h"

void test()
{
	Stack stack ;                                          //創建堆疊
	StackInit(&stack);                                     //堆疊初始

	StackPush(&stack, 10);                                 //壓堆疊
	StackPush(&stack, 20);
	StackPush(&stack, 30);
	StackPush(&stack, 40);
	StackPush(&stack, 50);

	while (!StackEmpty(&stack))                            //回圈列印測驗StackEmpty
	{
		printf("StackTop:%d \n", StackTop(&stack));        //回圈列印測驗StackPop
		printf("StackSize:%d\n\n", StackSize(&stack));     //回圈列印測驗StackSize
		StackPop(&stack);
	}

	StackDestroy(&stack);                                  //銷毀堆疊
}

int main()
{
	test();
	return 0;
}

?寫在最后

?筆記時間：2021_10_23

🌐代碼：Gitee:朱雯睿 (zhu-wenrui) - Gitee.com

Github:https://github.com/Zero0Tw0

💻代碼平臺：Visual Studio2019