1.棧

1.1棧的概念及結構

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

• 壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數據在棧頂。
• 出棧：棧的刪除操作叫做出棧。出數據也在棧頂

1.2 棧的實現

在VS2022中新建一個工程

• stack20250308.h（棧的類型定義、接口函數聲明、引用的頭文件）
• stack20250308.c（棧的接口函數的實現）
• stackTest20250308.c（主函數、測試各個接口功能）

• 實現接口

// 支持動態增長的棧
typedef int  STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;

// 初始化棧
void STInit(ST* ps);
//銷毀
void STDestroy(ST* ps);
// 入棧，插入
void STPush(ST* ps, STDataType x);
// 出棧，刪除
void STPop(ST* ps);
//獲取棧中有效元素個數
int STSize(ST* ps);
//檢測棧是否為空，如果為空返回非零結果，如果不為空返回0
bool STEmpty(ST* ps);
//獲取棧頂元素
STDataType STTop(ST* ps);

1.1.0 棧的初始化

// 初始化棧
void STInit(ST* ps)
{assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType)*4);if (ps->a == NULL){perror("STInit::malloc fail!");return;}ps->capacity = 4;ps->top = 0;//top是棧頂元素的下一個位置//ps->top =-1;//top是棧頂元素位置
}

1.1.1 銷毀

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

1.1.2 入棧

// 入棧，插入
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){STDataType* tem = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity*2);//擴容當前的2倍if (ps->a == NULL){perror("STInit::relloc fail!");return;}ps->a = tem;ps->capacity *= 2; //修改容量}ps->a[ps->top] = x;ps->top++;
}

1.1.3 出棧

// 出棧，刪除
void STPop(ST* ps){assert(ps);assert(!STEmpty(ps));//檢查是否為空，為空就報錯，ps->top--;//直接--，但是空棧的時候就不能繼續--，所以在之前進行是否為空的檢查。
}

1.1.4 獲取棧中有效元素個數

//獲取棧中有效元素個數
int STSize(ST* ps)
{assert(ps);//top就是sizereturn ps->top;
}

1.1.5 檢測棧是否為空，如果為空返回非零結果，如果不為空返回0

//檢測棧是否為空，如果為空返回非零結果，如果不為空返回0
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

1.1.6 獲取棧頂元素

//獲取棧頂元素
STDataType STTop(ST* ps)
{assert(ps);return ps->a[ps->top - 1];//top是最后一個元素的下一個位置，所以-1
}

1.1.7 驗證

• 驗證的時候，我們棧是不能打印的，我們需要一個一個出棧打印棧頂元素

void STTest()
{ST st;STInit(&st);STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);STPush(&st, 5);while (!STEmpty(&st)){printf("%d ", STTop(&st));STPop(&st);}STDestroy(&st);}

插入

刪除

棧有效個數驗證

附錄 棧的C語言實現源碼

.h文件

#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>//靜態的
//#define N 10
//typedef struct Stack
//{
//	int a[N];
//	int top;
//
//}Stack;// 支持動態增長的棧
typedef int  STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;
// 初始化棧
void STInit(ST* ps);
//銷毀
void STDestroy(ST* ps);
// 入棧，插入
void STPush(ST* ps, STDataType x);
// 出棧，刪除
void STPop(ST* ps);
//獲取棧中有效元素個數
int STSize(ST* ps);
//檢測棧是否為空，如果為空返回非零結果，如果不為空返回0
bool STEmpty(ST* ps);
//獲取棧頂元素
STDataType STTop(ST* ps);

.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"stack20250308.h"// 初始化棧
void STInit(ST* ps)
{assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType)*4);if (ps->a == NULL){perror("STInit::malloc fail!");return;}ps->capacity = 4;ps->top = 0;//top是棧頂元素的下一個位置//ps->top =-1;//top是棧頂元素位置
}//銷毀
void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}
// 入棧，插入
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){STDataType* tem = (STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity*2);//擴容當前的2倍if (ps->a == NULL){perror("STInit::relloc fail!");return;}ps->a = tem;ps->capacity *= 2; //修改容量}ps->a[ps->top] = x;ps->top++;
}
// 出棧，刪除
void STPop(ST* ps){assert(ps);assert(!STEmpty(ps));//檢查是否為空，為空就報錯，ps->top--;//直接--，但是空棧的時候就不能繼續--，所以在之前進行是否為空的檢查。
}//獲取棧中有效元素個數
int STSize(ST* ps)
{assert(ps);//top就是sizereturn ps->top;
}
//檢測棧是否為空，如果為空返回非零結果，如果不為空返回0
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
//獲取棧頂元素
STDataType STTop(ST* ps)
{assert(ps);return ps->a[ps->top - 1];//top是最后一個元素的下一個位置，所以-1
}

test.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"stack20250308.h"void STTest()
{ST st;STInit(&st);STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);STPush(&st, 5);STPop(&st);STPop(&st);int size = STSize(&st);printf("棧有效元素為：%d\n", size);while (!STEmpty(&st)){printf("%d ", STTop(&st));STPop(&st);}STDestroy(&st);
}int main()
{STTest();return 0;
}