引言

? ? ? ? 動態模擬實現棧的各個接口

一、棧的概念與結構

????????棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數據插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數據元素遵守后進先出LIFO（LastInFirstOut）的原則。

壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數據在棧頂。

出棧：棧的刪除操作叫做出棧。出數據也在棧頂。?

棧底層結構選型

????????棧的實現?般可以使用數組或者鏈表實現，相對而言數組的結構實現更優一些。因為數組在尾上插入數據的代價比較小。而且與鏈表的結構體相比，數組所占內存的較小。?

?二、棧的模擬實現

因為棧是用動態數組來模擬實現的，所以順序表要是會的話，這個是很簡單的

分三個文件來寫：以代碼注釋為主

test.c //測試文件，測試棧的接口是否正確
Stack.h //實現棧所需要的所有的頭文件（核心）
Stack.c //實現棧各個接口的代碼（核心）

1、在Stack.h中定義棧的結構：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int STDataType;  //取別名，方便以后修改數據類型typedef struct Stack
{STDataType* arr;   //數組int top;           //棧的有效元素個數int capacity;      //棧的總大小
}ST;                   //取別名，方便下面代碼的書寫

2、棧的初始化、入棧

//初始化
void StackInit(ST* ps)
{ps->arr = NULL;      //先將數組指針設置為NULLps->top = ps->capacity = 0; //都是0
}//入棧 -- 棧頂入棧
void StackPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity) //空間不夠先增容{int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; //以二倍方式擴容STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;  //將擴容后的地址給Stack的arrps->capacity = newCapacity;  //修改空間大小;}ps->arr[ps->top++] = x; //賦值
}

3、判斷棧是否為空、出棧操作

//判斷棧是否為空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//出棧 -- 棧頂出棧
void StackPop(ST* ps)
{assert(!StackEmpty(ps));--ps->top;  //將棧頂減一
}

4、取棧頂元素（不出棧）、獲取棧中有效元素個數

//取棧頂元素（不出棧）
STDataType StackTop(ST* ps)
{assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}
//獲取棧中有效元素個數
int StackSize(ST* ps)
{return ps->top;
}

5、銷毀棧?

//摧毀
void StackDestory(ST* ps)
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->top = ps->capacity = 0;
}

3、所有代碼：

Stack.h中的代碼：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int STDataType;  //取別名，方便以后修改數據類型typedef struct Stack
{STDataType* arr;   //數組int top;           //棧的有效元素個數int capacity;      //棧的總大小
}ST;                   //取別名，方便下面代碼的書寫//初始化
void StackInit(ST* ps);//摧毀
void StackDestroy(ST* ps);//入棧 -- 棧頂入棧
void StackPush(ST* ps, STDataType x);//判斷棧是否為空
bool StackEmpty(ST* ps);//出棧 -- 棧頂出棧
void StackPop(ST* ps);//取棧頂元素（不出棧）
STDataType StackTop(ST* ps);//獲取棧中有效元素個數
int StackSize(ST* ps);

Stack.c文件中的代碼：

#include"Stack.h"//初始化
void StackInit(ST* ps)
{ps->arr = NULL;      //先將數組指針設置為NULLps->top = ps->capacity = 0; //都是0
}//入棧 -- 棧頂入棧
void StackPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity) //空間不夠先增容{int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; //以二倍方式擴容STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;  //將擴容后的地址給Stack的arrps->capacity = newCapacity;  //修改空間大小;}ps->arr[ps->top++] = x; //賦值
}//判斷棧是否為空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//出棧 -- 棧頂出棧
void StackPop(ST* ps)
{assert(!StackEmpty(ps));--ps->top;  //將棧頂減一
}//取棧頂元素（不出棧）
STDataType StackTop(ST* ps)
{assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}
//獲取棧中有效元素個數
int StackSize(ST* ps)
{return ps->top;
}//摧毀
void StackDestory(ST* ps)
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->top = ps->capacity = 0;
}

test.c文件中的代碼：

#include"Stack.h"int main()
{ST st;StackInit(&st);StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);StackPop(&st);StackPop(&st);int size = StackSize(&st);printf("%d ", size);while (!StackEmpty(&st)){StackPop(&st);size = StackSize(&st);printf("%d ", size);}return 0;
}