数算---栈和队列（一）

栈

栈的定义

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

栈

栈的存储主要有两种方式：

1. 顺序存储:顺序栈，即堆栈的顺序存储结构。利用一组地址连续的存储单元依次存放自栈底到栈顶的元素，同时使用指针 top 指示栈顶元素在顺序栈中的位置。
2. 链式存储:链式栈，即堆栈的链式存储结构。利用单链表的方式来实现堆栈。栈中元素按照插入顺序依次插入到链表的第一个节点之前，并使用栈顶指针 top 指示栈顶元素， top 永远指向链表的头节点位置。

---

顺序栈实现

顺序栈利用数组及一个移动指针即可实现，数组存储数据，指针指向需要插入数据的位置（栈顶），默认从-1开始。

#include <stdio.h>
#include "stdlib.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 InitStack(SqStack *S){
    S->top = -1;//默认空栈时，top指向-1，实际存数据从0开始
    return OK;
}
//清空栈
Status ClearStack(SqStack *S){
    S->top = -1;//不用清空数据，因为后续压栈的数据自然替换了老数据，随着top的移动
    return OK;
}
//是否为空栈
Status StackEmpty(SqStack S){
    if (S.top == -1){
        return TRUE;
    }else{
        return FALSE;
    }
}
//栈当前长度
int StackLength(SqStack S){
    return S.top + 1;
}
//获取栈顶
Status GetTop(SqStack S, SElemType *e){
    if(S.top == -1){
        return ERROR;
    }else{
        *e = S.data[S.top];
    }
    return OK;
}
//入栈
Status PushData(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;
}
//遍历
void PrintStack(SqStack S){
    int i = 0;
    while (i <= S.top) {
        printf("%d ",S.data[i++]);
    }
    printf("\n");
}

可见顺序栈结构很好地利用top栈顶指向来进行入栈出栈等操作。

---

链式栈实现

利用单链表的方式来实现，top同样也是指向栈顶位置，可以将top看作指向链表的首元结点，入栈的数据即插入首元结点，该结点指针域指向原来的首元结点，然后将头指针指向该新结点。

链式栈插入原理
链式栈出栈操作则需要先拿到首元结点，然后直接将top指针指向相邻的结点，将相邻结点看作是栈顶。
链式栈出栈
链式栈代码实现

//初始化
Status InitStack(LinkStack *S){
    S->top = NULL;
    S->count = 0;
    return OK;
}
//清空栈
Status ClearStack(LinkStack *S){
    LinkStackPtr p,q;
    p = S->top;
    while (p) {
        q = p;
        p = p->next;
        free(q);//需要释放
    }
    S->count = 0;//长度置0
    return OK;
}

Status StackEmpty(LinkStack S){
    if(S.count == 0){
        return TRUE;
    }else{
        return FALSE;
    }
}

int StackLength(LinkStack S){
    return S.count;
}
//获取栈顶数据
Status GetTop(LinkStack S, SElemType *e){
    if(S.top == NULL){//空表
        return ERROR;
    }else{
        *e = S.top->data;
        return OK;
    }
}
//入栈
Status Push(LinkStack *S, SElemType e){
    //创建新结点
    LinkStackPtr temp = (LinkStackPtr)malloc(sizeof(StackNode));
    temp->data = e;
    //第一步，next指向原首元结点
    temp->next = S->top;
    //第二步，将此新结点置为栈顶，top指向栈顶
    S->top = temp;
    //第三步，长度加1
    S->count++;
    return OK;
}
//出栈
Status Pop(LinkStack *S, SElemType *e){
    LinkStackPtr p;
    if(StackEmpty(*S)){
        return ERROR;
    }
    
    *e = S->top->data;
    //第一步，先拿到栈顶结点，稍后释放
    p = S->top;
    //第二步，将相邻结点设为新栈顶
    S->top = S->top->next;
    free(p);//释放出栈结点空间
    S->count --;//长度减1
    return OK;
}
//遍历
void PrintStack(LinkStack S){
    LinkStackPtr p;
    p = S.top;
    while (p) {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

---

---

队列

队列定义

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

在空间利用率上来讲，队列可以分为顺序队列和循环队列，区别就是循环队列是在顺序队列基础上，可以实现空间循环利用的优点。除了一些简单的场景外，循环队列实用性更强。

顺序队列

建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针front，它指向队头元素；另一个是队尾指针rear，它指向下一个入队元素的存储位置。

顺序队列

如上图所示，当rear增加到指向分配的连续空间之外时，队列无法再插入新元素，但这时往往还有大量可用空间未被占用，这些空间是已经出队的队列元素曾经占用过得存储单元。这样就出现了一种“假满”现象，造成空间浪费。

顺序队列代码实现

/* 循环队列的顺序存储结构 */
typedef struct
{
    QElemType data[MAXSIZE];
    int front;        /* 头指针 */
    int rear;        /* 尾指针，若队列不空，指向队列尾元素的下一个位置 */
}SqQueue;

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

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

Status QueueEmpty(SqQueue Q){
    if(Q.rear == Q.front){
        return TRUE;
    }else{
        return FALSE;
    }
}

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

Status GetHead(SqQueue Q, QElemType *e){
    if(Q.rear == Q.front)//空
        return ERROR;
    
    *e = Q.data[Q.front];
    return OK;
}

Status EnQueue(SqQueue *Q, QElemType e){
    //满了
    if((Q->rear + 1)%MAXSIZE == Q->front){
        return ERROR;
    }
    Q->data[Q->rear] = 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];
    Q->front = (Q->front + 1)%MAXSIZE;
    return OK;
}

Status QueuePrint(SqQueue Q){
    int i;
    i = Q.front;
    while ((i + Q.front) != Q.rear) {
        printf("%d  ",Q.data[i]);
        i = (i + 1)%MAXSIZE;
    }
    printf("\n");
    return OK;
}

链式队列代码实现

typedef struct QNode    /* 结点结构 */
{
    QElemType data;
    struct QNode *next;//指向队列的下一个
}QNode,*QueuePtr;

typedef struct            /* 队列的链表结构 */
{
    QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;

Status InitQueue(LinkQueue *Q){
    //初始化了一个头结点
    Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
    if(!Q->front){
        return ERROR;
    }
    Q->front->next = NULL;
    
    return OK;
}

Status DestroyQueue(LinkQueue *Q){
    while (Q->front) {
        Q->rear = Q->front->next;
        free(Q->front);
        Q->front = Q->rear;
    }//头结点都没了
    return OK;
}

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;
}

Status QueueEmpty(LinkQueue Q){
    if(Q.front == Q.rear)
        return TRUE;
    else
        return FALSE;
}

Status QueueLength(LinkQueue Q){
    int i = 0;
    QueuePtr p;
    p = Q.front;
    while (Q.rear != p) {
        i ++;
        p = p->next;
    }
    return i;
}

Status EnQueue(LinkQueue *Q, QElemType e){
    QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
    if(!s){
        return ERROR;
    }
    s->data = e;
    s->next = NULL;
    Q->rear->next = s;
    Q->rear = s;
    return OK;
}

Status DeQueue(LinkQueue *Q, QElemType *e){
    QueuePtr 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 = Q->front;
    free(p);
    return OK;
}

Status GetHead(LinkQueue Q, QElemType *e){
    if(Q.front != Q.rear){
        *e = Q.front->next->data;
        return TRUE;
    }
    return FALSE;
}

Status PrintQueue(LinkQueue Q){
    QueuePtr p;
    p = Q.front->next;
    while (p) {
        printf("%d  ",p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}

---

循环队列

在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，一旦rear指针增1或front指针增1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。

这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。

循环队列1
如上图所示，存在一个问题，那就是空队列和队列满时都满足Q.rear == Q.front，所以这就容易起冲突，为了避免这个问题，需要牺牲一个位置置空，当满足 （Q.rear +1 ）% MAXSIZE == Q.front，此队列呈“满”状态。
循环队列2