前言：大家好😍，本文主要介紹了數據結構——順序棧
目錄
一、概念
1.1 順序棧的基本概念
1.2 順序棧的存儲結構
二、基本操作
2.1 結構體定義
2.2 初始化?
2.3 判空
2.4 判滿
2.5 擴容
2.6 插入 入棧
2.7 刪除 出棧
2.8 獲取棧頂元素
2.9 獲取有效值長度
2.10 清空
2.11 銷毀
2.12 打印
2.13 測試
一、概念
順序棧是棧的一種實現方式，它是基于順序存儲結構（通常是數組或動態分配的內存空間）實現的棧。棧是一種**后進先出（LIFO，Last In First Out）**的數據結構，這意味著最后放入棧中的元素會最先被取出。
1.1 順序棧的基本概念
-
棧的定義：
-
棧是一種線性表，其操作主要在表的一端進行，這一端稱為棧頂（Top），另一端稱為棧底（Bottom）。
-
棧的操作遵循**后進先出（LIFO）**的原則，即最后放入棧中的元素最先被取出。
-
-
順序棧的特點：
-
順序棧使用連續的內存空間來存儲棧中的元素，通常通過數組或動態分配的內存來實現。
-
棧底的位置是固定的，通常用一個指針（如
base）來標記棧底。 -
棧頂的位置是動態變化的，用一個指針（如
top）來表示棧頂的位置。
-
1.2 順序棧的存儲結構
順序棧的存儲結構通常包括以下部分：
ps是一個指向Seq_Stack結構體的指針，所以? ? ps可以指向結構體的成員
-
base：指向棧底的指針，標記棧的起始位置。 -
top：棧頂指針，表示棧頂的位置。top的值通常等于棧中元素的數量。 -
stacksize：表示棧的總容量，即棧可以存儲的最大元素數量。
二、基本操作
2.1 結構體定義
typedef char ELEM_TYPE;
#define INITSIZE 10//*2struct Seq_Stack
{ELEM_TYPE* base;//指針，用來接收malloc的返回值int top;//棧頂指針int stacksize;//當前總的格子數
};
typedef struct Seq_Stack Seq_Stack;
typedef struct Seq_Stack* PSeq_Stack;
base是一個指針，它的作用是標記棧的底部位置，也就是這塊連續內存空間的起始地址。有了base，我們就能找到棧的“根基”，從而操作整個棧。無論棧頂指針top如何變化（入棧或出棧），base始終指向棧的底部，確保我們不會迷失方向。
2.2 初始化?
void Init_Seq_Stack(Seq_Stack* ps)
{assert(ps != NULL);ps->base = (ELEM_TYPE*)malloc(INITSIZE * sizeof(ELEM_TYPE));if (ps->base == NULL)//內存分配失敗{exit(1);//程序調用exit終止運行}ps->top = 0;ps->stacksize = INITSIZE;
}
參數：
Seq_Stack* ps是一個指向Seq_Stack結構體的指針。這個結構體定義了棧的基本屬性，比如棧底指針、棧頂指針和棧的容量等。
ps->base：這是棧底指針，用來存儲malloc分配的內存地址。分配完內存后，ps->base就指向了這塊內存的起始位置，也就是棧的底部。malloc：這是一個動態內存分配函數，用來在堆上分配一塊內存空間。
ps->top = 0：棧頂指針top初始化為0。在順序棧中，top的值通常表示棧中元素的數量。初始時棧為空，所以top為0。
ps->stacksize = INITSIZE：將棧的總容量stacksize設置為初始大小INITSIZE。這樣我們就知道棧一開始可以存儲多少個元素。通過
ps，函數可以訪問和修改這個棧的內部數據（如base、top和stacksize）。
2.3 判空
//2.判空(判斷順序表有沒有元素)
bool Is_Empty(Seq_Stack* ps)
{if (ps == NULL)exit(1);return ps->top ==0;
}
這個指針
ps就是用來告訴函數“我要檢查的是哪一個棧”。
if (ps == NULL)來檢查指針是否為空。如果是空的，說明傳入的棧是無效的，程序會調用exit(1)終止運行，避免后續操作出錯。
2.4 判滿
bool Is_Full(Seq_Stack* ps)
{if (ps == NULL)return false;return ps->top == ps->stacksize;
}
2.5 擴容
//4.擴容
static void Inc(Seq_Stack*ps)
{assert(ps != NULL);if (ps == NULL)return;ELEM_TYPE* tmp = (ELEM_TYPE*)realloc(ps->base, ps->stacksize * sizeof(ELEM_TYPE) * 2);if (tmp != NULL)ps->base = tmp;ps->stacksize *= 2;
}
Inc函數用于將順序棧的容量加倍。從而允許更多的元素入棧。
realloc：這是一個動態內存分配函數，用來重新分配一塊內存空間。它接受兩個參數：
第一個參數是當前內存塊的指針（這里是
ps->base）。第二個參數是新的內存大小（這里是
ps->stacksize * sizeof(ELEM_TYPE) * 2）。ps->stacksize是當前棧的容量，sizeof(ELEM_TYPE)是每個元素的大小，* 2表示將容量加倍。
tmp：這是一個臨時指針，用來存儲realloc返回的新內存地址。如果realloc成功，它會返回新的內存塊的指針；如果失敗，它會返回NULL。如果
tmp不為NULL，說明realloc成功，新的內存已經分配好了。此時，將ps所指向的結構體中的base成員更新為tmp的值。，即讓棧底指針指向新的內存地址。將棧的總容量
stacksize加倍。
2.6 插入 入棧
//插入元素(入棧/壓棧) Push
bool Push(Seq_Stack* ps, ELEM_TYPE val)
{assert(ps != NULL);if (ps == NULL)return false;if (Is_Full(ps)){Inc(ps);}ps->base[ps->top] = val;ps->top++;return true;
}
ps->base[ps->top] = val;：將新元素val插入到棧頂位置。ps->top表示棧頂指針，ps->base[ps->top]表示棧頂位置的內存地址。這里將新元素val存儲到棧頂位置。
ps->top++;：將棧頂指針ps->top加1，表示棧中元素的數量增加了一個。
2.7 刪除 出棧
bool Pop(Seq_Stack* ps)
{assert(ps != NULL);if (ps == NULL)return false;if (Is_Empty(ps))return false;ps->top--;return true;
}2.8 獲取棧頂元素
ELEM_TYPE Top(Seq_Stack* ps)
{assert(ps != NULL);if (ps == NULL)exit(1);if (Is_Empty(ps))exit(1);return ps->base[ps->top - 1];return true;
}
ps->base[ps->top - 1]：棧頂元素的索引是ps->top - 1，因為ps->top表示棧中元素的數量，而數組索引是從0開始的。因此，ps->base[ps->top - 1]表示棧頂元素的值。
2.9 獲取有效值長度
//5.獲取有效值長度 Size
int Get_length(Seq_Stack* ps)
{assert(ps != NULL);if (ps == NULL)return -1;return ps->top;
}2.10 清空
//6.清空 不需要free
void Clear(Seq_Stack* ps)
{assert(ps != NULL);if (ps == NULL)return;ps->top = 0;
}2.11 銷毀
//7.銷毀 需要free
void Destroy(Seq_Stack* ps)
{assert(ps != NULL);if (ps == NULL)return;free(ps->base);ps->base = NULL;ps->top = ps->stacksize = 0;
}
Destroy函數的作用是銷毀一個順序棧，并釋放它所占用的動態內存。?
調用
free(ps->base)會釋放ps->base指向的內存空間。釋放內存后，這塊內存就不再屬于程序了，程序不能再使用它。
2.12 打印
//8.打印
void Show(Seq_Stack* ps)
{//assertfor (int i = 0; i < ps->top; i++){printf("%c ", ps->base[i]);}printf("\n");
}
ps->base：這是棧底指針，指向棧的起始內存地址。
ps->base[i]：表示棧中第i個元素的值。數組名本質上是一個指向數組首元素的指針。eg：arr和&arr[0]是等價的，都表示數組的起始地址。
2.13 測試
//順序棧測試用例
int main()
{/*srand((unsigned int)time(NULL));int tmp = rand() % 29 + 1;printf("%d\n", tmp);*/Seq_Stack head;Init_Seq_Stack(&head);Push(&head, 'A');Push(&head, 'B');Push(&head, 'C');Show(&head);//A B Cprintf("%c\n", Top(&head));//CPop(&head);//A BShow(&head);//A B return 0;
}
)
