1 棧的概念及結構
棧是一種特殊的線性表，其特點是只允許在固定的一端進行插入和刪除操作。進行操作的一端稱為棧頂，另一端稱為棧底。
棧中的元素遵循后進先出（LIFO，Last In First Out）?原則。
- 壓\入\進棧（Push）：在棧頂插入元素的操作
- 出棧（Pop）：從棧頂刪除元素的操作
?
2 棧的實現
棧可以通過數組或鏈表實現，數組實現更為高效（尾插尾刪的時間復雜度為 O (1)）。
?
2.1 棧的結構定義及聲明
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>typedef STDataType;//定義
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;// 初始化
void STInit(ST* pst);// 銷毀
void STDestroy(ST* pst);// 插入數據（入棧）
void STPush(ST* pst, STDataType x);//刪除數據（出棧）
void StackPop(ST* pst);// 獲取棧頂元素
STDataType STTop(ST* pst);// 棧的判空
bool STEmpty(ST* pst);// 棧的大小(獲取棧中數據個數)
int STSize(ST* pst);2.2 核心操作實現
1.初始化
// 初始化
void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = 0; // 設定初始棧頂為0，表示無元素ps->capacity = 0;
}2.銷毀
// 銷毀
void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}3.入棧操作
原本棧為空時，top 為-1，為了便于寫代碼，令為 0
?原本 top 指向棧頂元素的，沒有元素時候，指向 -1，不指向 0。
所以對于上述兩種情況，
情況一：
top 指向棧頂數據。
情況二：
top 指向棧頂數據的下一個位置。
// 插入數據（入棧）
void STPush(ST* ps, STDataType x)
{assert(ps);// 檢查容量，不足則擴容if (ps->top == ps->capacity)//相等就擴容{int newCapacity = ps->capacity == 0 ? 4 : ps->capacity* 2;//最初時候都是0，剛開始開空間開4個STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity = newCapacity;}// 存入數據后棧頂上移ps->a[ps->top] = x;ps->top++;
}
4.出棧操作
void StackPop(ST* ps)
{assert(ps);// 棧頂下移即完成出棧 ps->top--;
}
5.獲取棧頂元素
// 獲取棧頂元素
STDataType STTop(ST* ps)
{assert(ps);//assert(!STEmpty(ps));assert(ps->top > 0);//避免空棧return ps->a[ps->top - 1];
}6.棧的判空
// 棧的判空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}?7.棧的大小
// 棧的大小(獲取棧中數據個數)
int STSize(ST* ps)
{assert(ps);return ps->top;
}
2.3 測試一下
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"int main()
{ST s;STInit(&s);STPush(&s, 1);STPush(&s, 2);STPush(&s, 3);STPush(&s, 4);//訪問元素while (!STEmpty(&s)){printf("%d ", STTop(&s));STPop(&s);}STDestroy(&s);return 0;
}
?
