栈和队列
栈和队列是两种重要的线性结构，他们广泛应用于软件系统当中。
栈
栈（stack）就是限定只允许在表尾进行插入或者删除，也称为入栈和出栈，表位称为栈顶，表头称为栈底，不含元素的栈称为空栈。栈又被称为后进先出的线性表。
栈的表示和实现
顺序栈，基站的存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，栈中设置两个指针base，top，分别指向栈底和栈顶，通常top=0表示空栈，栈中还包括两个常量，STACK_INIT_SIZE（储存空间初始分配），STACKINCREMENT（储存空间分配增量），这是因为在初始化栈的时候并不知道栈要开多大，所以先分配一定的内存，当栈的空间不够时在进行空间分配。下述类型说明栈的定义：
typedef int ElementType; // 定义数据类型,可根据需要进行其他类型定义
#define STACK_INIT_SIZE 100 // 储存空间初始分配
#define STACKINCREMENT 10 //储存空间分配增量
//顺序栈定义
typedef struct SqStack{
ElementType *base;
ElementType *top;
int stacksize; //栈目前最大容量
}SqStack;
栈的初始化操作，base指针始终指向栈底，若base指针指向NULL则表示栈结构不存在，top指针初始指向栈底，若top=base说明空栈，每当插入新元素栈顶指针+1，删除元素栈顶指针-1。因此在非空栈中栈顶指针始终在栈顶元素的下一个位置，下述说明栈的初始化操作：
//构造一个空栈
SqStack InitStack(SqStack S){
S.base = (ElementType *)malloc(STACK_INIT_SIZE * sizeof(ElementType));
if(!S.base){ //储存分配失败
printf("储存分配失败");
return S;
}
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return S;
}
对栈底元素分配内存空间，栈顶指针指向栈底指针，初始化栈的初始大小，返回栈。
插入元素
新建一个栈的结构体指针用来对栈进行操作（栈本身定义时并不是指针，只能用指针进行访问操作，如过还有疑问请参考数据结构杂谈指针部分），栈指针指向需要插入新元素的栈，判断栈是否以满，满了就重新分配一块增加后的储存空间，设置栈顶指针，重写栈当前容量，要插入的元素赋值给栈顶指针所指向的内存空间，栈顶指针自增。
//插入元素e为新的栈顶元素
SqStack Push(SqStack P,ElementType e){
SqStack *S = &P;
if(S->top - S->base >= S->stacksize){ //栈满，追加空间
S->base = (ElementType *)realloc(S->base,(S->stacksize + STACKINCREMENT) * sizeof(ElementType));
S->top = S->base + S->stacksize;
S->stacksize += STACKINCREMENT;
}
*S->top++ = e;
return P;
}
S->base = (ElementType *)realloc(S->base,(S->stacksize + STACKINCREMENT) * sizeof(ElementType)); 重新分配内存。
*S->top++ = e;插入元素与栈顶指针自增合并操作。
删除元素
判断栈是否为空，若是则无法删除元素，若不是栈顶指针自减即可。下述说明删除元素操作：
//删除栈顶元素
SqStack pop(SqStack S){
if(S.base == S.top){
printf("只有一个元素");
}
S.top--;
return S;
}
清空栈
只需top栈顶指针指向base栈底指针,重写栈的大小。
SqStack ClearStack(SqStack S){
S.top = S.base;
S.stacksize = 0;
return S;
}
栈的应用举例
设置一个字符站，从终端接受一行字符，其中字符‘#’表示退格，‘@’表示退行，之后输出字符串，下述表明实际操作：
void LineEdit(){
//利用字符栈S，从终端接收一行并传送并调用过程的数据区。
SqStack S;
char ch;
InitStack(S); //构造空栈S
ch = getchar();
while(ch != EOF){
while (ch != EOF && ch != '\n') {
switch (ch) {
case '#':
S = pop(S);
break;
case '@':
ClearStack(S);
break;
default:
Push(S, ch);
break;
}
ch = getchar();
}
ClearStack(S); //重置S为空栈
if (ch != EOF) ch = getchar();
}
}
栈与递归的的实现
栈的一个重要应用就是在设计程序是实现队规，一个直接调用自己，或者通过一系列语句间接的调用自己的函数，称为递归函数。 举个例子：求任意阶数的Fibonacc数列，下述说明Fibonacc函数：
#include<stdio.h>
int Fibonacc(int x){
if(x == 0) return 0;
if(x == 1) return 1;
return Fibonacc(x - 1) + Fibonacc(x - 2);
}
int main(){
int x,Fib;
scanf("%d",&x);
Fib = Fibonacc(x);
printf("%d",Fib);
return 0;
}
栈完整代码请见 ：stack
队列
队列（queue）就是限定只允许在表尾进行插入在表头删除元素，也称为入队和出队，允许删除的一端称为队头，允许插入的一段称为队尾，队列又被称为先进先出的线性表。队列在炒作系统中也经常出现，通常操作系统中允许多个线程排队，根据先后次序进行处理。
和线性表类似，队列的实现也有两种方式，一种是链队列，一种是顺序队列，也称为循环队列，链队列和链表类似下面会分别说明。
链队列的表示和实现
根据队列的定义，一个链队列需要两个指针分别指向队头的头结点和队尾元素。下面给出链队列的结构：
typedef int ElementType; // 定义数据类型,可根据需要进行其他类型定义
typedef struct QNode{
ElementType data;
struct QNode *next;
}QNode,*QueuePtr;
//--------单链表队列————队列的链式存储结构-------
typedef struct {
QueuePtr front; //队头指针 不存放数据next指向第一个数据
QueuePtr rear; //队尾指针 存放最后一个数据next指向NULL
}LinkQueue;
这里做了一些特殊的处理，首先定义了每个数据类型的基本结构，每个数据元素包括一个数据域和一个指针域，同链表，又定义了一个数据结构，其中只包含两个指针队头和队尾指针，其中队头指针不存放数据，类似链表中的头结点。
构造一个空队列
初始化队列，为队头指针和队尾指针分配内存地址，队头指针的nxet指针指向NULL，表示没有数据即可，下面说明构造空队列：
//构造一个空队列
LinkQueue InitQueue(LinkQueue Q){
Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
if(!Q.front){
printf("储存分配失败");
}
Q.front->next = NULL;
return Q;
}
插入元素
新建一个队列元素指针，并为其分配内存空间 ，赋值给新的元素，新元素的结尾指针设置为NULL,原队列的队尾指针的next指向新元素，把新元素赋值给队尾指针，也可以说队尾指针指向新元素。下面说明插入元素：
//插入元素e为Q的新的队尾元素
LinkQueue EnQueue(LinkQueue Q,ElementType e){
QueuePtr p = (QueuePtr)malloc(sizeof(QNode)); //创建新添加元素
if(!p){
printf("储存分配失败");
}
p->data = e; //把e赋值给新的元素
p->next = NULL; //新元素的结尾指针为NULL
Q.rear->next = p; //把队尾指针的next指向p
Q.rear = p; //把P赋值给队尾指针
printf("成功插入元素\n");
return Q;
}
删除元素
可以使队头指针的next指向头指针的next的next，但被删除的元素空间没有被释放，造成了空间浪费，所以通常会新建一个节点指向队头指针的next所指向的，之后对队头指针点的next指向头指针的next的next，最后释放新节点就好，新节点起到了哨兵的作用。下面说明删除元素的实现：
//消除队列头元素
LinkQueue DeQueue(LinkQueue Q){
if(Q.front == Q.rear){
printf("队列为空");
}
QueuePtr p = (QueuePtr)malloc(sizeof(QNode)); //创建队列指针
p = Q.front->next;//P指针指向队头指针所指向的 p指向头指针所指的下一个节点
Q.front->next = p->next; //队头指针指向P的next 头指针指向下一节点的下一个节点
if(Q.rear == p)Q.rear = Q.front; //若元素全部出队后 队尾指针丢失 重新赋值指向有节点
free(p);
printf("成功消除队列头元素\n");
return Q;
}
销毁队列
类似于删除节点，区别在于不需要设置哨兵，每到一个节点释放内存空间，首先使队尾指针指向队头指针指向的下一个元素，释放队头指针，使队头指针指向队尾指针，重复上述操作直到队头指针指向NULL，下面说明销毁队列的操作：
//销毁队列
LinkQueue DestroyQueue(LinkQueue Q){
while(Q.front){ //只要头节点指向节点就进行删除
Q.rear = Q.front->next; //尾指针指向头指针所指向的
free(Q.front); //释放头结点
Q.front = Q.rear; //头结点指向尾指针所指向的 就是指向被删除的节点之后的节点
}
printf("成功销毁队列\n");
return Q;
}
循环队列
循环队列类似于顺序栈，使用一组地址连续的存储单元依次存放队头到队尾的元素，仍需设置两个指针，分别指向队头和队尾，类似栈顶和栈底指针。其中因为队列的先进先出的结构，只要元素数不超过队列长度，可以实现在一块内存地址上循环使用循环队列。
循环队列的结构以及初始化
循环链表的结构类似于链队列，区别在于不需要单独设置一个链表元素结构，以及增加一个动态空间的指针。初始化操作，为初始化的动态分配空间指针分配内存空间即可，具体操作如下：
//---------循环链表------------
typedef struct {
ElementType *base; //初始化的动态分配储存空间
int front; //队头指针 不存放数据next指向第一个数据
int rear; //队尾指针 存放最后一个数据next指向NULL
}SqQueue;
//-------------- 循环队列基本操作的算法描述-----------------
//构造一个新队列
SqQueue InitQueue2(SqQueue Q){
Q.base = (ElementType *)malloc(MAXQSIZE * sizeof(ElementType));
if(!Q.base){
printf("储存分配失败");
Q.front = Q.rear = 0;
}
printf("构建循环队列成功");
return Q;
}
插入元素
首先判断队列情况是否队列已满，队尾指针指向新的元素，队头指针自增。下面说明插入元素：
//插入元素e为Q的新队尾元素
SqQueue EnQueue2(SqQueue Q,ElementType e){
if((Q.front + 1) % MAXQSIZE == Q.front){
printf("队列已满");
}
Q.rear = e;
Q.rear = (Q.rear + 1) % MAXQSIZE;
printf("成功插入元素\n");
return Q;
}
Q.rear = (Q.rear + 1) % MAXQSIZE;循环实现的关键，每次对自增后的指针进行取余，保证能够循环。
删除元素
因为是在连续的内存中操作，所以不存在释放内存空间，直接队头指针自增就好。
//删除队头元素
SqQueue DeQueue2(SqQueue Q){
if(Q.front == Q.rear){
printf("删除失败");
}
Q.front = (Q.front + 1) % MAXQSIZE;
printf("成功消除队列头元素\n");
return Q;
}
Q.front = (Q.front + 1) % MAXQSIZE;循环实现的关键，每次对自增后的指针进行取余，保证能够循环。
队列完整代码见： Queue
