数据结构 1-3 栈

一、原理

栈是只允许在一端进行插入或删除操作的线性表

所谓的栈，其实就是一个特殊的线性表（顺序表、链表），但是它在操作上有一些特殊的要求和限制：

• 栈的元素必须“后进先出”
• 栈的操作只能在这个线性表的表尾进行。
• 对于栈来说，这个表尾称为栈的栈顶（top），相应的表头称为栈底（bottom）。

先进后出FILO

栈的插入和删除操作：

栈的插入操作（Push），叫做进栈，也称为压栈，入栈。

栈的删除操作（Pop），叫做出栈，也称为弹栈。

二、顺序存储实现栈

2.1 定义栈

#define MaxSize 50
typedef int ElemType;
typedef struct {ElemType data[MaxSize];int top;
}Stack;

2.2 初始化栈

void init_stack(Stack &S) {S.top = -1;//初始化栈，让栈为空}

2.3 判断栈为空

bool stack_empty(Stack S) {if (-1 == S.top) {return true;}else {return false;}
}

2.4入栈

bool push(Stack &S, ElemType x) {//判断栈是否满？if (S.top == MaxSize -1) {return false;}S.data[++S.top] = x; //等于S.top = S.top +1;S.data[S.top]=x;return true;}

注意：入栈需要判断栈是否为满，为满则不能再插入数据

2.5 出栈

出栈则需要先判断栈是否为空，为空的栈不需要出栈

bool pop(Stack S, ElemType m) {if (stack_empty(S)) {return  false;}m = S.data[S.top--];等于S.data[S.top]=x;S.top = S.top -1;return true;
}

2.6得到栈顶

bool get_top(Stack S, ElemType &m) {if (stack_empty(S)) {return  false;}m = S.data[S.top];return  true;}

2.7 运行主函数

int main() {Stack S;init_stack(S);//判断栈是否为空bool flag;flag = stack_empty(S);if (flag) {printf(("stack is empty"));}push(S,3); //入栈push(S,5); //入栈push(S,6); //入栈push(S,7);ElemType m;flag = get_top(S, m);if (flag) {printf("get top %d\n",m);}flag = pop(S, m);//弹出栈元素if (flag) {printf("pop ele %d\n",m);}return 0;
}