資料結構之堆疊詳解
文章目錄
- 資料結構之堆疊詳解
- 一、堆疊的概念及結構
- 二、堆疊的實作
- 1.基本結構
- 2.增刪查改基本操作
- (1)初始化及銷毀
- (2)入堆疊出堆疊
- (3)判空和有效個數
- (4)回傳堆疊頂元素
- 總結：堆疊的操作相較于鏈表比較簡單，同時堆疊的應用也很多，比如括號匹配問題，運算式求值，模擬遞回問題等等，下一篇文章來詳細介紹，
一、堆疊的概念及結構
- 堆疊：一種特殊的「線性表」，其只允許在 『 固定 』的一端進行插入和洗掉元素操作，進行資料插入和洗掉操作的一端稱為 『 堆疊頂 』，另一端稱為 『 堆疊底 』，堆疊中的資料元素遵守『 后進先出LIFO 』（Last In First Out）的原則，
- 壓堆疊：堆疊的插入操作叫做進堆疊/壓堆疊/入堆疊，入資料在『 堆疊頂 』，
- 出堆疊：堆疊的洗掉操作叫做出堆疊，出資料也在『 堆疊頂 』，
二、堆疊的實作
1.基本結構
- 堆疊的實作一般可以使用陣列或者鏈表實作，相對而言陣列的結構實作更優一些，因為陣列在尾上插入資料的 代價比較小，
- 并且堆疊也可以分為『 靜態堆疊 』（容量有限）和『 動態堆疊 』（可以擴容）
// 下面是定長的靜態堆疊的結構，實際中一般不實用，所以我們主要實作下面的支持動態增長的堆疊
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;
- 那么我們以動態堆疊為例接下來說明基本操作，
2.增刪查改基本操作
(1)初始化及銷毀
- 這里注意初始化堆疊_capacity 表示最大容量初始為零，_top表示堆疊頂 可以初始化為0或者-1.
如果是0，那么注意第一個有效元素就是 ps->_capacity[ ps->_top ]；
如果是-1，那么注意第一個有效元素就是 ps->_capacity[ ps->_top+1 ]；
// 初始化堆疊
void StackInit(Stack* ps)
{
ps->_a = NULL;
ps->_capacity = ps->_top = 0;
}
// 銷毀堆疊
void StackDestroy(Stack* ps)
{
ps->_capacity = ps->_top = 0;
free(ps->_a);
ps->_a = NULL;
}
(2)入堆疊出堆疊
- 入堆疊首先判斷ps是否為空，其次判斷容量如果是0需要附一個初始值，那么這里假設為4，如果容量不為0 ，則正常2倍擴容，并把新資料賦值，
// 入堆疊
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
if (ps->_capacity == ps->_top)
{
int newcap = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
ps->_a = (STDataType*)realloc(ps->_a,sizeof(STDataType) * 2 * newcap);
ps->_capacity = newcap;
}
ps->_a[ps->_top++] = data;
}
// 出堆疊
void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->_top--;
}
(3)判空和有效個數
// 檢測堆疊是否為空，如果為慷訓傳非零結果，如果不為慷訓傳0
int StackEmpty(Stack* ps)
{
assert(ps);
return ps->_top == 0;
}
// 獲取堆疊中有效元素個數
int StackSize(Stack* ps)
{
assert(ps);
return ps->_top;
}
(4)回傳堆疊頂元素
// 獲取堆疊頂元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->_a[ps->_top - 1];
}
總結：堆疊的操作相較于鏈表比較簡單，同時堆疊的應用也很多，比如括號匹配問題，運算式求值，模擬遞回問題等等，下一篇文章來詳細介紹，
測驗樣例：void test()
{
Stack s;
StackInit(&s);
StackPush(&s, 1);
StackPush(&s, 2);
StackPush(&s, 3);
StackPush(&s, 4);
printf("%d\n", StackSize(&s));
printf("%d ", StackTop(&s));
StackPop(&s);
printf("%d ", StackTop(&s));
StackPop(&s);
printf("%d ", StackTop(&s));
StackPop(&s);
printf("%d ", StackTop(&s));
StackPop(&s);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/341880.html
標籤：其他
上一篇：演算法開啟小碼農雙鏈表血脈