一，什么是棧
棧（Stacks）是限定在一端插入和刪除的線性表。允許插入和刪除的一端稱(chēng)為棧頂（Top），另一端稱(chēng)為棧底（Bottom）。棧中的數(shù)據(jù)元素遵守后進(jìn)先出（Last In First Out）的原則。因此，棧又稱(chēng)為后進(jìn)先出（先進(jìn)后出）線性表。
壓棧：棧的插入操作叫做進(jìn)棧、壓棧、入棧，入數(shù)據(jù)在棧頂。
出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂。
如圖所示：
?二，棧的實(shí)現(xiàn)
棧的實(shí)現(xiàn)一般有兩種存儲(chǔ)方法，順序棧（數(shù)組）和鏈棧（鏈表）。
這里我們采用順序棧。
?
2.1，棧的結(jié)構(gòu)
這里采用支持動(dòng)態(tài)增長(zhǎng)的棧，用a來(lái)指向空間中對(duì)應(yīng)數(shù)組的地址。用top來(lái)表示棧頂，用capcity表示容量，到后面容量不夠擴(kuò)容用。
typedef int SDataType;
typedef struct Stack
{
SDataType* a;//數(shù)組存儲(chǔ)數(shù)據(jù)
int top;//棧頂
int capcity;//容量
}ST;2.2，棧的接口
void STInit(ST* p);//棧的初始化
void STPush(ST* p, SDataType x);//壓棧
bool STEmpty(ST* p);//判斷數(shù)據(jù)是否為空
void STPop(ST* p);//出棧
SDataType STTop(ST* p); //取棧頂數(shù)據(jù)
void STDestroy(ST* p);//棧的銷(xiāo)毀
int STSize(ST* p);//棧的大小三，接口的實(shí)現(xiàn)。
3.1，棧的初始化
這里先申請(qǐng)一個(gè)4個(gè)字節(jié)的空間。容量為4。top可以是0，也可以是1。
void STInit(ST* p)//棧的初始化
{
assert(p);
p->a = (SDataType*)malloc(sizeof(SDataType)*4);
p->top = -1;//top = 0 時(shí)是棧頂?shù)南乱粋€(gè)位置。top =-1 是棧頂?shù)奈恢谩? p->capcity = 4;
}3.2，棧的插入（壓棧）
這里插入數(shù)據(jù)前判斷一下容量是否充足，如果不足，就用realloc擴(kuò)容成原來(lái)容量的2倍。最后將x插入到棧頂中。注意：p->top++;//這里加加后，訪問(wèn)棧頂?shù)脑刂苯涌梢杂胊[p->top]
void STPush(ST* p, SDataType x)//壓棧
{
assert(p);
if (p->capcity == p->top + 1)
{
SDataType* tmp = (SDataType*)realloc(p->a, sizeof(SDataType) * p->capcity * 2);
if (tmp == NULL)
{
perror("realloc fail");
}
p->a = tmp;
p->capcity *= 2;
}
p->a[p->top + 1] = x;
p->top++;//這里加加后，訪問(wèn)棧頂?shù)脑刂苯涌梢杂胊[p->top]
}3.3，出棧
這里在top減一之前需要判斷一下棧是否為空的情況。
void STPop(ST* p)//出棧
{
assert(p);
assert(!STEmpty(p));//判斷是否為空
p->top--;
}棧為空的實(shí)現(xiàn)
這里bool（布爾值）的頭文件為：stdbool.h，如果為空返回1，不為空等號(hào)不成立，返回0；
bool STEmpty(ST* p)
{
assert(p);
return p->top + 1 == 0;
}3.4，獲取棧頂元素
這里還是判斷一下是否為空，然后返回棧頂元素。
SDataType STTop(ST* p) //取棧頂數(shù)據(jù)
{
assert(p);
assert(!STEmpty(p));
return p->a[p->top];
}3.5，棧的大小
這里判斷完非空后，直接返回top+1(看完上面的壓棧程序中，這里可以把top理解成數(shù)組下標(biāo)，加一是總大小)。
int STSize(ST* p)//棧的大小
{
assert(p);
assert(!STEmpty(p));
return p->top + 1;
}3.6，棧的銷(xiāo)毀
把申請(qǐng)的空間釋放，再置為空。其余賦值為0；文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-641299.html
void STDestroy(ST* p)//棧的銷(xiāo)毀
{
assert(p);
free(p->a);
p->a = NULL;
p->capcity = 0;
p->top = 0;
}四，總代碼
//test.h
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>
typedef int SDataType;
typedef struct Stack
{
SDataType* a;//數(shù)組存儲(chǔ)數(shù)據(jù)
int top;//棧頂
int capcity;//容量
}ST;
void STInit(ST* p);//棧的初始化
void STPush(ST* p, SDataType x);//壓棧
bool STEmpty(ST* p);//判斷數(shù)據(jù)是否為空
void STPop(ST* p);//出棧
SDataType STTop(ST* p); //取棧頂數(shù)據(jù)
void STDestroy(ST* p);//棧的銷(xiāo)毀
int STSize(ST* p);//棧的大小
//stack.c接口的實(shí)現(xiàn)
#define _CRT_SECURE_NO_WARNINGS 1
#include"test.h"
void STInit(ST* p)//棧的初始化
{
assert(p);
p->a = (SDataType*)malloc(sizeof(SDataType)*4);
p->top = -1;//top = 0 時(shí)是棧頂?shù)南乱粋€(gè)位置。top =-1 是棧頂?shù)奈恢谩? p->capcity = 4;
}
void STPush(ST* p, SDataType x)//壓棧
{
assert(p);
if (p->capcity == p->top + 1)
{
SDataType* tmp = (SDataType*)realloc(p->a, sizeof(SDataType) * p->capcity * 2);
if (tmp == NULL)
{
perror("realloc fail");
}
p->a = tmp;
p->capcity *= 2;
}
p->a[p->top + 1] = x;
p->top++;
}
void STPop(ST* p)//出棧
{
assert(p);
assert(!STEmpty(p));
p->top--;
}
SDataType STTop(ST* p) //取棧頂數(shù)據(jù)
{
assert(p);
assert(!STEmpty(p));
return p->a[p->top];
}
void STDestroy(ST* p)//棧的銷(xiāo)毀
{
assert(p);
free(p->a);
p->a = NULL;
p->capcity = 0;
p->top = 0;
}
int STSize(ST* p)//棧的大小
{
assert(p);
assert(!STEmpty(p));
return p->top + 1;
}
bool STEmpty(ST* p)
{
assert(p);
return p->top + 1 == 0;
}
//test.c接口的測(cè)試
#define _CRT_SECURE_NO_WARNINGS 1
#include"test.h"
int main()//測(cè)試
{
ST s;
STInit(&s);
STPush(&s, 0);
printf("%d\n", STTop(&s));
STPush(&s, 1);
printf("%d\n", STTop(&s));
STPush(&s, 2);
printf("%d\n", STTop(&s));
STPush(&s, 3);
printf("%d\n", STTop(&s));
STPop(&s);
STPop(&s);
printf("%d\n", STTop(&s));
printf("%d\n", STSize(&s));
return 0;
}好了，到這里就該結(jié)束了。希望對(duì)大家有所幫助！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-641299.html
到了這里，關(guān)于一篇文章帶你實(shí)現(xiàn)棧的接口的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
