栈与队列 - Yuan's Blog

栈是限定仅在表位进行插入和删除操作的线性表,把允许插入和删除的一端称为栈顶,另一端称为栈底,不含任何数据元素的栈称为空栈.栈又称为后进先出(LIFO)的线性表。

栈的抽象数据类型

ADT 栈（stack）
Data
    线性表的数据对象集合为{a1, a2,......,an},每个元素的类型均为DataType。其中第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
Operation
    InitStack（*S）：初始化操作，建立一个空栈。
    DestroyStack（*S）：若栈存在，则销毁它。
    ClearStack（*S）：将栈清空。
    StackEmpty（S）：若栈为空，返回TURE
    GetTop（S，*e）：若栈存在且为空， 用e返回s的栈顶元素。
    Pop（*S，*e）：删除栈S中的栈顶元素，并用e返回值。
    StackLength（S）：返回栈S的元素个数。
endADT

栈的存储结构

顺序存储

typedef int SElemType;  //指定存储类型
//栈的结构定义
typedef struct
{
    SElemType data[MAXSIZE];
    int top;
}
//进栈
Status Push(SqStack *S,SElemType e)
{
    if(S->top == MAXSIZE -1)
    {
        return ERROR;
    }
    S->top++;
    S->data[S->top]=e;
    return OK;
}
//出栈
Status Pop(SqStack *S,SElemType *e)
{
    if(S->top==-1)
        return ERROR;
    *e=S->data[S->top];
    S->top--;
    return OK;
}

链式存储结构

//结构定义
typedef struct StackNode
{
    SElemType data;
    struct StackNode *next;
}StackNode,*LinkStackPtr;
typedef struct
{
    LinkStackPtr top;
    int count;
}LinkStack;
//进栈
Status Push(LinkStack *S,SElemType e)   //插入元素e为新的栈顶元素
{
    LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode));
    s->data=e;
    s->next=S->top; //把当前的栈顶存在新结点中
    S->top=s;   //把新结点指成栈顶
    S->count++;
    return OK;
}
//出栈
Status Pop(LinkStack *S,SElemType *e)   //删除栈顶,并用e返回其值
{
    LinkStackPtr p;
    if(StackEmpty(*S))
        return ERROR;
    *e=S->top->data;    //把删的数据值拿出来
    p=S->top;   //把删的结点拿出来
    S->top=S->top->next;    //跟换栈顶
    free(p)
    S->count--;
    return OK;
}

栈的应用

递归

斐波拉契递归

四则运算表达式求值

常见的四则运算的表达式叫做中缀表达式,而计算机在计算时无法辨别表达式运算的优先顺序,因此就要将中缀表达式转化为后缀表达式。其步骤要遵循一下规则：

从左至右，遇到数字就输出，遇到运算符号就进栈
将栈中的运算符与即将进栈的运算符进行比较，如果即将进栈的运算符优先级低于栈顶运算符，则输出栈顶运算符。如果没有，则进栈。
如果遇到），则输出（之前的运算符。

现在得到了后缀表达式，例如 9+(3-1)*3+10/2 的后缀表达式则为 9 3 1 -3*+10 2/+ 。在进行后缀表达式计算中，计算机会运用如下规则：

从左到右遍历表达式的每个数字和符号
遇到数字就进栈，遇到符号就将处于栈顶的两个数字出栈。

队列

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

队列的抽象数据类型

ADT 队列（Queue）
Data
    同线性表
Operation
    InitQueus(*Q)：初始化操作，建立一个列Q。
    DestroyQueue(*Q)：若队列Q存在，则销毁它。
    ClearQueue(*Q)：将队列Q清空。
    QueneEmpty(Q):若队列Q为空，返回TURE
    GetHead(Q,*e):若队列为非空，用e返回s的队头元素
    EnQueue(*Q,e):若队列Q存在，插入新元素e到队列Q中并成为队尾元素。
    DeQueue(*Q,*e):删除队列Q中队头元素，并用e返回值。
    QueueLength(Q):返回队列Q的元素个数。
endADT

队列循环

把队列头尾相接排列的顺序存储结构称为循环队列，其中 front 指向队头，rear 指向队尾新入队结点的位置。通过修改队列的存储条件：将队列保留一个元素空间。就可以通过队头 front 和队尾 rear 判断队列是否满了，其公式为 (rear-front+QueueSize)%QueueSize

typedef int QElemType;
typedef struct
{
    QElemType data[MAXSIZE];
    int front;
    int rear;
}SqQueue;

Status InitQueue(SqQueue *Q)
{
    Q->front=0;
    Q->rear=0;
    return OK;
}

int QueueLength(SqQueue Q)
{
    return (Q.rear-Q.front+MAXSIZE)%MAXSIZE；
}

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; //如果满了就放在最前边
    return OK;
}

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   //将队头指针后移一位，如果最后就移到开头
    return OK;
}

队列链式存储

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

typedef intQElemType;

typedef struct QNode
{
    QElemType data;
    struct QNode *next;
}QNode,*QueuePtr;

typedef struct
{
    QueuePtr front,rear;
}LinkQueue;

Status EnQueue(LinkQue *Q,QElemType e)
{
    QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
    if(!s)
        exit(OVERLOW);  //存储分配失败
    s->data=e;
    s->next=NULL;
    Q->rear->next=s;
    Q->rear=s;
    return OK;
}

Status DeQueue(LinkQueue *Q,QElemType *e)
{
    Queue p;
    if(Q->front==Q->rear)
        return ERROR;
    P=Q->front->next;
    *e=p->data;
    Q->front->next=p->next;
    if(Q->rear==p)
        Q->rear=Qfront;
    free(p);
    return OK;
}