数据结构——栈

栈

       栈的理解

        咱们先不管栈的数据结构什么，先了解栈是什么，栈就像一个桶一样，你先放进去的东西，被后放进的的东西压着，那么就需要把后放进行的东西拿出才能拿出来先放进去的东西，如图1，就像图1中样子：

 图1

        图1中如果你需要拿书本1那么就要先将，书本432按照这个顺序拿出来，才能拿到书本1，如果拿书本4那么就可以直接拿到，这就是栈的一个性质，所以栈的专业名称就叫：FILO(first in last out),翻译后就是先进后出；

      栈的数据结构：

        物理结构：

        和队列一样，有一个存储数据的数据域，这里用的是数组，然后是一个栈顶指针，栈顶指针指向栈顶元素，还有栈的大小;

        用结构体封装后，代码实现如下：

        

typedef struct stack {//栈的结构定义int top, size;//分别是栈顶指针，栈的大小void *data;//数据域
} stack;

        逻辑结构：

        先进后出，后进先出，需要维护的性质，不能破坏这个性质；

      结构操作

        来看栈是如何对里面的数据如何出栈和入栈的；

        入栈：

        如图现在是栈的情况，里面有元素1234：

         

        现在对元素5进行入栈，top指针先往上偏移：

        

        然后元素5入栈：

         

         最后完成入栈；

         出栈：

         直接对于上面的完成入栈元素5的情况开始出栈，出栈元素4： 

         直接将指针，偏移两步，到指针指向元素3，然后元素5，元素4按照顺序出栈：

        最终元素4，5都出栈：

         

        看完了图片的展示，下面开始代码实现： 

        

#include <stdio.h>
#include <stdlib.h>
#include <time.h>typedef struct stack {//栈的结构定义int top, size;//分别是栈顶指针，栈的大小int *data;//数据域
} stack;stack *init(int n) {//向计算机借空间，然栈里面有空间可以存值stack *s = (stack *)malloc(sizeof(stack));s->data = (int *)malloc(sizeof(int) * n);s->top = -1;s->size = n;return s;
}int empty(stack *s) {//判短栈是否为空return s->top == -1;
}int top(stack *s) {//获取栈顶元素if (empty(s)) return -1;return s->data[s->top];
}int push(stack *s, int val) {//入栈元素if (s->top == s->size - 1) return 0;s->data[++(s->top)] = val;s->size++;return 1;
}int pop(stack *s) {//出栈元素if (empty(s)) return 0;s->top--;s->size--;return 1;
}void clear(stack *s) {//借了计算机的还回去if (!s) return ;free(s->data);free(s);return ;
}void output(stack *s) {//打印栈里的元素printf("stack(%d) = [", s->size);for (int i = s->top; i >= 0; i--) {i != s->top && printf(" ");printf("%d", s->data[i]);}printf("]\n");return ;
}int main() {//测试srand(time(0));stack *s = init(20);int op, val;for (int i = 0; i < 20; i++) {op = rand() % 4;val = rand() % 100;switch (op) {case 0:case 1:case 2: {printf("%d push in stack is %d\n", val, push(s, val));   } break;case 3: {int top_number = top(s);printf("%d pop in stack is %d\n", top_number, pop(s));} break;}output(s);}clear(s);return 0;
}