嵌入式学习 day23：栈

一、什么是栈栈是一种先进后出的结构。最后放进去的东西最先拿出来最先放进去的东西最后才能拿出来。text入栈 → ← 出栈 ↓ ┌─────────┐ │ 元素5 │ ← 栈顶 ├─────────┤ │ 元素4 │ ├─────────┤ │ 元素3 │ ├─────────┤ │ 元素2 │ ├─────────┤ │ 元素1 │ ← 栈底 └─────────┘关键术语栈顶允许插入和删除的一端栈底不允许操作的一端入栈把元素放到栈顶出栈从栈顶取出元素二、栈的分类根据栈针指向位置的不同栈分为几种空栈栈针指向下一个元素要放的位置先存数据再移动栈针满栈栈针指向当前栈顶元素的位置先移动栈针再存数据增栈栈针向高地址移动减栈栈针向低地址移动我当前主要学的是空增栈。三、顺序栈3.1 结构体定义c#define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; // 存数据的数组 int top; // 栈针 } SeqStack;top存的是下一个元素要放的位置的下标。top 0表示栈是空的。3.2 初始化cvoid InitStack(SeqStack *s) { s-top 0; }3.3 判断空和满cint IsEmpty(SeqStack *s) { return s-top 0; } int IsFull(SeqStack *s) { return s-top MAX_SIZE; }3.4 入栈cint Push(SeqStack *s, int data) { if (IsFull(s)) { return -1; } s-data[s-top] data; // 先放数据 s-top; // 再移动栈针 return 0; }3.5 出栈cint Pop(SeqStack *s, int *data) { if (IsEmpty(s)) { return -1; } s-top--; // 先移动栈针 *data s-data[s-top]; // 再取数据 return 0; }注意入栈和出栈的顺序刚好相反。四、链式栈4.1 结构体定义ctypedef struct StackNode { int data; struct StackNode *next; } StackNode; typedef struct { StackNode *top; // 栈顶指针 int size; // 元素个数 } LinkStack;4.2 初始化cvoid InitLinkStack(LinkStack *s) { s-top NULL; s-size 0; }4.3 入栈链式栈的入栈就是链表的头插cint Push(LinkStack *s, int data) { StackNode *newNode (StackNode *)malloc(sizeof(StackNode)); if (newNode NULL) { return -1; } newNode-data data; newNode-next s-top; // 新节点指向原来的栈顶 s-top newNode; // 栈顶换成新节点 s-size; return 0; }4.4 出栈cint Pop(LinkStack *s, int *data) { if (s-top NULL) { return -1; } StackNode *tmp s-top; *data tmp-data; s-top tmp-next; // 栈顶指向下一个节点 free(tmp); s-size--; return 0; }链式栈其实就是只在头部操作的单向链表入栈等于头插出栈等于删头。五、今日总结今天学了栈核心要点如下栈的特点先进后出只能在一端操作顺序栈用数组实现top指向下一个元素要放的位置链式栈用链表实现入栈头插出栈删头入栈出栈顺序相反入栈先存后移出栈先移后取今日感悟栈和表不同只能在指定的位置插入和删除。但是栈和表仍存在着共同点当表的基础打好了栈的代码编写就相对轻松很多也更容易理解。