数据结构 栈和队列

1. 栈 Stack

定义：
限定仅在表尾进行插入和删除操作的线性表。即后进先出的线性表（Last In First Out）表尾即栈顶top，表头即栈低bottom。

存储方式：
顺序栈、链栈；

1. 顺序栈：

一组地址连续的存储单元，依次存放自栈低到栈顶的数据元素。

结构：两个指针top，base，一个int size描述栈的大小；
主要操作：出栈和入栈（压栈）
空栈：top = base；
非空栈：base指向栈低，top指向栈顶元素的下一个位置上。

有一个元素的栈

C语言的结构体

#define MAXSIZE 100  //顺序栈存储空间的初始分配量
typedef struct{

    SElemtype *base;
    SElemtype *top;
    int  stacksize;

}SqlStack;

2. 链栈

采用链式存储结构实现栈，通常用单链表表示。

结构：stackNode（elemtype data，stackNode next）；
主要操作： 对栈顶的插入和删除

链栈

typedef struct StackNode{

    SElemtype data;
    struct StackNode  *next;

}StackNode,*LinkStack;

2. 栈的应用

1. 数制转换
   十进制数据N和其他进制的转换是计算机实现计算的基本问题，算法基于的原理：

N=(N div d)*d+N mod d
div：整除
mode：取余数

2. 括号匹配的检验
3. 表达式求值

3. 栈与递归

1.递归：

若在一个函数、过程或数据结构定义的内部又直接或间接出现定义本身的应用，则称为递归。

通常在3中情况下使用递归：

1. 定义是递归的（Fact阶乘函数、Fib二阶的Fibonacci数列）
2. 数据结构是递归的（依次输出链表中各个节点的递归）
3. 问题的解法是递归（Hanoi问题）

递归过程与递归工作栈 暂时没时间写，有时间补上
递归算法的效率分析 暂时没时间写，有时间不上

将递归转换为非递归方法

• 递归的优点：结构清晰，程序易读；
• 递归的缺点：需要系统提供隐式栈这种结构来实现，占用内存空间较多，运行效率低。

递归的目的：提高算法的时间、空间性能，所以使用递归算法来分析问题，用非递归算法来解决问题；

将递归换为非递归的方法（两种）

循环方法
1.单项递归
2.尾递归
利用栈消除递归

4.队列 Queue

定义：是一种先进先出（First In First Out）FIFO的线性表。
存储表示：顺序表示和链式表示；

队列的出和入

顺序存储结构
一组地址连续的存储单元依次存放队列头到队列尾的元素；
结构：两个指针队头front和队尾rear；
这种存储会出现假溢出问题；

队列的存储

循环队列
为了解决假溢出现象，将顺序队列臆造为一个环状的空间，称之为循环队列。

循环队列

队头、尾指针的环状增1的操作用“模”运算来实现。

区别队满和队空的方法：

1. 少用一个空间，队列有m个空间，当有m-1个元素时，就判定队列已满。

• 队空：Q.font = Q.rear
• 队满：(Q.rear+1) % MAXQSIZE = Q.font

2. 设置标志位

链队
链表表示的队列即链队；

队列的应用
打印二项式系数表