数据结构 408-3-1&2 - 数据结构 - 计算机科学 | Flüstern = Whispering's Blog = 无需过去，无关未来，只有现在

# 栈的定义

栈是一个只允许一端进行插入或删除操作的线性表

重要术语：栈顶、栈底、空栈

栈顶：允许插入和删除的一端
栈底：不允许插入和删除的一端
特点：后进先出（LIFO）
逻辑结构：与普通的线性表相同
数据的运算：插入、删除操作有区别

# 栈的基本操作

InitStack (&S)：初始化栈。构造一个空栈 S，分配内存空间

DestroyStack (&S)：销毁栈。销毁并释放栈 S 所占用的内存空间

Push (&S,x)：进栈，若栈 S 未满，则将 x 加入使之称为新栈顶

Pop (&S,x)：出栈，若栈 S 非空，则弹出栈顶元素，并用 x 返回

GetTop (&S)：读栈顶元素，若栈 S 非空，则用 x 返回栈顶元素

StackEmpty (S)：判断一个栈 S 是否为空。若 S 为空，则返回 true，否则返回 false

n 个不同的元素进栈，出栈元素不同的排列的个数位\frac{1}{n}C_{2n}^

# 顺序栈

顺序栈的定义：

#define MaxSize 10    //定义栈中元素的最大个数
typedef struct{
    ElemType data[MaxSize];  //静态数组存放栈元素
    int top;     //栈顶指针
}SqStack;

顺序存储，给各个数据元素分配连续的存储空间，大小为 MaxSize*sizeof (ElemType)

栈的基本操作：

void InitStack(SqStack &S){
    S.top=-1;  //初始化栈顶指针
}

bool StackEmpty(SqStack &S){  //判空操作
    if(S.top==-1)  //栈空
        return true;
    else //栈不为空
        return false;
}

bool Push(SqStack &S,ElemType x){ //入栈操作
    if(S.top==MaxSize-1) //栈满，报错
        return false;
    S.top=S.top+1;  //指针+1
    S.data[S.top]=x; //新元素入栈
    //或者直接S.data[++S.top]=x;
    return true;
}

bool Pop(SqStack &S,ElemType &x){ //出栈操作
    if(S.top==-1) //如果栈为空
        return false;
    x=S.data[S.top];
    S.top--;
    //等价于x=S.data[S.top--];
    return true;
}
//出栈操作数据还在内存当中，只是逻辑上已经被移除了
bool GetTop(SqStack &S,ElemType &x){
    if(S.top==-1)
        return false;
   	x=S.data[S.top];
    return true;
}

顺序栈的缺点：栈的大小不可变

# 共享栈

#define MaxSize 10
typedef struct{
    ElemType data[MaxSize];
    int top0; //0号栈顶指针
    int top1; //1号栈顶指针
} ShStack;

void InitStack(ShStack &S){
    S.top0=-1;
    S.top1=MaxSize;
}

栈满的条件：top0+1==top1

# 链栈

链栈定义：

typedef struct Linknode{
    ElemType data; //数据域
    struct Linknode *next; //指针域
} *LiStack;

至于基本操作，请参考带头结点的链表和不带头结点的链表的增加删除操作。

链栈仅仅只是所有的插入都是头插法，删除都是删除头结点的特殊情况，比起单独链表还好写

# 队列的定义

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

特点：先进入队列的元素先出队

重要术语：队头、队尾、空队列

队头：允许删除的一端
队尾：允许插入的一端

队列特点：先进先出 (FIFO)

# 队列的基本操作

InitQueue (&Q)：初始化队列，构造一个空队列 Q

DestroyQueue (&Q)：销毁队列，销毁并释放队列 Q 所占用的内存空间

EnQueue (&Q,x)：入队，若队列 Q 未满，将 x 加入，使之称为新的队尾

DeQueue (&Q,x)：出队，若队列 Q 非空，删除队头元素，并用 x 返回

GetHead (Q,&x)：获取队头元素，若队列非空，则将队头赋值给 x

QueueEmpty (Q)：判队列空，若队列 Q 位空，返回 true，否则返回 false

# 队列的顺序实现

#define MaxSize 10
typedef struct{
    ElemType data[MaxSize];  //用静态数组存放队列元素
    int front,rear; //队头指针和队尾指针
} SqQueue;

void InitQueue(SqQueue &Q){ //初始化
    //初始化时，队头、队尾指针指向0
    Q.rear=Q.front=0;
}

bool QueueEmpty(SqQueue Q){ //队列判空
    if(Q.rear==Q.front)
        return true;
    else
        return false;
}

bool EnQueue(SqQueue &Q,ElemType x){ //入队
    if((Q.rear+1)%MaxSize==Q.front) //本质上这个队列被改造成了循环队列
        return false;
    Q.data[Q.rear]=x;
    Q.rear=(Q.rear+1)%MaxSize;
    return true;
}

bool DeQueue(SqQueue &Q,ElemType x){ //出队（删除一个元素，并用x返回）
    if(Q.rear==Q.front)
        return false;
    x=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    return true;
}

bool GetHead(SqQueue Q,ElemType &x){ //获取队头
    if(Q.rear==Q.front)
        return false;
    x=Q.data[Q.front];
    return true;
}

队列元素个数：(rear+MaxSize-front)% MaxSize

判断队列已满 / 为空：

常规方法：(Q.rear+1)% MaxSize==Q.front，但是会浪费一个空间
增加 size，用 size 来记录队列元素个数以判断是否为满 \ 空
增加 tag，tag 表示最近进行的是删除 / 插入，初始为 0，每次删除操作成功时，都令 tag=0，每次插入操作成功时，都令 tag=1，只有删除操作，才会导致队列为空，同样只有插入操作，才会导致队列为满，因此：
- 队列为满：Q.rear==Q.front && tag == 1
- 队列为空：Q.rear==Q.front && tag == 0

注意：有的题目队尾指针可能指向的是队尾元素，上面讨论结果都是队尾指针指向队尾元素的下一个元素

# 队列链式实现

typedef struct LinkNode{ //链式队列节点
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct{ //链式队列
    LinkNode *front,*rear; //队列的队头和队尾指针
}LinkQueue;

void InitQueue(LinkQueue &Q){ //带头结点
    Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next=NULL;
}

bool IsEmpty(LinkQueue &Q){ //带头结点
    if(Q.front==Q.rear)
        return true;
    else
        return false;
}

void InitQueue(LinkQueue &Q){ //不带头结点
    Q.front=NULL;
    Q.rear=NULL;
}

bool IsEmpty(LinkQueue &Q){ //不带头结点
    if(Q.front==NULL)
        return true;
    else
        return false;
}

void Enqueue(LinkQueue &Q,ElemType x){  //新元素入队（带头结点）
    LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    Q.rear->next=s; //新节点插入到rear之前
    Q.rear=s; //修改表尾指针
}

void Enqueue(LinkQueue &Q,ElemType x){  //新元素入队（不带头结点）
    LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    if(Q.front==NULL){
        Q.front=s;
        Q.rear=s;
    } else{
        Q.rear->next=s; //新节点插入到rear之前
    	Q.rear=s; //修改表尾指针
    }
}

bool Dequeue(LinkQueue &Q,ElemType &x){ //队头出队（带头结点）
    if(Q.front==Q.rear)
        return false; //空队
    LinkNode *p=Q.front->next;
    x=p->data;  //用变量x返回队头元素
    Q.front->next=p->next; //修改头结点的next指针
    if(Q.rear==p) //此次是最后一个节点
        Q.rear=Q.front; //修改rear指针
   	free(p);  //释放空间
    return true;
}

bool Dequeue(LinkQueue &Q,ElemType &x){ //队头出队（不带头结点）
    if(Q.front==NULL)
        return false; //空队
    LinkNode *p=Q.front->next;
    x=p->data;  //用变量x返回队头元素
    Q.front=p->next; //修改头结点的next指针
    if(Q.rear==p){ //此次是最后一个节点
        Q.rear=NULL;
        Q.front=NULL;
    } 
   	free(p);  //释放空间
    return true;
}

# 双端队列

队列：只允许从一端插入、另一端删除的线性表

双端队列：只允许从两端插入、两端删除的线性表

输入受限的双端队列：只允许从一端插入、两端删除的线性表

输出受限的双端队列：只允许从两端插入，一端删除的线性表

考点：判断输出序列的合法性

输入受限的双端队列：栈中合法的序列，双端队列中一定也合法

输出受限的双端队列：栈中合法的序列，双端队列中一定也合法

数据结构考研408