线性结构的应用

具体的线性结构应用分为下面两种：

栈

一种可以实现先进后出的存储结构，类似弹夹

栈的分类：

• 静态栈（也就是顺序栈）
• 动态栈（也就是链栈）

栈的定义

typedef struct Node
{
    int data;
    struct Node *pNext;
}NODE,*PNODE;

typedef struct Stack
{
    PNODE pTop;   //弹夹顶部
    PNODE pBottom; //弹夹底部的一个元素(头节点)
}STACK,*PSTACK;  //PSTACK 等价于 struct STACK *

栈的应用

• 函数调用（复合函数？递归）
• 中断
• 表达式求值
• 内存分配
• 缓冲处理
• 迷宫……

队列

是一种可以实现先进先出的存储结构

队列分类

• 静态队列（顺序队）–数组实现 通常都是循环队列

用一般的数组实现队列会浪费空间，但是如果思想不变，变个形式，变成一个圈，也就是循环队列，就可以解决这个问题 头部frout 和尾部rear在不同场合有不同的含义 frout=rear 空 多增加一个元素标识参数或者少用一个元素来判断满与不满，若frout与rear相邻，则满

• 链式队列（链队）–链表实现

//循环队列的结构体
//头部frout 和尾部rear在不同场合有不同的含义
typedef struct Queue{
    int *pBase; //指向头的指针
    int frout; //头
    int rear  //尾部后一个元素
}QUEUE,*PQUEUE;

队列的应用

• 所有和时间有关的操作都与队列有关（操作系统？线程，阻塞…队列）

最终的代码存放在Github仓库 Stack和Queue部分