栈和队列

���前言

栈和队列是两种重要的线性结构。从数据结构角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，它们是操作受限的线性表，因此，可称为限定性的数据结构。

但是从数据类型角度看，栈和队列是和线性表大不相同的两种重要的抽象数据类型。栈和队列的运用比较广泛，属于多型数据类型。

���栈（satck）

���栈的定义

栈(stack)是限定仅在表尾进行插入或删除操作的线性表。因此，对于栈来说，表尾端有其特殊的含义，称为栈顶(top)，相应地，表头端称为栈底(bottom)。不包含元素的空表称为空栈

假设S = ( a 1 , a 2 , . . . . a n ) S=(a1, a2,....an)S=(a1,a2,....an)，则称a 1 a1a1为栈底元素，a n anan为栈顶元素。栈中元素按a 1 , a 2 , . . . a n a1,a2,...ana1,a2,...an的次序进栈，那么出栈的第一个元素应为栈顶元素。

栈的修改是按照后进先出的原则进行的，因此，栈又称为后进先出(last in first out)的线性表（简称LIFO）结构

���共享栈（节省空间）

两个栈共享一个存储空间，意义在于高效利用存储空间

���第二种说法：两个栈底分别设置在一个空间的两端，栈顶向中间延伸

共享栈的定义

typedef struct Linknode{

    ElemType data;      //数据域

    struct Linknode *next;      //指针域

}LiStack;                   //栈类型定义

���共享栈的栈满情况：当两个栈的top在空间中某一位置相遇时

���栈的表示和实现（顺序栈）

和线性表类似，栈也有两种存储表示方法——顺序栈和链栈

顺序栈，即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附加指针top表示栈顶元素在顺序栈中的位置。通常当top=-1时，表示此栈为空栈。

���顺序栈的定义

# define MaxSize 10         //定义栈中元素的最大个数

typedef struct{

    ElemType data[MaxSize];    //静态数组存放栈中元素

    int top;                   //栈顶指针

}SqStack;

void testStack(){

    SqStack S;      //声明一个顺序栈(分配空间)

    .....

    //后续操作

}

由于栈在使用过程中所需要最大空间的大小很难估计，所以，一般来说，在初始化设空栈时不应限定栈的最大容量，常规做法是：先为栈分配一个基本容量，然后在应用过程中，当栈的空间不够使用时再逐步扩大容量

���初始化操作

构造一个空栈，分配内存空间

# define MaxSize 10         //定义栈中元素的最大个数

typedef struct{

    ElemType data[MaxSize];    //静态数组存放栈中元素

    int top;                   //栈顶指针

}SqStack;

void InitStack(SqStack &S){

    S.top = -1;             //初始化栈顶指针

}

void testStack(){

    SqStack S;      //声明一个顺序栈(分配空间)

    InitStack(S);

    .....

    //后续操作

}

//栈的判空操作

bool StackEmpty(SqStack S){

    if(S.top == -1){

        return true;        //栈空

    }

    else{

        return false;       //不为空

    }

}

第二种定义

按设定的初始分配量进行第一次存储分配，base可称为是栈底指针，在顺序占中，它始终指向栈底的位置，若base的值为NULL，则表明栈结构不存在，top表示栈顶指针，其初始值指向栈底，即top==base，空栈可以表示为top==base。每当插入新的栈顶元素时，指针top增加1，删除栈顶元素时，指针top减1，因此，非空栈中的栈顶指针始终在栈顶元素的下一个位置上

#define STACK_INIT_SIZE 100;        //存储空间初始分配量

#define STACKINCREMENT 10;          //存储空间分配增量

typedef struct{

    SElemType *base;        //栈底指针

    SElemType *top;         //栈顶指针

    int stacksize;          //当前已分配的空间

}SqStack;

void InitStack(SqStack &S){

    //构造一个空栈

    S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));

    if(!S.base) exit(OVERFLOW);         //存储分配失败

    S.top = S.base;

    S.stacksize = STACK_INIT_SIZE;

}

void testStack(){

    SqStack S;          //声明一个顺序栈

    InitStack(S);

    ....

    //后续操作

}

���进栈操作

若栈未满，则将x加入使之成为新栈顶

#define MaxSize 10;     //定义栈中元素的最大个数

typedef struct{

    ElemType data[MaxSize];     //静态数组存放栈中元素

    int top;                    //栈顶指针

}SqStack;

//新元素入栈

bool Push(SqStack &S, ElemType x){

    if(S.top == MaxSize-1){     //表示栈满了

        return false;

    }

    S.top = S.top + 1;          //指针先加一

    S.data[S.top] = x;          //新元素入栈

    return true;

}

���出栈操作

若栈非空，则释放栈顶元素，并返回。

#define MaxSize 10;     //定义栈中元素的最大个数

typedef struct{

    ElemType data[MaxSize];     //静态数组存放栈中元素

    int top;                    //栈顶指针

}SqStack;

//出栈操作

bool Pop(SqStack &S, ElemType &x){

    if(S.top == -1){        //栈空，报错

        return false;

    }

    x = S.data[S.top];      //栈顶元素先出栈

    S.top = S.top - 1;      //指针再减1

    return true;

}

���读取栈顶元素

若栈非空，则用x返回栈顶元素

#define MaxSize 10;     //定义栈中元素的最大个数

typedef struct{

    ElemType data[MaxSize];     //静态数组存放栈中元素

    int top;                    //栈顶指针

}SqStack;

//读取栈顶元素

bool GetTop(SqStack &S, ElemType &x){

    if(S.top == -1){        //栈空，报错

        return false;

    }

    x = S.data[S.top];      //记录栈顶元素

    return true;

}

���栈的表示和实现（链栈）

对于链栈的基本操作来说，和单链表的插入删除很类似，所以就不在赘述，链栈的入栈和出栈操作，其实就对应单链表的插入和删除操作

���链栈的定义

typedef struct Linknode{

    ElemType data;      //数据域

    struct Linknode *next;      //指针域

}LiStack;                   //栈类型定义

栈的非法操作

���上溢：当栈满了的情况下再次放入元素会造成此情况

���下溢：当栈空了的情况下再次删除元素会造成此情况

���队列（queue）

���队列的定义

和栈相反，队列(queue)是一种先进先出(first in first out)的线性表（缩写为FIFO）。它只允许在表的一端进行插入，在另一端进行删除元素。这种数据结构概括起来就和我们平时排队是一样的道理，最早进入到的队列的元素最先离开。

在队列中，只允许插入的一端叫做队尾(rear)，允许删除的一端则称为队头(front)。假设队列为q = ( a 1 , a 2 , . . . a n ) ， q=(a1,a2,...an)，q=(a1,a2,...an)，那么，a 1 a1a1就是队头元素，a n anan就是队尾元素。队列中的元素是按照a 1 , a 2 , a 3.... a n a1,a2,a3....ana1,a2,a3....an的顺序进入的，退出队列也只能按照这个次序依次退出，也就是说，只有在a 1 , a 2 , a 3... a n − 1 a1,a2,a3...an-1a1,a2,a3...an−1都离开队列之后，a n anan才能退出队列

���队首队尾指针的两种指法

⭐队首指针（front）指向：队头元素的前一个存储位置

⭐队尾指针（rear）指向：队尾元素

⚡队首指针（front）指向：队头元素

⚡队尾指针（rear）指向：队尾元素的下一个存储位置

���假溢出：队中有空间，元素无法入队

���队列的顺序表示和实现（顺序队列）

和顺序栈类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放队列头到队列尾的元素之外，还需要附设两个指针front和rear分别指示队列头元素以及队列尾元素的位置。基本操作基于循环队列，循环队列的引出是为了解决假溢出的问题。

���循环队列的性质

⛅数组实现

空队列：front == rear

满队列：牺牲一个单元判满（不牺牲的话队空队满无法区分）

（rear+1）% maxSize == front

进队：rear新 = （rear旧+1）% maxSize

出队：front新 = （front旧+1）% maxSize

队中元素个数/长度：(rear - front + maxSize) % maxSize

���初始化操作

初始化队列，构造一个空队列

#define MaxSize 10         //定义队列中元素的最大个数

typedef struct{

    ElemType data[MaxSize];     //用静态数组存放队列元素

    int front, rear;            //队头指针和队尾指针

}SqQueue;

//初始化队列

void InitQueue(SqQueue &Q){

    //初始化 队头、队尾指针指向0

    Q.rear = Q.front = 0;

}

void testQueue(){

    //声明一个队列（顺序存储）

    SqQueue Q;

    InitQueue(Q);

    ...

    //后续操作

}

//判断队列是否为空

bool QueueEmpty(SqQueue Q){

    if(Q.rear == Q.front){  //队空条件

        return true;

    }else{

        return false;

    }

}

���入队操作

若队列未满，将x加入，使之称为新的队尾

#define MaxSize 10         //定义队列中元素的最大个数

typedef struct{

    ElemType data[MaxSize];     //用静态数组存放队列元素

    int front, rear;            //队头指针和队尾指针

}SqQueue;

//入队

bool EnQueue(SqQueue &Q, ElemType x){

    if((Q.rear+1)%MaxSize == Q.front){       //判断队列是否已满

        return false;       //对满则报错

    }

    Q.data[Q.rear] = x;     //将x插入队尾

    Q.rear = (Q.rear + 1) % MaxSize;    //队尾指针后移

    return true;

}

���出队操作

若队列非空，删除队头元素并返回x

#define MaxSize 10         //定义队列中元素的最大个数

typedef struct{

    ElemType data[MaxSize];     //用静态数组存放队列元素

    int front, rear;            //队头指针和队尾指针

}SqQueue;

//出队(删除一个队头元素，并返回x)

bool DeQueue(SqQueue &Q, ElemType &x){

    if(Q.rear == Q.front){      //判断队空

        return false;           //队空则报错

    }

    x = Q.data[Q.front];

    Q.front = (Q.front+1)%MaxSize;

    return true;

}

���获取队头元素操作

读队头元素，若队列非空，则将队头元素赋值给x

#define MaxSize 10         //定义队列中元素的最大个数

typedef struct{

    ElemType data[MaxSize];     //用静态数组存放队列元素

    int front, rear;            //队头指针和队尾指针

}SqQueue;

//获得队头元素的值，用x返回

bool GetHead(SqQueue Q, ElemType &x){

    if(Q.rear == Q.front){

        return false;       //队空报错

    }

    x = Q.data[Q.front];

    return true;

}

���队列的链式表示和实现（链队列）

和线性表类似，队列也可以有两种存储表示

用链表表示的队列简称为链队列，一个链队列显然需要两个分别指示队头和队尾的指针（分别称为头指针和尾指针）才能唯一确定。

链队列的操作即为单链表的插入和删除操作的特殊情况，只是需要修改尾指针或头指针

一般情况下，删除队列头元素时仅需修改头结点中的指针，但当队列中最后一个元素被删除后，队列表尾指针也丢失了，因此需对队尾指针重新赋值（指向头结点）

���初始化操作

初始化队列，构造一个空队列

���带头结点：

typedef struct LinkNode{        //链式队列结点

    ElemType data;

    struct LinkNode *next;

}LinkNode;

typedef struct{     //链式队列

    LinkNode *front, *rear  //队列的队头和队尾指针

}LinkQueue;

//初始化队列(带头结点)

void InitQueue(LinkQueue &Q){

    //初始化 front、rear都指向头结点

    Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));

    Q.front -> next = NULL;

}

viod testLinkQueue(){

    LinkQueue Q;        //声明一个队列

    InitQueue(Q);       //初始化队列

}

在实际使用中，还可以有输出受限的双端队列（即一个端点允许插入和删除，另一个端点只允许插入的双端队列）和输入受限的双端队列（即一个端点允许插入和删除，另一个端点只允许删除的双端队列）。而如果限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变为了两个栈底相邻接的栈了