数据结构 1-3 栈

一、原理

栈是只答应在一端进行插入或删除操纵的线性表
所谓的栈，实在就是一个特别的线性表（次序表、链表），但是它在操纵上有一些特别的要求和限制：

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

先进后出FILO

栈的插入和删除操纵：
栈的插入操纵（Push），叫做进栈，也称为压栈，入栈。
栈的删除操纵（Pop），叫做出栈，也称为弹栈。
二、次序存储实现栈

2.1 界说栈

1. #define MaxSize 50
2. typedef int ElemType;
3. typedef struct {
4.     ElemType data[MaxSize];
5.     int top;
6. }Stack;

复制代码

2.2 初始化栈

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

复制代码

2.3 判断栈为空

1. bool stack_empty(Stack S) {
2.     if (-1 == S.top) {
3.         return true;
4.     }
5.     else {
6.         return false;
7.     }
8. }

复制代码

2.4入栈

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

复制代码

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

  2.5 出栈

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

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

复制代码

2.6得到栈顶

1. bool get_top(Stack S, ElemType &m) {
2.     if (stack_empty(S)) {
3.         return  false;
4.     }
5.     m = S.data[S.top];
6.     return  true;
8. }

复制代码

2.7 运行主函数

1. int main() {
2.     Stack S;
3.     init_stack(S);
4.     //判断栈是否为空
5.     bool flag;
6.     flag = stack_empty(S);
7.     if (flag) {
8.         printf(("stack is empty"));
9.     }
10.     push(S,3); //入栈
11.     push(S,5); //入栈
12.     push(S,6); //入栈
13.     push(S,7);
15.     ElemType m;
16.     flag = get_top(S, m);
17.     if (flag) {
18.         printf("get top %d\n",m);
19.     }
21.     flag = pop(S, m);//弹出栈元素
22.     if (flag) {
23.         printf("pop ele %d\n",m);
24.     }
26.     return 0;
27. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。