創建一個堆疊之前，我們需要先想好堆疊的特點以及堆疊如何去使用更加方便，堆疊可以用順序表或者鏈表的方式來實作，我們考慮一下順序表和鏈表在創建堆疊時分別會有什么優缺點，
鏈堆疊按需申請空間，不會造成空間浪費，需要存盤一個指標消耗一定空間，
順序堆疊無法按需申請空間，可能會造成空間浪費，但只需存盤資料，并且空間連續，空間利用率高，
由于順序堆疊和鏈堆疊的插入和洗掉操作時間復雜度都是O(1)，所以如果所堆疊元素的數目會在使用程序中發生較大的改變，我們一般使用鏈堆疊，而倘如我們堆疊的元素數目是固定不變的，則最好采用順序堆疊的方式來存盤，
對于小白來說，順序堆疊可能會更好理解，并且順序表和鏈表各有優缺，所以在此使用順序表建立堆疊，
首先需要考慮的是一個堆疊的結構體需要什么，我們需要堆疊頂的元素，所以用一個top變數記錄，我們存盤元素需要陣列，記錄陣列大小需要一個size變數，
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
STDataType top;
STDataType capacity;
}ST;
這樣一個堆疊的結構體就建立好了，
一個堆疊的基本功能應該有這些：
void StackInit(ST* ps);
void StackDestory(ST* ps);
void Stackpush(ST* ps, STDataType);
void StackPop(ST* ps);
STDataType Stacktop(ST* ps);
int Stacksize(ST* ps);
bool StackEmpty(ST* ps);
初始化、銷毀、插入、洗掉、回傳堆疊頂元素、回傳堆疊的大小、判斷堆疊是否為空，
初始化：
void StackInit(ST* ps)
{
assert(ps);//結構體指標不為空
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
銷毀：
void StackDestory(ST* ps)
{
assert(ps);
free(ps->a);
ps->capacity = 0;
ps->top = 0;
}
插入：
void Stackpush(ST* ps, STDataType x)
assert(ps);
if (ps->top == ps->capacity)//當堆疊頂的位置等于堆疊的大小時堆疊就滿了需要擴容，
{
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
//如果此時堆疊為空先申請四個空間，不為空申請兩倍空間，
STDataType* tmp = (ST*)realloc(ps->a, sizeof(STDataType)*newCapacity);
//創建一個變數把申請的空間給他
if (tmp == NULL)
{
printf("realloc fail");
exit(-1);
}
ps->a = tmp;//把tmp空間給陣列
ps->capacity = newCapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
洗掉：
void StackPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);//堆疊頂位置必須大于0
ps->top--;
}
其他：
int Stacksize(ST* ps)
{
assert(ps);
return ps->top;
}
bool StackEmpty(ST* ps)
{
return ps->top<=0;
}
STDataType Stacktop(ST* ps)
{
return ps->a[ps->top];
}
這樣就把一個堆疊和堆疊的功能創建完了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/353398.html
標籤：其他
上一篇：搞懂緩沖區，看這篇文章就夠了