目录

一、栈的基本概念

1.定义

2.几个重要术语

二、顺序栈的表示

三 、顺序栈的基本操作

1.栈的初始化操作

2.栈的判空操作

3.进栈操作

4.出栈操作

5.取栈顶元素

一、栈的基本概念

1.定义

栈是一种只允许在一端进行插入和删除的特殊线性表。

2.几个重要术语

①栈顶：表中允许进行插入、删除操作的一端叫做栈顶
②栈底：固定的，不允许进行插入和删除的另一端
③空栈：不任何元素
④栈的操作特性：先进后出(FILO)
⑤栈的数学性质：n个不同元素进栈，出栈元素不同排列的个数为1/(n+1)*C2n(n)--卡特兰数(Catalan) 

二、顺序栈的表示

typedef int ElemType;#define MaxSize 50     //定义栈中元素的最大个数typedef struct {ElemType  data[MaxSize];  //存放栈中的元素int top;    //栈顶指针}SqStack;

三 、顺序栈的基本操作

栈空条件：pastack.top == -1;
栈满条件：pastack.top == MaxSize-1;
栈的长度：pastack.top+1;

1.栈的初始化操作

void InitStack(SqStack* pastack){pastack->top = -1; //初始化栈顶指针}

2.栈的判空操作

bool EmptyStack(SqStack pastack){if (pastack.top = -1)  //栈空{return true;}elsereturn false;     //栈不空}

3.进栈操作

bool Push(SqStack* pastack, ElemType e){if (pastack->top == MaxSize - 1)   //栈满，报错{return false;}pastack->top++;      //栈顶指针加1pastack->data[pastack->top] = e;   //元素进栈return true;}

4.出栈操作

bool Pop(SqStack* pastack, ElemType* e){if (pastack->top == -1)     //栈空，报错{return false;}*e = pastack->data[pastack->top]; //将栈顶元素赋个epastack->top--;     //栈顶指针减一return true;}

5.取栈顶元素

bool GetTopElem(SqStack pastack, ElemType* e){if (pastack.top == -1)     //栈空，报错{return false;}*e = pastack.data[pastack.top];   //将栈顶元素赋给ereturn true;}

A soul without imagination is like an observatory without a telescope.