堆疊
文章目錄
- 堆疊
- 一、堆疊是什么，為什么使用堆疊
- 二、堆疊的介面
- 1. 初始化堆疊
- 2. 進堆疊
- 3. 銷毀堆疊
- 4. 出堆疊
- 5. 找到堆疊頂的元素
一、堆疊是什么，為什么使用堆疊
在記憶體的存盤中了解到壓堆疊和出堆疊，這種類似的資料結構中也有
堆疊是限定僅在表尾進行插入或者洗掉操作的線性表，
堆疊中的資料元素遵守后進先出LIFO（Last In First Out）的原則
圖片即可解釋，凡是具有LIFO特征的問題都可以運用堆疊的資料結構和思維來求解，
壓堆疊：堆疊的插入操作叫做進堆疊/壓堆疊/入堆疊，
進入的資料在堆疊頂出堆疊：堆疊的洗掉操作叫做出堆疊，
洗掉的資料也在堆疊頂
二、堆疊的介面
為什么使用陣列來作為堆疊呢因為讀取資料時，會先從快取區讀取，而陣列是連續的，而且realloc會開辟2倍（約定的擴容倍數）使得每次都有加載到快取區，而鏈表時一個一個malloc的快取區利用不佳
1. 初始化堆疊
//初始化堆疊
void StackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->capacity = 0;//堆疊容量0
ps->top = 0;//堆疊頂還是0
}
2. 進堆疊
真的和以前寫的順序表一模一樣，直接照搬！
順序表代碼傳送門：順序表原始碼gitee地址
//進堆疊
void StackPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
//滿了需要擴容
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
ST* tmp = (ST*)realloc(ps->a, newcapacity * sizeof(ST));
if (tmp == NULL)
{
exit(-1);
}
ps = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top] = x;
ps->top++;
ps->capacity++;
}
測驗結果：1-4很好的入堆疊了，且是按順序的
3. 銷毀堆疊
輕車熟路！
//銷毀堆疊
void StackDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
銷毀地址，無法訪問（變灰色）
4. 出堆疊
//出堆疊
void StackPop(ST* ps)
{
assert(ps);
ps->top--;
}
非常簡短，將top值減1就行
5. 找到堆疊頂的元素
計算堆疊中元素個數
//堆疊中元素個數
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
判斷堆疊是否已經空了
//判斷堆疊是否為空
bool StackEmpty(ST* ps)
{
return ps->top == 0;
}
最后找到堆疊頂
//找到堆疊頂
STDataType StackTop(ST* ps)
{
assert(ps);
//assert(ps->top);
assert(!StackEmpty(ps));
return ps->a[ps->top - 1];
}
此圖也可以說明，堆疊的出堆疊和進堆疊方式
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/342209.html
標籤：其他
上一篇：【資料結構初階】堆疊