建站
咨詢
售后
建站咨詢
新聞中心
- 棧的定義
- 棧的接口
- 元素定義
- 初始化
- 數(shù)據(jù)入棧
- 數(shù)據(jù)出棧
- 獲取棧頂元素
- 是否為空
- 銷毀棧
- 完整代碼
棧的接口棧是允許在同一端進(jìn)行插入和刪除操作的特殊線性表。允許進(jìn)行插入和刪除操作的一端稱為棧頂 (top)，另一端為棧底 (bottom)；棧底固定，而棧頂浮動(dòng)；棧中元素個(gè)數(shù)為零時(shí)稱為空棧。特點(diǎn)是：先進(jìn)后出，后進(jìn)先出。
首先我們先來看將使用3個(gè)數(shù)據(jù){2，3，4}形成棧的示意圖：
由定義可知，棧是線性表，可以分為順序存儲(chǔ)結(jié)構(gòu)（順序表）和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（鏈表）來實(shí)現(xiàn)，下面我們用數(shù)組來實(shí)現(xiàn)，即實(shí)現(xiàn)它的順序存儲(chǔ)結(jié)構(gòu)，其次我們知道他是可以獲取堆頂元素的，所以我們還需要一個(gè)top指針記錄棧頂?shù)奈恢茫ㄟ@個(gè)不是真正意義上的指針，而是記錄棧頂元素的位置），且因?yàn)槲覀兪莿?dòng)態(tài)開辟實(shí)現(xiàn)棧，所以我們還需要一個(gè)capacity來記錄當(dāng)前的元素個(gè)數(shù)（相當(dāng)于size),以檢查是否需要進(jìn)行擴(kuò)容
定義如下：
typedef int Datatype; //此處是為了方便棧存放不同的元素類型
typedef struct Stack {Datatype* a; //管理數(shù)組
int top;//棧頂元素下標(biāo)
int capacity;//記錄當(dāng)前容量大小
}Stack;棧的初始化就較為簡單了，將a置空（相當(dāng)于初始化），top和capacity=0,
即可
代碼實(shí)現(xiàn)如下：
//初始化函數(shù)
void InitStack(Stack* st)
{assert(st);
st->a = NULL;
st->capacity = 0;
st->top = -1; //指向棧頂元素
}這里的top=-1,表示的狀態(tài)是數(shù)組中沒有元素，因?yàn)橛性氐脑挘热缯f如果數(shù)組中有一個(gè)元素，top就等于0，即數(shù)組第一個(gè)元素的下標(biāo)位置
數(shù)據(jù)入棧數(shù)據(jù)入棧的操作就是，將新值插入到數(shù)組末尾，然后更新top和capacity，
代碼如下：
//入棧
void Push(Stack* st,Datatype x)
{assert(st);
if (st->capacity == (st->top + 1))
{int newcapacity = st->capacity == 0 ? 4 : 2 * st->capacity;
Datatype* tmp = (Datatype*)realloc(st->a,sizeof(Datatype) * newcapacity);
if (tmp == NULL) //開辟失敗，tmp會(huì)指向空
{ printf("realloc failed\n");
exit(-1);//終止程序
}
st->a = tmp;
st->capacity = newcapacity;
}
st->a[++st->top] = x;
}數(shù)據(jù)出棧實(shí)現(xiàn)也很簡單，我們直接邏輯刪除，就是將capacity–，元素的值其實(shí)還在數(shù)組中，只是我們假裝看不見 😐 ,但簡單是簡單這里還是有坑點(diǎn)的，就是我們刪除數(shù)據(jù)的時(shí)候，如果棧已經(jīng)空了，我們還進(jìn)行刪除操作，就會(huì)影響后續(xù)的使用，所以我們每次都要先判斷棧是否為空
代碼實(shí)現(xiàn)如下：
//出棧
void Pop(Stack* st)
{assert(st);
if (!empty(st))
{--st->top;
}
}這里提一下，我們函數(shù)實(shí)現(xiàn)時(shí)判斷一些空指針或者不可進(jìn)行操作的情況時(shí)，例如：下面當(dāng)棧為空時(shí)還去獲取棧頂元素。這些情況的判斷最好都用assert去判斷，因?yàn)楫?dāng)我們代碼行數(shù)多起來時(shí)，那個(gè)接口出了問題，會(huì)馬上被顯示出來還有行號(hào)。
例：
如果棧中沒有數(shù)據(jù)，而我們還去獲取棧頂元素，他不僅會(huì)報(bào)錯(cuò)而且還會(huì)告訴我們哪個(gè)位置出的錯(cuò)
代碼實(shí)現(xiàn)：
//拿到棧頂元素
Datatype top(Stack* st)
{assert(st);
//if (!empty(st))//此處也可用assert
//{// return st->a[st->top];
//}
assert(!empty(st));
return st->a[st->top];
}這里注意如果要使用c++中的bool類型，要印=引頭文件
//檢查是否為空
bool empty(Stack* st)
{assert(st);
return st->top == -1;//為0即為空 為真true
}銷毀棧的操作其實(shí)就是在初始化的基礎(chǔ)上，將我們數(shù)據(jù)入棧時(shí)，為我們的數(shù)組管家a動(dòng)態(tài)開辟的內(nèi)存空間釋放掉，這里如果單純置空而不進(jìn)行釋放操作，會(huì)造成內(nèi)存泄漏
//銷毀棧
void Destroy(Stack* st)
{assert(st);
free(st->a);
st->a = NULL;
st->capacity = 0;
st->top = -1;
}//初始化函數(shù)
void InitStack(Stack* st)
{assert(st);
st->a = NULL;
st->capacity = 0;
st->top = -1;//指向棧頂元素
}
//入棧
void Push(Stack* st,Datatype x)
{assert(st);
if (st->capacity == (st->top + 1))
{int newcapacity = st->capacity == 0 ? 4 : 2 * st->capacity;
Datatype* tmp = (Datatype*)realloc(st->a,sizeof(Datatype) * newcapacity);
if (tmp == NULL)
{ printf("realloc failed\n");
exit(-1);//終止程序
}
st->a = tmp;
st->capacity = newcapacity;
}
st->a[++st->top] = x;
}
//出棧
void Pop(Stack* st)
{assert(st);
if (!empty(st))
{--st->top;
}
}
//檢查是否為空
bool empty(Stack* st)
{assert(st);
return st->top == -1;//為0即為空 為真true
}
//拿到棧頂元素
Datatype top(Stack* st)
{assert(st);
//if (!empty(st))//此處也可用assert
//{// return st->a[st->top];
//}
assert(!empty(st));
return st->a[st->top];
}
//銷毀棧
void Destroy(Stack* st)
{assert(st);
free(st->a);
st->a = NULL;
st->capacity = 0;
st->top = -1;
}
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
當(dāng)前題目：c語言模擬實(shí)現(xiàn)棧（動(dòng)圖演示）-創(chuàng)新互聯(lián)
分享URL：http://ef60e0e.cn/article/ccpeps.html
