堆疊
- 前言
- 1、堆疊的定義
- 2、堆疊的基本實作
- 頭檔案
- 1. 初始化
- 2. 入堆疊
- 3. 出堆疊
- 4. 獲取堆疊頂元素
- 5. 檢查站中有效個數
- 6. 檢查堆疊是否為空
- 7. 銷毀堆疊
- 面試題
- 擴展
| 目錄 | 目錄 |
|---|---|
| 順序表 | 單鏈表（不帶附加頭結點） |
| 雙鏈表（帶附加頭結點） | 堆疊（順序表實作） |
前言
大家好，上一次我們學習到了雙鏈表，今天我們來學習堆疊的一些性質和注意事項，
1、堆疊的定義
- 堆疊是一種先進后出并且只能在末端進行插入和洗掉的線性表，允許插入和洗掉的一端叫堆疊頂(top)，而不允許插入和洗掉的另一端叫堆疊底(bottom)，
- 堆疊一般是用順序表實作的，因為只考慮在堆疊頂進行插入和洗掉，獲取也是獲取的堆疊頂元素，不需要考慮其他位置，
2、堆疊的基本實作
頭檔案
#pragma once // 防止頭檔案重復包含
#include<stdio.h>
#include<assert.h> // 斷言檢查頭檔案
#include<stdlib.h> // 動態記憶體函式頭檔案
#include<stdbool.h> // bool頭檔案
// 下面是定長的靜態堆疊的結構，實際中一般不實用，所以我們主要實作下面的支持動態增長的堆疊
//typedef int STDataType;
//#define N 10
//typedef struct Stack
//{
// STDataType a[N];
// int top; // 堆疊頂
//}Stack;
// 支持動態增長的堆疊
typedef int STDataType;
typedef struct Stack
{
STDataType* a; // 指標形式，可以進行擴容
int top; // 堆疊頂
int capacity; // 容量
}Stack;
1. 初始化
void StackInit(Stack* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
2. 入堆疊
- 入堆疊只能在堆疊頂入堆疊，這里實作用的是陣列，所以是在陣列末尾入堆疊的，
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
if (ps->top == ps->capacity) // 若順序表滿了，就擴容
{
STDataType newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; // 設定新容量進行擴容
STDataType* ps1 = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType)); // 給指標ps->a 進行擴容
if (ps1 == NULL) // 檢查記憶體是否分配成功
{
perror("realloc"); // 錯誤報警資訊
exit(-1); // 退出
}
ps->a = ps1; // 申請記憶體成功，賦給ps->a
ps->capacity = newcapacity; // 容量等于新的容量
}
ps->a[ps->top] = data; // 堆疊頂賦新值
ps->top++; // 有效個數 +1
}
3. 出堆疊
- 出堆疊也是從堆疊頂出元素，洗掉堆疊頂的元素，既為出堆疊，在這里依然是洗掉陣列末尾的元素即可，所以實作起來比較簡單，直接檢查堆疊是否為空，有效個數 -1 即可，
void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));// 檢查堆疊是否為空
--ps->top;// 有效個數 -1
}
4. 獲取堆疊頂元素
- 獲取堆疊頂元素，檢查堆疊是否為空，然后回傳堆疊頂元素（末尾元素）即可，
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->a[ps->top - 1];
}
5. 檢查站中有效個數
- 回傳top即可，
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
6. 檢查堆疊是否為空
- 檢測堆疊是否為空，如果為慷訓傳非零結果，如果不為慷訓傳0，
int StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
7. 銷毀堆疊
- 釋放 ps->a，防止記憶體泄漏，
void StackDestroy(Stack* ps)
{
assert(ps);
if (ps->a) // 檢查是否為空，不為空就釋放
{
free(ps->a); // 防止記憶體泄漏
}
ps->a = NULL; // 置空，防止變成野指標
ps->top = 0;
ps->capacity = 0;
}
面試題
學了堆疊，可以做一道括號匹配題來檢驗你是否學會了，鏈接：有效的括號.
擴展
學到這，想必大家都知道堆疊是比較簡單的線性表，但它是一種最常用和最重要的資料結構，用途是非常廣泛的，
例如：
- 匯編處理程式中的句法識別和運算式計算就是基于堆疊實作的，
- 堆疊還經常使用在函式呼叫時的引數傳遞和函式值的回傳方面，
下來之后，大家可以自己去了解了解堆疊的作用哦，這里就不多說了，
原始碼鏈接：gitee.
ps：制作不易，記得三連！！！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/293607.html
標籤：其他