棧的定義：

??一種可以實現“先進后出”的存儲結構

??棧類似于箱子，先放進去的最后取出來，最后放入的先取出來

棧的分類：

??靜態棧的內核是數組

??動態棧的內核是鏈表

棧的算法：

??出棧

??壓棧

棧的應用：

??函數調用

??中斷

??表達式求值

??內存分配

??緩沖處理

??迷宮

/*
@file      main.c
@brief     線性結構常見應用之棧
@author    EricsT (EricsT@163.com)
@version   v1.0.0
@date      2025-09-23
@history   2025-09-23 EricsT - 新建文件
*/

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

typedef struct NODE
{
	int data;
	NODE* ptrNext;
}* PtrNode, Note;

typedef struct STACK
{
	PtrNode ptrTop;
	PtrNode ptrBottom;
}* PtrStack, Stack;

void InitStack(PtrStack ptrStack);//初始化
void PushStack(PtrStack ptrStack, int pushValue);//壓棧
bool PopStack(PtrStack ptrStack);//出棧
void TraverseStack(const PtrStack ptrStack);//遍歷
bool IsEmptyStack(const PtrStack ptrStack);//判斷是否為NULL
void ClearStack(PtrStack ptrStack);//清空棧

int main(void)
{
	Stack stack;

	InitStack(&stack);

	int pushValue;
	printf("請輸入插入數值");
	scanf("%d", &pushValue);
	PushStack(&stack, pushValue);

	printf("請輸入插入數值");
	scanf("%d", &pushValue);
	PushStack(&stack, pushValue);

	printf("請輸入插入數值");
	scanf("%d", &pushValue);
	PushStack(&stack, pushValue);

	printf("請輸入插入數值");
	scanf("%d", &pushValue);
	PushStack(&stack, pushValue);

	printf("請輸入插入數值");
	scanf("%d", &pushValue);
	PushStack(&stack, pushValue);

	TraverseStack(&stack);

	PopStack(&stack);

	TraverseStack(&stack);

	ClearStack(&stack);

	TraverseStack(&stack);

	return 0;
}

void InitStack(PtrStack ptrStack)
{//頂棧和底棧都指向空節點

	ptrStack->ptrBottom = (PtrNode)malloc(sizeof(NODE));
	ptrStack->ptrBottom->ptrNext = NULL;

	ptrStack->ptrTop = ptrStack->ptrBottom;
}

void PushStack(PtrStack ptrStack, int pushValue)
{
	PtrNode ptrPushNode = (PtrNode)malloc(sizeof(NODE));

	ptrPushNode->data = pushValue;
	ptrPushNode->ptrNext = ptrStack->ptrTop;

	ptrStack->ptrTop = ptrPushNode;
}

void TraverseStack(const PtrStack ptrStack)
{
	PtrNode ptrNodeCur = ptrStack->ptrTop;

	//while (NULL != ptrNodeCur->ptrNext)
	//{
	//	printf("%d ", ptrNodeCur->data);
	//	ptrNodeCur = ptrNodeCur->ptrNext;
	//}

	while (ptrStack->ptrBottom != ptrNodeCur)
	{
		printf("%d ", ptrNodeCur->data);
		ptrNodeCur = ptrNodeCur->ptrNext;
	}

	printf("\n");
}

bool PopStack(PtrStack ptrStack)
{
	if (IsEmptyStack(ptrStack))//空棧時無法出棧
		return false;

	PtrNode ptrNode = ptrStack->ptrTop;
	ptrStack->ptrTop = ptrNode->ptrNext;
	free(ptrNode);
	//ptrStack->ptrTop = ptrStack->ptrTop->ptrNext;這種寫法無法釋放原來頂棧的內存
	return true;
}

bool IsEmptyStack(const PtrStack ptrStack)
{
	if (ptrStack->ptrBottom == ptrStack->ptrTop)
		return true;

	return false;
}

void ClearStack(PtrStack ptrStack)
{
	if (IsEmptyStack(ptrStack))
		return;

	PtrNode ptrNoteCur = ptrStack->ptrTop;
	PtrNode ptrNoteNext = NULL;

	while (ptrStack->ptrBottom != ptrNoteCur)
	{
		ptrNoteNext = ptrNoteCur->ptrNext;
		free(ptrNoteCur);//釋放內存
		ptrNoteCur = ptrNoteNext;
	}

	ptrStack->ptrTop = ptrStack->ptrBottom;
}