数据结构（栈和队列）

栈

　　定义：栈是一个先进后出的线性表，要求只在表尾进行删除和插入操作

　　注：对于栈来说，表尾成为栈的栈顶（top）,相应的表头称为栈低（bottom）。

　　因为栈的本质是线性表，所以栈也分为顺序存储结构和链式存储结构；（一般用顺序存储实现）

栈的顺序存储：

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define initSize 10
#define sup 2
typedef int ElemType;

typedef struct{
    int stackSize;//栈当前可用最大容量
    ElemType *base;//栈低
    ElemType *top;//栈顶
}sqStack;

void initStack(sqStack *);
void Push(sqStack *,ElemType);
void pop(sqStack *,ElemType *);

void pop(sqStack *s,ElemType *val){
    if(s->base==s->top){
        return ;
    }
    *val=*(--s->top);
}

void Push(sqStack *s,ElemType val){
    if(s->top-s->base>=s->stackSize){//判断栈是否存满，并追加空间
        s->base=(ElemType *)realloc(s->base,(s->stackSize+sup) * sizeof(ElemType));
        if(!s->base)
            exit(0);
        s->top=s->base+s->stackSize;
        s->stackSize+=sup;
    }
    *(s->top)=val;//栈顶压栈数据
    s->top++;
}

void initStack(sqStack *s){
    s->base=(ElemType *)malloc(initSize * sizeof(ElemType));
    if(!s->base)
        exit(0);
    s->top=s->base;
    s->stackSize=initSize;
}

void main(){
    int val;
    sqStack s;
    initStack(&s);
    printf("请输入压栈（-1退出）：");
    scanf("%d",&val);
    while(val != -1){
        Push(&s,val);
        printf("请输入压栈（-1退出）：");
        scanf("%d",&val);
    }
    printf("开始弹栈：\n");
    while(s.top!=s.base){
        pop(&s,&val);
        printf("%d  ",val);
    }
}

后缀表达式

　　利用栈的方式：遍历中缀表达式；为数字压栈，为符号时弹栈；

　　方法：从左到右遍历中缀表达式，若为数字时直接输出；若为符号，则判断其与栈顶符号的优先级：是‘）’的话则栈中符号依次出栈，直到遇到‘（’【括号不会输出在后缀表达式中】；其他符号：如果该符号优先级小于等于栈顶优先级，则栈中符号依次弹栈输出，直到栈顶符号优先级小于带压栈符号优先级或者栈顶为‘（’；如果遍历结束，再将栈中符号依次出栈输出；

例如：5+2*(3*(3-1*2+1))　　=>　　523312*-1+**+

后缀表达式的计算：1、按次序读取后缀表达式的每个字符。2、读取到操作数时，把操作数压入栈中。3、读取到操作符时，对栈顶的2个操作数做相应运算，要注意操作数的前后顺序。结果压入栈中。4、读取完所有字符后，弹出栈。得到的值就是所求结果。

队列

定义：只允许在一端进行插入操作，另一端进行删除操作的线性表

　　与栈相反，队列是一种先进后出的线性表。

　　队列既可以用链表实现，也可以用顺序存储实现，（一般用链表实现）

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
typedef int ElemType;

typedef struct QNode{
    ElemType data;
    struct QNode *next;
}QNode,* QueuePrt;

typedef struct{
    QueuePrt head;//队头
    QueuePrt rear;//队尾
}LinkQueue;

void init(LinkQueue *);
void Insedt(LinkQueue *,ElemType);
void pop(LinkQueue *,ElemType *);

void init(LinkQueue *q){
    q->head=q->rear=(QueuePrt)malloc(sizeof(QNode));
    if(!q->head)
        exit(0);
    q->head->next=NULL;
}

void Insedt(LinkQueue *q,ElemType e){
    QueuePrt p=(QueuePrt)malloc(sizeof(QNode));
    if(p==NULL)
        exit(0);
    p->data=e;
    p->next=NULL;
    q->rear->next=p;//用队尾链接
    q->rear=p;//更新队尾
}

void pop(LinkQueue *q,ElemType *e){
    QueuePrt p=q->head->next;//得到队列中头结点指向的结点（）队列中第一个值
    q->head->next=p->next;//更新头结点指向的结点（在队列中删除原先第一个有值结点）
    if(q->rear==p){//判断删除结点是否为队列中最后一个结点
        q->rear=q->head;//队列将要成为空队列，将指向尾结点的指针指向头结点
    }
    *e=p->data;
    free(p);
}

void main(){
    ElemType val;
    LinkQueue s;
    init(&s);
    printf("%d\n",s.head->data);
    printf("请输入进入队列的数（-1退出）：");
    scanf("%d",&val);
    while(val != -1){
        Insedt(&s,val);
        printf("请输入进入队列的数（-1退出）：");
        scanf("%d",&val);
    }
    printf("开始出队列：\n");
    while(s.head!=s.rear){
        pop(&s,&val);
        printf("%d  ",val);
    }
    printf("\n");
}