順序棧

一、相關概念

1. 棧和隊列是操作受限的線性表，是限定性的數據結構；
2. 棧分為順序棧和鏈式棧
3. 棧只能在一端進行操作（插入、刪除）
4. 棧是限定僅在表尾進行插入或刪除操作的線性表，因此，對棧來說，表尾端具有特殊含義，稱為棧頂（top），相應的，表頭端稱為棧底（bottom）
5. 不含元素的空表稱為空棧

二、順序棧的結構

typedef struct Stack
{int* base; //指向動態內存int top; //棧頂指針，實際上是下標int stacksize; //棧的總大小
}Stack, *PStack;

三、順序棧的實現

#define INIT_SIZE 10
//初始化
void InitStack(PStack ps)
{assert(ps != NULL);ps->base = (int*)malloc(INIT_SIZE * sizeof(int*));ps->top = 0;ps->stacksize = INIT_SIZE;
}
static bool IsFull(PStack ps)
{return ps->top == ps->stack;
}
static void Inc(PStack ps)
{ps->stacksize *= 2;ps->base = (int*)realloc(ps->base, ps->stacksize * sizeof(int));assert(ps->base != NULL); 
}
//入棧操作
bool Push(PStack ps, int val)
{assert(ps != NULL);if(IsFull)Inc(ps);ps->base[ps->top++] = val;return true;
}
//獲取棧頂元素的值，但是不刪除
//輸出參數
bool GetTop(PStack ps, int *rtval)
{assert(ps != NULL);if(IsEmpty(ps))return false;*rtval = ps->base[ps->top - 1];return true;
}
//獲取棧頂元素的值，但是刪除
bool Pop(PStack ps, int *rtval)
{assert(ps != NULL);if(IsEmpty(ps))return false;*rtval = ps->base[--ps->top];return true;
}
//判空
bool IsEmpty(PStack ps)
{return ps->top == 0;
}
//獲取棧中有效元素的個數
int GetLength(PStack ps)
{assert(ps != NULL);return ps->top;
}
//清空所有的數據
void Clear(PStack ps)
{assert(ps != NULL);ps-> top = 0;
}
//銷毀
void Destroy(PStack ps)
{assert(ps != NULL);free(ps->base);ps->base = NULL;ps->top = 0;ps-> =stacksize;
}

四、順序棧的總結

1. 棧的特點：后進后出，后來的反而需要先服務（訪問受限的線性表）
2. 棧又分為順序棧和鏈式棧
3. 本篇順序棧為不定長的順序棧，能自動擴容
4. 棧只能在一端進行插入和刪除，插入和刪除這一端稱之為棧頂，另一端稱之為棧底
5. 順序棧的棧頂在尾部，因為入棧和出棧的時間復雜度為O(1)