棧的定義
棧實際上也是線性表暇检，只不過是一種特殊的線性表。其特殊性在于棧的基本操作是線性表操作的子集婉称，他們的操作受限于線性表块仆，可稱為限定性的數(shù)據(jù)結構。
棧(stack)是限定僅在表尾進行插入和刪除操作的線性表王暗，它是一種后進先出(Last in First out ,LIFO)的線性表
棧的特性
- 允許插入和刪除的一段稱為棧頂(top)悔据，另外一段稱為棧底(bottom)。
- 不含任何數(shù)據(jù)元素的棧稱為空棧俗壹。
- 棧的元素必須后進先出科汗。
棧的操作
- 插入操作
棧的插入操作(Push)，叫做進棧绷雏，也稱壓棧头滔、入棧。
進棧 - 刪除操作
棧的刪除操作(Pop)涎显，叫做出棧坤检，也稱彈棧。
出棧
棧的順序存儲結構及實現(xiàn)
棧的本質是一個線性表期吓，線性表有兩種存儲形式早歇，棧也分為棧的順序存儲結構和棧的鏈式存儲結構
在操作棧的時候，棧會有三種情況：棧普通情況讨勤、空棧箭跳、棧滿。
棧的三種情況
定義一個順序順序存儲結構
#include <stdio.h>
#include <stdlib.h>
#define OK 1;
#define ERROR 0;
#define TRUE 1;
#define FALSE 0;
#define STACK_INIT_SIZE 100 /* 初始化椞肚В空間為 100 */
#define STACKINCREMENT 10
typedef int Status; /*Status是函數(shù)的類型谱姓，其值是函數(shù)結果狀態(tài)碼，如OK等*/
typedef int ElemType;
typedef struct {
ElemType * base; /* 指向棧底的指針變量 */
ElemType * top; /* 指向棧頂?shù)闹羔樧兞?*/
int stackSize; /* 棧的當前可使用的最大容量 */
}sqStack;
也可以這樣聲明
typedef struct {
ElemType data[MAXSIZE];
int top; /* 用于標注棧頂?shù)奈恢?*/
int stackSize; /* 棧的當前可使用的最大容量 */
}sqStack;
創(chuàng)建一個順序順序存儲結構的棧
#define STACK_INIT_SIZE 100 /* 初始化椗偾纾空間為 100 */
/**
* 創(chuàng)建棧
*/
void initStack(sqStack *s){
s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
if (!s->base) exit(0);
s->top = s->base; /* 最開始逝段，棧頂就是棧底 */
s->stackSize = STACK_INIT_SIZE;
}
一、入棧操作
/**
* 入棧操作
*/
Status Push(sqStack * s, ElemType e){
if (s->top - s->base >= s->stackSize) { //棧滿 割捅，追加空間
s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType));
if (!s->base) exit(0);
s->top = s->base + s->stackSize; // 設置棧頂
s->stackSize = s->stackSize + STACKINCREMENT; // 設置棧的最大容量
}
*(s->top) = e; // 元素e入棧，賦值到棧頂空間
s->top++; // 棧頂指針增加1
return OK;
}
二帚桩、出棧操作
/**
* 出棧操作（刪除棧S的棧頂元素亿驾，用e返回其值）
*/
Status Pop(sqStack * s, ElemType *e){
if (s->top == s->base) // 棧空
return ERROR;
s->top--; // 棧頂指針減1
*e = *(s->top); // 將要刪除的棧頂元素賦值給e
// *e = *--(s->top);
return OK;
}
三账嚎、清空棧
清空一個棧莫瞬，就是將棧中的元素全部作廢儡蔓，但是棧本身物理空間并不發(fā)生變化。這里的方式定義的棧疼邀，只需要將s->top = s->base;即可實現(xiàn)棧的清空喂江。
/**
* 清空一個棧(將棧中的元素全部作廢，棧本身的物理空間并不發(fā)生變化)
*/
Status ClearStack(sqStack *s){
s->top = s->base;
return OK;
}
四旁振、銷毀棧
銷毀一個棧和釋放一個棧不同获询，銷毀一個棧是要釋放該棧所占據(jù)的物理內存空間。
/**
* 銷毀棧(釋放該棧鎖占據(jù)的物理內存空間)
*/
Status DestoryStack(sqStack * s){
int i,len;
len = s->stackSize; // 獲取棧容量
for (i = 0; i < len; i++) {
free(s->base);
s->base++;
}
s->base = s->top = NULL;
s->stackSize = 0;
return OK;
}
五拐袜、計算棧的當前容量
計算棧的當前容量也就是計算棧中元素的個數(shù)吉嚣，在這里只需要返回即可
/**
* 計算棧的當前容量
*/
int StackLen(sqStack s){
return (s.top - s.base);
}
