系列文章目錄
文章目錄
- 系列文章目錄
- 前言
- 一、堆疊的概念及結構
- 1.堆疊的概念
- 2.堆疊的結構
- 二、堆疊的實作
- 1.定義陣列動態增長的堆疊struct Stack
- 2.初始化堆疊StackInit函式
- 3.銷毀堆疊StackDestroy函式
- 4.入堆疊StackPush函式
- 5.出堆疊StackPop函式
- 6.獲取堆疊頂資料StackTop函式
- 7.判斷堆疊是否為空StackEmpty函式
- 8.求出堆疊的大小StackSize函式
- 總結
前言
一、堆疊的概念及結構
1.堆疊的概念
堆疊：一種特殊的線性表，其只允許在固定的一端進行插入和洗掉元素操作，進行資料插入和洗掉操作的一端稱為堆疊頂，另一端稱為堆疊底，堆疊中的資料元素遵守后進先出LIFO（Last In First Out）的原則，
壓堆疊：堆疊的插入操作叫做進堆疊/壓堆疊/入堆疊，入資料在堆疊頂，
出堆疊：堆疊的洗掉操作叫做出堆疊，出資料也在堆疊頂，
2.堆疊的結構
二、堆疊的實作
堆疊的實作一般可以使用陣列或者鏈表實作，相對而言陣列的結構實作更優一些，因為陣列在尾上插入資料的代價比較小，
1.定義陣列動態增長的堆疊struct Stack
代碼如下：
typedef int STDataType;
struct Stack //動態增長的堆疊
{
STDataType* a;
int top; //堆疊頂
int capacity; //容量
};
2.初始化堆疊StackInit函式
先給堆疊分配4個容量的空間，方便以后擴容，
代碼如下：
void StackInit(struct Stack* pst)
{
assert(pst);
pst->a = (STDataType*)malloc(sizeof(STDataType)* 4);
pst->top = 0;
pst->capacity = 4;
}
3.銷毀堆疊StackDestroy函式
釋放出動態增加的空間，防止記憶體泄露
代碼如下：
void StackDestroy(struct Stack* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->a = pst->capacity = 0;
}
4.入堆疊StackPush函式
首先判斷堆疊的容量，然后在堆疊頂寫入資料，
代碼如下：
void StackPush(struct Stack* pst, STDataType x)
{
assert(pst);
if (pst->top == pst->capacity) //容量不夠則增加容量
{
STDataType* tmp = (STDataType*)realloc(pst->a,sizeof(STDataType)*pst->capacity * 2);
if (tmp == NULL)
{
printf("開辟空間失敗!\n");
exit(-1); //0是正常退出，-1是例外退出
}
pst->a = tmp;
pst->capacity = pst->capacity * 2;
}
pst->a[pst->top] = x;
pst->top++;
}
5.出堆疊StackPop函式
在堆疊頂洗掉資料，注意判斷堆疊是否為空，
代碼如下：
void StackPop(struct Stack* pst)
{
assert(pst);
assert(!(StackEmpty(pst)));
pst->top--;
}
6.獲取堆疊頂資料StackTop函式
代碼如下：
STDataType StackTop(struct Stack* pst)
{
assert(pst);
assert(!(StackEmpty(pst)));
return pst->a[pst->top - 1]; //top減一就是堆疊頂資料
}
7.判斷堆疊是否為空StackEmpty函式
直接看堆疊頂top是否有資料
代碼如下：
bool StackEmpty(struct Stack* pst)
{
assert(pst);
return pst->top == 0;
}
8.求出堆疊的大小StackSize函式
其中top從0開始top的大小就是堆疊中資料的多少
代碼如下：
STDataType StackSize(struct Stack* pst)
{
return pst->top;
}
結果：
總結
以上就是今天要講的內容，本文僅僅簡單介紹了資料結構中堆疊的的使用，對于堆疊提供了一些簡便方法幫助我們解題，能使我們快速便捷地處理資料的函式和方法，另外這個結構雖然結構復雜，但是使用代碼實作起來更容易寫，以后會發現結構會帶來很多優勢，我們務必掌握，另外，如果有需要原始碼的私信我即可，還有，，如果上述有任何問題，請懂哥指教，不過沒關系，主要是自己能堅持，更希望有一起學習的同學可以幫我指正，但是如果可以請溫柔一點跟我講，愛與和平是永遠的主題，愛各位了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/279853.html
標籤：其他