栈和队列

栈

后进先出（LIFO），last_in_first_out
顺序栈：
- top == -1表示空
- 双端栈：栈底不变，栈顶相互正对（底在两边，顶在中间）
链栈
栈和递归
- 递归进层(i->i+1层)系统需要做三件事:
  1. 保留本层参数与返回地址
  2. 为被调用函数的局部变量分配存储区,给下层参数赋值
  3. 将程序转移到被调函数的人口。
- 而从被调用函数返回调用函数之前，递归退层(i<-i+1层)系统也应完成三件工作:
  1. 保存被调丽数的计算结果
  2. 释放被调函数的数据区,恢复上层参数。
  3. 依照被调函数保存的返回地址,将控制转移回调用函数。
- 当递归函数调用时,应按照“后调用先返回”的原则处理调用过程,因此上述函数之间的信息传递和控制转移必须通过栈来实现。系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时,就为它在栈顶分配-一个存储区,而每当从一个函数退出时,就释放它的存储区。显然,当前正在运行的函数的数据区必在栈顶。
- 一个递归函数的运行过程中,调用函数和被调用函数是同一个函数,因此,与每次调用时相关的一个重要的概念就是递归函数运行的“层次”。假设调用该递归函数的主函数为第0层,则从主函数调用递归函数为进入第1层;从第i层递归调用本函数为进入“下一层”,即第i+1层。反之,退出第i层递归应返回至“上一层”,即第i-1层。为了保证递归函数正确执行,系统需设立一个递归工作栈作为整个递归函数运行期间使用的数据存储区。每层递归所需信息构成一个工作记录,其中包括所有的实在参数、所有的局部变量以及上-一层的返回地址。每进入一层递归,就产生一个新的工作记录压人栈顶。每退出一层递归,就从栈顶弹出一个工作记录。因此当前执行层的工作记录必为递归工作栈栈顶的工作记录,称这个记录为活动记录,并称指示活动记录的栈顶指针为当前环境指针。由于递归工作栈是由系统来管理的，无须用户操心,所以用递归法编制程序非常方便。
- 递归转换非递归
  - 单向递归：
    
    单向递归是指递归函数中虽然有一处以上的递归调用语句,但各次递归调用语句的参数只和主调用函数有关,相互之间参数无关,并且这些递归调用语句处于算法的最后。
  - 尾递归：
    
    尾递归是指递归调用语句只有一个,而且是处于算法的最后,尾递归是单向递归的特例。

队列

先进先出（FIFO），first_in_first_out
允许插入的一端：队尾
允许删除的一端：队头

链队列：

队头：front
队尾rear
入队关键代码：

NewNode->data= x ;
NewNode->next= NULL;
Q->rear->next= NewNode;
Q->rear= NewNode;

出队关键代码：

p=Q->front-> next;
Q->front->next=p->next;     / *队头元素p出队*/
if( Q->rear==p)             / *如果队中只有一个元素p,则p出队后成为空队*/
Q->rear=Q->front;
* x=p->data;
free(p);

循环队列：

初始化：front=rear=0
入队

rear = (rear+1) mod MAXSIZE;

出队

front = (front+1) mod MAXSIZE;

队满

(rear+1) mod MAXSIZE == front

队空

rear == front