栈的定义

栈是仅限有表尾进行插入和删除操作的线性表

允许插入和删除操作的一端称为栈顶，别一端称为栈底。不包含任何数据元素的栈称为空栈。栈又称为先进后出（Last In First Out）的线性表，简称为LIFO结构。

栈的插入操作叫做进栈，也称压栈、入栈。

栈的删除操作叫做出栈，也称弹栈

栈的抽象数据类型

 

栈的顺序存储结构

栈的插入和删除操作和时间复杂度均是O(1)

栈的不同状态下的示意图：

栈的实现源码如下：

#include "stdio.h"    #include "stdlib.h"   #include "io.h"  #include "math.h"  #include "time.h"#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define MAXSIZE 20 /* 存储空间初始分配量 */typedef int Status; typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int *//* 顺序栈结构 */typedef struct{        SElemType data[MAXSIZE];        int top; /* 用于栈顶指针 */}SqStack;Status visit(SElemType c){        printf("%d ",c);        return OK;}/*  构造一个空栈S */Status InitStack(SqStack *S){         /* S.data=(SElemType *)malloc(MAXSIZE*sizeof(SElemType)); */        S->top=-1;        return OK;}/* 把S置为空栈 */Status ClearStack(SqStack *S){         S->top=-1;        return OK;}/* 若栈S为空栈，则返回TRUE，否则返回FALSE */Status StackEmpty(SqStack S){         if (S.top==-1)                return TRUE;        else                return FALSE;}/* 返回S的元素个数，即栈的长度 */int StackLength(SqStack S){         return S.top+1;}/* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */Status GetTop(SqStack S,SElemType *e){        if (S.top==-1)                return ERROR;        else                *e=S.data[S.top];        return OK;}/* 插入元素e为新的栈顶元素 */Status Push(SqStack *S,SElemType e){        if(S->top == MAXSIZE -1) /* 栈满 */        {                return ERROR;        }        S->top++;                /* 栈顶指针增加一 */        S->data[S->top]=e;  /* 将新插入元素赋值给栈顶空间 */        return OK;}/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */Status Pop(SqStack *S,SElemType *e){         if(S->top==-1)                return ERROR;        *e=S->data[S->top];    /* 将要删除的栈顶元素赋值给e */        S->top--;                /* 栈顶指针减一 */        return OK;}/* 从栈底到栈顶依次对栈中每个元素显示 */Status StackTraverse(SqStack S){        int i;        i=0;        while(i<=S.top)        {                visit(S.data[i++]);        }        printf("\n");        return OK;}int main(){        int j;        SqStack s;        int e;        if(InitStack(&s)==OK)                for(j=1;j<=10;j++)                        Push(&s,j);        printf("栈中元素依次为：");        StackTraverse(s);        Pop(&s,&e);        printf("弹出的栈顶元素 e=%d\n",e);        printf("栈空否：%d(1:空 0:否)\n",StackEmpty(s));        GetTop(s,&e);        printf("栈顶元素 e=%d 栈的长度为%d\n",e,StackLength(s));        ClearStack(&s);        printf("清空栈后，栈空否：%d(1:空 0:否)\n",StackEmpty(s));                return 0;}

 

两栈共享空间

基本思路是：数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，另一个栈为栈的末端，两个栈如果增加元素就是两个端点向中间延伸

实现源码：

#include "stdio.h"    #include "stdlib.h"   #include "io.h"  #include "math.h"  #include "time.h"#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define MAXSIZE 20 /* 存储空间初始分配量 */typedef int Status; typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int *//* 两栈共享空间结构 */typedef struct {        SElemType data[MAXSIZE];        int top1;    /* 栈1栈顶指针 */        int top2;    /* 栈2栈顶指针 */}SqDoubleStack;Status visit(SElemType c){        printf("%d ",c);        return OK;}/*  构造一个空栈S */Status InitStack(SqDoubleStack *S){         S->top1=-1;        S->top2=MAXSIZE;        return OK;}/* 把S置为空栈 */Status ClearStack(SqDoubleStack *S){         S->top1=-1;        S->top2=MAXSIZE;        return OK;}/* 若栈S为空栈，则返回TRUE，否则返回FALSE */Status StackEmpty(SqDoubleStack S){         if (S.top1==-1 && S.top2==MAXSIZE)                return TRUE;        else                return FALSE;}/* 返回S的元素个数，即栈的长度 */int StackLength(SqDoubleStack S){         return (S.top1+1)+(MAXSIZE-S.top2);}/* 插入元素e为新的栈顶元素 */Status Push(SqDoubleStack *S,SElemType e,int stackNumber){        if (S->top1+1==S->top2)    /* 栈已满，不能再push新元素了 */                return ERROR;            if (stackNumber==1)            /* 栈1有元素进栈 */                S->data[++S->top1]=e; /* 若是栈1则先top1+1后给数组元素赋值。 */        else if (stackNumber==2)    /* 栈2有元素进栈 */                S->data[--S->top2]=e; /* 若是栈2则先top2-1后给数组元素赋值。 */        return OK;}/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */Status Pop(SqDoubleStack *S,SElemType *e,int stackNumber){         if (stackNumber==1)         {                if (S->top1==-1)                         return ERROR; /* 说明栈1已经是空栈，溢出 */                *e=S->data[S->top1--]; /* 将栈1的栈顶元素出栈 */        }        else if (stackNumber==2)        {                 if (S->top2==MAXSIZE)                         return ERROR; /* 说明栈2已经是空栈，溢出 */                *e=S->data[S->top2++]; /* 将栈2的栈顶元素出栈 */        }        return OK;}Status StackTraverse(SqDoubleStack S){        int i;        i=0;        while(i<=S.top1)        {                visit(S.data[i++]);        }        i=S.top2;        while(i
      
       =MAXSIZE-2;j--)                        Push(&s,j,2);        }        printf("栈中元素依次为：");        StackTraverse(s);        printf("当前栈中元素有：%d \n",StackLength(s));        Pop(&s,&e,2);        printf("弹出的栈顶元素 e=%d\n",e);        printf("栈空否：%d(1:空 0:否)\n",StackEmpty(s));        for(j=6;j<=MAXSIZE-2;j++)                Push(&s,j,1);        printf("栈中元素依次为：");        StackTraverse(s);        printf("栈满否：%d(1:否 0:满)\n",Push(&s,100,1));                ClearStack(&s);        printf("清空栈后，栈空否：%d(1:空 0:否)\n",StackEmpty(s));                return 0;}
      

 

栈的链式存储结构

如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。

链栈的实现源码：

#include "stdio.h"    #include "stdlib.h"   #include "io.h"  #include "math.h"  #include "time.h"#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define MAXSIZE 20 /* 存储空间初始分配量 */typedef int Status; typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int *//* 链栈结构 */typedef struct StackNode{        SElemType data;        struct StackNode *next;}StackNode,*LinkStackPtr;typedef struct{        LinkStackPtr top;        int count;}LinkStack;Status visit(SElemType c){        printf("%d ",c);        return OK;}/*  构造一个空栈S */Status InitStack(LinkStack *S){         S->top = (LinkStackPtr)malloc(sizeof(StackNode));        if(!S->top)                return ERROR;        S->top=NULL;        S->count=0;        return OK;}/* 把S置为空栈 */Status ClearStack(LinkStack *S){         LinkStackPtr p,q;        p=S->top;        while(p)        {                  q=p;                p=p->next;                free(q);        }         S->count=0;        return OK;}/* 若栈S为空栈，则返回TRUE，否则返回FALSE */Status StackEmpty(LinkStack S){         if (S.count==0)                return TRUE;        else                return FALSE;}/* 返回S的元素个数，即栈的长度 */int StackLength(LinkStack S){         return S.count;}/* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */Status GetTop(LinkStack S,SElemType *e){        if (S.top==NULL)                return ERROR;        else                *e=S.top->data;        return OK;}/* 插入元素e为新的栈顶元素 */Status Push(LinkStack *S,SElemType e){        LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode));         s->data=e;         s->next=S->top;    /* 把当前的栈顶元素赋值给新结点的直接后继，见图中① */        S->top=s;         /* 将新的结点s赋值给栈顶指针，见图中② */        S->count++;        return OK;}/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */Status Pop(LinkStack *S,SElemType *e){         LinkStackPtr p;        if(StackEmpty(*S))                return ERROR;        *e=S->top->data;        p=S->top;                    /* 将栈顶结点赋值给p，见图中③ */        S->top=S->top->next;    /* 使得栈顶指针下移一位，指向后一结点，见图中④ */        free(p);                    /* 释放结点p */                S->count--;        return OK;}Status StackTraverse(LinkStack S){        LinkStackPtr p;        p=S.top;        while(p)        {                 visit(p->data);                 p=p->next;        }        printf("\n");        return OK;}int main(){        int j;        LinkStack s;        int e;        if(InitStack(&s)==OK)                for(j=1;j<=10;j++)                        Push(&s,j);        printf("栈中元素依次为：");        StackTraverse(s);        Pop(&s,&e);        printf("弹出的栈顶元素 e=%d\n",e);        printf("栈空否：%d(1:空 0:否)\n",StackEmpty(s));        GetTop(s,&e);        printf("栈顶元素 e=%d 栈的长度为%d\n",e,StackLength(s));        ClearStack(&s);        printf("清空栈后，栈空否：%d(1:空 0:否)\n",StackEmpty(s));        return 0;}

链栈的进栈push和出栈pop操作时间复杂度都为O(1)

栈的作用

1. 栈的应用--递归
2. 栈的应用--四则运算表达式求值

学过编译原理的应该都听说过逆波兰表示法，它也就是一种不需要括号的后缀表示法，所有的符号都是在运算数字的后面出现。

队列

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表

队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头

队列的抽象数据类型

循环队列

在队列中增加元素的时间复杂度为O(1)，而删除元素的时间复杂度为O(n)(因为入队列的时候只需要在队尾追加一个元素，而不需要移动任何元素。出队列的时候则需要将队列中所有元素都向前移动)

对于队列来说，为了避免数组插入和删除时需要移动数据，于是引入了循环队列，使得队头和队尾可以在数组中循环变化。解决了移动数据的时间损耗，使得本来删除是O(n)的时间复杂度变成了O(1)

队列的头尾相接的顺序存储结构称为循环队列

队列满的条件是（rear+1）%QueueSize==front（这里是队列满时，数组中还有一个空闲单元，如下图所示）

通用的计算队列长度公式为：(rear-front+QueueSize)%QueueSize

具体实现代码如下：

#include "stdio.h"    #include "stdlib.h"   #include "io.h"  #include "math.h"  #include "time.h"#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define MAXSIZE 20 /* 存储空间初始分配量 */typedef int Status; typedef int QElemType; /* QElemType类型根据实际情况而定，这里假设为int *//* 循环队列的顺序存储结构 */typedef struct{    QElemType data[MAXSIZE];    int front;        /* 头指针 */    int rear;        /* 尾指针，若队列不空，指向队列尾元素的下一个位置 */}SqQueue;Status visit(QElemType c){    printf("%d ",c);    return OK;}/* 初始化一个空队列Q */Status InitQueue(SqQueue *Q){    Q->front=0;    Q->rear=0;    return  OK;}/* 将Q清为空队列 */Status ClearQueue(SqQueue *Q){    Q->front=Q->rear=0;    return OK;}/* 若队列Q为空队列,则返回TRUE,否则返回FALSE */Status QueueEmpty(SqQueue Q){     if(Q.front==Q.rear) /* 队列空的标志 */        return TRUE;    else        return FALSE;}/* 返回Q的元素个数，也就是队列的当前长度 */int QueueLength(SqQueue Q){    return  (Q.rear-Q.front+MAXSIZE)%MAXSIZE;}/* 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR */Status GetHead(SqQueue Q,QElemType *e){    if(Q.front==Q.rear) /* 队列空 */        return ERROR;    *e=Q.data[Q.front];    return OK;}/* 若队列未满，则插入元素e为Q新的队尾元素 */Status EnQueue(SqQueue *Q,QElemType e){    if ((Q->rear+1)%MAXSIZE == Q->front)    /* 队列满的判断 */        return ERROR;    Q->data[Q->rear]=e;            /* 将元素e赋值给队尾 */    Q->rear=(Q->rear+1)%MAXSIZE;/* rear指针向后移一位置， */                                /* 若到最后则转到数组头部 */    return  OK;}/* 若队列不空，则删除Q中队头元素，用e返回其值 */Status DeQueue(SqQueue *Q,QElemType *e){    if (Q->front == Q->rear)            /* 队列空的判断 */        return ERROR;    *e=Q->data[Q->front];                /* 将队头元素赋值给e */    Q->front=(Q->front+1)%MAXSIZE;    /* front指针向后移一位置， */                                    /* 若到最后则转到数组头部 */    return  OK;}/* 从队头到队尾依次对队列Q中每个元素输出 */Status QueueTraverse(SqQueue Q){     int i;    i=Q.front;    while((i+Q.front)!=Q.rear)    {        visit(Q.data[i]);        i=(i+1)%MAXSIZE;    }    printf("\n");    return OK;}int main(){    Status j;    int i=0,l;    QElemType d;    SqQueue Q;    InitQueue(&Q);    printf("初始化队列后，队列空否？%u(1:空 0:否)\n",QueueEmpty(Q));    printf("请输入整型队列元素(不超过%d个),-1为提前结束符: ",MAXSIZE-1);    do    {        /* scanf("%d",&d); */        d=i+100;        if(d==-1)            break;        i++;        EnQueue(&Q,d);    }while(i
      
       0)        printf("现在由队头删除%d个元素:\n",l-2);    while(QueueLength(Q)>2)    {        DeQueue(&Q,&d);        printf("删除的元素值为%d\n",d);    }    j=GetHead(Q,&d);    if(j)        printf("现在队头元素为: %d\n",d);    ClearQueue(&Q);    printf("清空队列后, 队列空否？%u(1:空 0:否)\n",QueueEmpty(Q));    return 0;}
      

 

队列的链式存储结构

队列的链式存储结构其实就是线性表的单链表，只不过它是尾进头出而已，我们把它简称为链队列。

入队的示意图：

出队的示意图：

若链表中除头结点外只剩下一个元素时，则需要将rear指向头结点

下面这种是普通的链表队列出队的情况

链式存储结构的队列实现源码如下：

#include "stdio.h"    #include "stdlib.h"   #include "io.h"  #include "math.h"  #include "time.h"#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define MAXSIZE 20 /* 存储空间初始分配量 */typedef int Status; typedef int QElemType; /* QElemType类型根据实际情况而定，这里假设为int */typedef struct QNode    /* 结点结构 */{   QElemType data;   struct QNode *next;}QNode,*QueuePtr;typedef struct            /* 队列的链表结构 */{   QueuePtr front,rear; /* 队头、队尾指针 */}LinkQueue;Status visit(QElemType c){    printf("%d ",c);    return OK;}/* 构造一个空队列Q */Status InitQueue(LinkQueue *Q){     Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));    if(!Q->front)        exit(OVERFLOW);    Q->front->next=NULL;    return OK;}/* 销毁队列Q */Status DestroyQueue(LinkQueue *Q){    while(Q->front)    {         Q->rear=Q->front->next;         free(Q->front);         Q->front=Q->rear;    }    return OK;}/* 将Q清为空队列 */Status ClearQueue(LinkQueue *Q){    QueuePtr p,q;    Q->rear=Q->front;    p=Q->front->next;    Q->front->next=NULL;    while(p)    {         q=p;         p=p->next;         free(q);    }    return OK;}/* 若Q为空队列,则返回TRUE,否则返回FALSE */Status QueueEmpty(LinkQueue Q){     if(Q.front==Q.rear)        return TRUE;    else        return FALSE;}/* 求队列的长度 */int QueueLength(LinkQueue Q){     int i=0;    QueuePtr p;    p=Q.front;    while(Q.rear!=p)    {         i++;         p=p->next;    }    return i;}/* 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR */Status GetHead(LinkQueue Q,QElemType *e){     QueuePtr p;    if(Q.front==Q.rear)        return ERROR;    p=Q.front->next;    *e=p->data;    return OK;}/* 插入元素e为Q的新的队尾元素 */Status EnQueue(LinkQueue *Q,QElemType e){     QueuePtr s=(QueuePtr)malloc(sizeof(QNode));    if(!s) /* 存储分配失败 */        exit(OVERFLOW);    s->data=e;    s->next=NULL;    Q->rear->next=s;    /* 把拥有元素e的新结点s赋值给原队尾结点的后继，见图中① */    Q->rear=s;        /* 把当前的s设置为队尾结点，rear指向s，见图中② */    return OK;}/* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */Status DeQueue(LinkQueue *Q,QElemType *e){    QueuePtr p;    if(Q->front==Q->rear)        return ERROR;    p=Q->front->next;        /* 将欲删除的队头结点暂存给p，见图中① */    *e=p->data;                /* 将欲删除的队头结点的值赋值给e */    Q->front->next=p->next;/* 将原队头结点的后继p->next赋值给头结点后继，见图中② */    if(Q->rear==p)        /* 若队头就是队尾，则删除后将rear指向头结点，见图中③ */        Q->rear=Q->front;    free(p);    return OK;}/* 从队头到队尾依次对队列Q中每个元素输出 */Status QueueTraverse(LinkQueue Q){    QueuePtr p;    p=Q.front->next;    while(p)    {         visit(p->data);         p=p->next;    }    printf("\n");    return OK;}int main(){    int i;    QElemType d;    LinkQueue q;    i=InitQueue(&q);    if(i)        printf("成功地构造了一个空队列!\n");    printf("是否空队列？%d(1:空 0:否)  ",QueueEmpty(q));    printf("队列的长度为%d\n",QueueLength(q));    EnQueue(&q,-5);    EnQueue(&q,5);    EnQueue(&q,10);    printf("插入3个元素(-5,5,10)后,队列的长度为%d\n",QueueLength(q));    printf("是否空队列？%d(1:空 0:否)  ",QueueEmpty(q));    printf("队列的元素依次为：");    QueueTraverse(q);    i=GetHead(q,&d);    if(i==OK)     printf("队头元素是：%d\n",d);    DeQueue(&q,&d);    printf("删除了队头元素%d\n",d);    i=GetHead(q,&d);    if(i==OK)        printf("新的队头元素是：%d\n",d);    ClearQueue(&q);    printf("清空队列后,q.front=%u q.rear=%u q.front->next=%u\n",q.front,q.rear,q.front->next);    DestroyQueue(&q);    printf("销毁队列后,q.front=%u q.rear=%u\n",q.front, q.rear);        return 0;}

 

总结