warehouse queue - yaokun123/php-wiki GitHub Wiki

栈和队列

一、栈的定义

官方定义

栈(Stack)是一个后进先出(Last in first out,LIFO)的线性表，他要求只在表尾进行删除和插入操作。

所谓的栈，其实也就是一个特殊的线性表（顺序表、链表），但是它在操作上有一些特殊的要求和限制：
-栈的元素必须“后进先出”。
-栈的操作只能在这个线性表的表尾进行。
-注：对于栈来说，这个表尾称为栈的栈顶(top)，响应的表头称为栈低(bottom)。

栈是一种重要的线性结构，可以这样讲，栈是前面讲过的线性表的一种具体形式。

栈这种后进先出的数据结构应用是非常广泛的。在生活中，例如我们的浏览器，每点击一次“后退”都是退回到最近的一次浏览网页。 例如我们的Word、Photoshop等的“撤销”功能也是如此。再例如我们C语言的函数，也是利用栈的基本原理实现的。

二、栈的插入和删除操作

栈的插入操作(push)，叫做进栈，也称为压栈，入栈。类似子弹放入弹夹的动作。

栈的删除操作(pop)，叫做出栈，也称为弹栈，如同弹夹中的子弹出夹。

三、栈的顺序存储结构

因为栈的本质是一个线性表，线性表有两种存储形式，那么栈也有分为栈的顺序存储结构和栈的链式存储结构。

最开始栈中不含有任何数据，叫做空栈，此时栈顶就是栈底。然后数据从栈顶进入，栈顶栈低分离，整个栈的当前容量变大。数据出栈时从栈顶弹出，栈顶下移，整个栈的当前容量变小。

typedef int ElemType;
typedef struct{
    ElemType *base;
    ElemType *top;
    int stackSize;
}sqStack;

有些朋友提出疑问：怎么没有data元素存放数据？怎么会有两个ElemType元素？

其实如果按照套路出牌，我们完全可以这样子声明

typedef int ElemType;
type struct{
    ElemType data[MAXSIZE];
    int top;/用于标注栈顶的位置
    int stackSize;
}

这里定义了一个顺序存储的栈，它包含了三个元素：base、top、stackSize。其中base是指向栈低的指针变量，top是指向栈顶的指针变量，stackSize指示栈的当前可使用的最大容量。

创建一个栈

#define STACK_INIT_SIZE 100
initStack(sqStack *s){
    s->base = (ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));

    if(!s->base){
        exit(0);
    }

    s->top = s->base;//最开始，栈顶就是栈底
    s->stackSize = STACK_INIT_SIZE;
}

入栈操作

入栈操作又叫做压栈操作，就是向栈中存放数据。

入栈操作要在栈顶进行，每次向栈中压入一个数据，top指针就要+1，直到栈满为止。

#define SATCKINCREMENT 10

Push(sqStack *s,ElemType e){
    //如果栈满，追加空间
    if(s->top - s->base >= s->stackSize){
        s->base = (ElemType *)realloc(s->base,(s->stackSize + STACKINCREMENT) * sizeof(ElemType));
        
        if(!s->base){
            exit(0);
        }

        s->top = s->base + s->stackSize;//设置栈顶
        s->stackSize = s->stackSize + STACKINCREMENT;//设置栈的最大容量
    }

    *(s->top) = e;
    s->top++;
}

出栈操作

出栈操作就是在栈顶取出数据，栈顶指针随之下移的操作。

每当从栈内弹出一个数据，栈的当前容量就-1。

Pop(sqStack *s,ElemType *e){
    if(s->top == s->base){//栈已空
        return;
    }
    *e = *--(s->top);
}

清空一个栈

所谓清空一个栈，就是将栈中的元素全部作废，但栈本身物理空间并不发生改变（不是销毁）。

因此我们只需要将s->top的内容赋值为s->base即可，这样s->base等于s->top，也就标明这个栈是空的了，这个原理跟高级格式化是单纯的清空文件列表而没有覆盖硬盘的原理是一样的。

ClearStack(sqStack *s){
    s->top = s->base;
}

销毁一个栈

销毁一个栈与清空一个栈不同，销毁一个栈是要释放掉该栈所占用的物理内存空间，因此不要把销毁一个栈与清空一个栈这两种操作混淆。

DestoryStack(sqStack *s){
    int i,len;
    len = s->stackSize;
    
    for(i = 0;i<len;i++){
        free(s->base);
        s->base++;
    }

    s->base = s->top = NULL;
    s->stackSize = 0;
}

计算栈的当前容量

计算栈的当前容量也就是计算栈中元素的个数，因此只要返回s.top-s.base即可。

注意，栈的最大容量是指该栈占据内存空间的大小，其实是s.stackSize，它与栈的当前容量不是一个概念。

int StackLen(){
    return (s.top - s.base);//初学者需要重点讲解
}

实例分析

题目：利用栈的数据结构特点，将二进制转换为十进制数。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10

typedef char ElemType;
typedef struct {
    ElemType *base;
    ElemType *top;
    int stackSize;
}sqStack;

void InitStack(sqStack *s){
    s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    
    if(!s->base){
        exit(0);
    }
    
    s->top = s->base;
    s->stackSize = STACK_INIT_SIZE;
}

void Push(sqStack *s,ElemType e){
    if(s->top - s->base >= STACK_INIT_SIZE){
        s->base = (ElemType *)realloc(s->base,(s->stackSize+STACKINCREMENT) *sizeof(ElemType));
        
        if(s->base){
            exit(0);
        }
    }
    *(s->top) = e;
    s->top++;
}

void Pop(sqStack *s,ElemType *e){
    if(s->top == s->base){
        return;
    }
    *e = *--(s->top);
}

int StackLen(sqStack s){
    return (s.top - s.base);
}


int main(){
    ElemType c;
    sqStack s;
    int len,i,sum = 0;
    
    InitStack(&s);
    
    printf("请输入二进制数，输入#符号表示结束\n");
    scanf("%c",&c);
    
    while(c!= '#'){
        Push(&s,c);
        scanf("%c",&c);
    }
    getchar();//把\n从缓冲区去掉
    
    len = StackLen(s);
    
    for(i=0;i<len;i++){
        Pop(&s,&c);
        sum = sum + (c-48) * pow(2,i);
    }
    printf("转化为十进制值:%d\n",sum);
    return 0;
}

四、栈的链式存储结构

栈的链式存储结构，简称栈链。（通常我们用的都是栈的顺序存储结构，链式存储我们作为一个知识点，大家知道就好！）

typedef struct StackNode{
    ElemType data;//存放栈的数据
    struct StackNode *next;
}StackNode,*LinkStackPtr;

typedef struct LinkStack{
    LinkStackPrt top;//top指针
    int count;//栈元素计数器
}

进栈操作

对于栈链的Push操作，假设元素值为e的新节点是s，top为栈顶指针，我们得到如代码

Status Push(LinkStack *s,ElemType e){
    LinkStackPtr p = (LinkStackPtr) malloc(sizeof(StackNode));

    p->data = e;
    p->next = s->top;
    s->top = p;
    s->count++;
    return OK;
}

出栈操作

至于链栈的出栈Pop操作，假设变量p用来存储要删除的栈顶节点，将栈顶指针下移一位，最后释放p即可

Status Pop(LinkStack *s,ElemType *e){
    LinkStackPtr p;

    if(StackEmpty(*s)){//判断是否为空栈
        return ERROR;
    }

    *e = s->top->data;
    p = s->top;
    free(p);
    s->count--;
    return OK;
}

五、队列

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

与栈相反，队列是一种先进先出(First In First Out,FIFO)的线性表

与栈相同的是，队列也是一种重要的线性结构，实现一个队列同样需要顺序表或链表作为基础。

我们的输入缓冲区接受键盘的输入就是按队列的形式输入和输出的。

队列的链式存储结构

队列既可以用链表实现，也可以用顺序表实现。跟栈相反的是，栈一般我们用顺序表来实现，而队列我们常用链表来实现，简称为链队列。

typedef struct QNode{
    ElemType data;
    struct QNode *next;
}QNode,*QueuePrt;


typedef struct{
    QueuePrt front,rear;//队头、尾指针
}LinkQueue;

我们将队头指针指向链队的头节点，而队尾指针指向终端节点。（注：头节点不是必要的，但是为了方便操作，我们加上了）

空队列时，front和rear都指向头节点。

创建一个队列

创建一个队列要完成两个任务：一是在内存中创建一个头节点，二是将队列的头指针和尾指针都指向这个生成的头节点，因为此时是空队列。

initQueue(LinkQueue *q){
    q->front = q->rear = (QueuePtr)malloc(sizeof(QNode));

    if(!q->front){
        exit(0);
    }
    q->front->next = NULL;
}

入队列操作

InsertQueue(LinkQueue *q,ElemType e){
    QueuePtr p;
    p = (QueuePtr)malloc(sizeof(QNode));
    if(p == NULL){
        exit(0);
    }

    p->data = e;
    p->next = NULL;
    q->rear->next = p;
    q->rear = p;
}

出对列操作

出队列擦欧总是将队列中的第一个元素移除，队头指针不发生改变，改变头节点的next指针即可。

如果元队列只有一个元素，那么我们就应该处理一下队尾指针。

DeletedQueue(LinkQueue *q,ElemType *e){
    QueuePtr p;
    if(q->front == q->rear){
        return;
    }

    p = q->front->next;
    *e = p->data;
    q->front->next = p->next;

    if(q->rear == p){
        q->rear = q->front;
    }
    free(p);
}

销毁一个队列

由于链队列建立在内存的动态区，因此当一个队列不再有用时应当把它及时销毁掉，以免过多的占用内存空间。

DestroyQueue(LinkQueue *q){
    while(q->front){
        q->rear = q->front->next;
        free(q->front);
        q->front = q->rear;
    }
}

六、队列的顺序存储结构

为什么说队列的实现上我们更愿意用链式存储结构来存储？

我们先按照应有的思路来考虑下如何构造队列的顺序存储结构，然后发掘都遇到了什么麻烦。

我们假设一个队列有n个元素，则顺序存储的队列需建立一个大于n的存储单元，并把队列的所有元素存储在数组的前n个单元，数组下标为0的一端则是队头

入队列操作其实就是在队尾追加一个元素，不需要任何移动，时间复杂度为O(1)。出队列则不同，因为我们已经假设下标为0的位置是队头，因此每次出队列操作的所有元素都要向前移动。

可是我们研究数据结构和算法的一个根本目的就是要想方设法提高我们的程序的效率，按刚才的方式，出队列的时间复杂度是O(n)，效率大打折扣！

循环队列

#define MAXSIZE 100
typedef struct{
    ElemType *base;//用于存放内存分配基地址
    int front;
    int rear;
}

初始化一个循环队列

initQueue(cycleQueue *q){
    q->base = (ElemType *)malloc(MAXSIZE*sizeof(ElemType));
    if(!q->base){
        exit(0);
    }

    q->front = q->rear = 0;
}

循环队列入队

InsertQueue(cycleQueue *q,ElemType e){
    if((q->rear+1)%MAXSIZE == q->front){
        return;//队列已满
    }
    q->base[q->rear] = e;
    q->rear = (q->rear+1) % MAXSIZE;
}

循环队列出队列

DeletedQueue(cycleQueue *q,ElemType *e){
    if(q->front == q->rear){
        return;//队列为空
    }

    *e = q->base[q->front];
    q->front = (1->front+1)%MAXSIZE;
}
⚠️ **GitHub.com Fallback** ⚠️