前言

进行栈和队列的学习。全篇使用C语言进行学习

栈

定义

栈是一种线性表，它只允许在数据的一段进行插入和删除的操作。
由于栈只能在一端进行插入和删除的操作，栈又被称为“后进先出”（Last In First Out）的线性表。LIFO结构

栈的“后进先出”的特性类似于铁路调度站，又类似于食堂里叠放的盘子，要想从一叠盘子里取出或放入一个盘子，只有在这一叠盘子的顶部操作才是最方便的

• 栈顶（Top）：线性表允许进行插入和删除的那一端
• 栈底（Bottom）：固定的不允许进行操作的一端
• 空栈：不含任何元素的线性表

一些基本操作

• InitStack(&S):初始化一个空栈S
• StackEmpty（S）：判断栈S是否为空，为空返回true，否则返回false
• Push（&S，x）：进栈，若栈S未满，将x加入使x成为新栈顶（栈的插入操作）
• Pop（&S，&x）：出栈，若栈S非空，弹出栈顶元素，并用x返回（栈的删除操作）
• GetTop（S，&x）：读取栈顶元素，若S非空，用x返回栈顶元素
• SetEmpty（S）：置空栈
• DestroyStack（&S）：销毁栈，释放栈S的存储空间

顺序结构存储

栈的顺序存储

采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的元素，附设一个指针top表示当前栈顶元素的位置
若栈的长度为StackSize则栈顶位置top必须小于StackSize
当栈中存在一个元素时，top等于0，因此空栈的判断条件为top等于-1
利用顺序存储方式存储的栈称为“顺序栈”。类似顺序表的定义，栈中的数据元素用一个预设的足够长的一维数组ElemType elem[MAXSIZE]来实现
栈底位置可以设置在数组的任何一个端点，栈顶是随着元素的插入和删除变化的。

栈的定义：

//定义栈中最大储存元素个数
#define MAXSIZE 50
//ElemType的类型定为int
typedef int ElemType;
typedef struct {
    ElemType elem[MAXSIZE];
    //栈顶指针
    int top;
}SeqStack;

通常我们把0下标端设为栈底，这样空栈时栈顶指针s->top = -1;
入栈时，s->top++;
出栈时，s->top–;

• 图中a为空栈
• b为元素A入栈后栈中元素和栈顶指针top的情况
• c为元素A、B、C、D、E依次入栈后的情况。
• d为依次让栈中的元素E、D出栈，此时栈中还有三个元素。或许最近出栈的元素E、D仍在原先位置存储，但是指针top已经指向了新的位置，可以表示E、D已经不在栈中了

//置空栈
SeqStack* InitStack(){
    SeqStack* s;
    s = (SeqStack*)malloc(sizeof(SeqStack));
    s->top = -1;
    return s;
}
//判空栈
int Empty(SeqStack* s){
    if (s->top == -1){
        return 1;
    } else{
        return 0;
    }
}
//入栈
int Push(SeqStack* s,ElemType x){
    if (s->top == MAXSIZE-1){
        return 0;
    } else{
        s->top++;
        s->elem[s->top] = x;
        return 1;
    }
    
}
//出栈
int Pop(SeqStack* s,ElemType x){
    if (Empty(s)){
        return 0;
    } else{
        *x = s->elem[s->top];
        s->top--;
        return 1;
    }
}
//取栈顶元素
ElemType GetTop(SeqStack*s){
    if (Empty(s)){
        return 0;
    } else{
        return (s->elem[s->top]);
    }
}

• 对于顺序栈，入栈时应先判断栈是否已满（s->top == MAXSIZE-1)，栈满时不能在入栈。否则出现空间溢出。这种现象称为“上溢”
• 出栈和读取栈顶元素时，先判断栈是否为空，为空时不能操作。栈空通常作为一种控制转移的条件。
• 取栈顶元素不改变指针top的指向位置，只是读出栈顶元素的值。而出栈需要改变指针top的指向

多栈共享邻接空间

有时候一个程序中要用到多个栈，若采用顺序栈，所需栈的空间大小难以估计，会出现有的栈空间溢出，有的是空栈的情况。为了不发生“上溢”错误，就必须给每个栈预先分配一块更大的空间，势必会造成储存空间紧张。
如果我们让多个栈共用一个足够大的连续处处可见，则可以利用栈的动态特性使其储存空间互补。

栈的共享中最常见的是两栈共享。假设两个栈共享一维数组elem[MAXSIZE]，则可以利用栈的“栈底位置不变，栈顶位置动态变化”特性。两个栈底分别为-1和MAXSIZE，栈顶分别向中间方向延伸。只要整个数组elem[MAXSIZE]未被占满，无论哪个栈的入栈都不会发生上溢。

//两栈共享空间
typedef struct{
    ElemType elem[MAXSIZE];
    //左栈栈顶指针
    int lefttop;
    //右栈栈顶指针
    int righttop;
} Dupsqstack;

左栈入栈时，栈顶指针加1，又栈 入栈时，栈顶指针减1
在进行栈操作时，需指定栈号是左栈还是右栈，并判断是否栈满。
栈满的判断条件：s->left top == s->righttop;

//初始化
int InitDupStack(Dupsqstack* s){
    if ((s = (Dupsqstack*)malloc(sizeof(dupsqstack))) == NULL){
        return FALSE;
    }
    s->lefttop = -1;
    s->righttop = MAXSIZE;
    return TRUE;
}
//入栈操作
int PushDupStack(Dupsqstack* s,char status){
    if (s->lefttop + 1 == s->righttop){
        return FALSE;
    }
    if (status == 'L'){
        s->elem[++s->lefttop] = x;
    }
    else if (status == 'R'){
        s->elem[--s->lefttop] = x;
    } else{
        return FALSE;
    }
    return TRUE;
}
//出栈操作
ElemType PopDupStack(Dupsqstack* s,char status){
    if (status == 'L'){
        if (s->lefttop<0){
            return NULL;
        }else{
            return (s->elem[s->lefttop--]);
        }
    }else if(status == 'R'){
        if (s->righttop>MAXSIZE-1){
            return NULL;
        }else{
            return (s->elem[s->righttop++]);
        }
    }else{
        return NULL;
    }
}

链式结构存储

在上面玩吗为了避免“上溢”现象，采用了多栈共享空间。但是更好的避免“上溢”的方法是使用链式存储结构，让多个栈共享所有可用存储空间。所以，栈也可以采用链式存储结构表示，这种结构的栈简称“链栈”。
在一个链栈中，栈底就是链表的最后一个结点，栈顶总是在链表的第一个结点。
新入栈的元素即为链表新的第一个结点，只要系统还有存储空间，就不会发生满栈。

在这个图中，采用带头结点的单链表实现栈，因为栈的插入和删除操作仅限制在表头位置进行，所以链表的表头指针top就作为栈顶指针，top始终指向当前栈顶元素前面的头结点，top->next = NULL；代表栈为空。

typedef struct Stacknode{
    DataType data;
    struct Stacknode* next;
} slStackType;
//入栈操作
int PushLstack(slStackType* top,DataType x){
    slStackType* p;
    if ((p = (slStackType*)malloc(sizeof(slStackType))) == NULL){
        return FALSE;
    }
    p->data = x;
    p->next = top->next;
    top->next = p;
    return TRUE;
}
//出栈操作
//从链栈top中删除栈顶元素
DataType PopLstack(slStackType* top){
    slStackType* p;
    DataType x;
    if (top->next == NULL){
        return ;
    }
    p = top->next;
    top->next = p->next;
    x = p->data;
    return x;
}

多个链栈的操作

在程序中同时使用两个以上的栈时，使用顺序栈共用邻接空间很不方便。单若用多个单链栈操作就极为方便。
可用将多个单链栈的栈顶指针放在一个一维数组中
设一维数组top[M]
slStacktype* top[M];
其中，top[0],top[1]…top[I],…,top[M-1]指向M个不同的链栈，分别是M个链栈的栈顶指针。这样只需要确定链栈号i，然后把以top[i]为栈顶指针进行操作

//入栈操作
//将元素x压入链栈top[i]
int PushDupls(slStackType* top[M],int i,DataType x){
    slStackType* p;
    if ((p = (slStackType*)malloc(sizeof(slStackType))) == NULL){
        return FALSE;
    }
    p->data = x;
    p->next = top[i]->next;
    top[i]->next = p;
    return TRUE;
}
//出栈操作
//从链栈top[i]中删除元素
DataType PopDupls(slStackType* top[M],int i){
    slStackType* p;
    DataType x;
    if (top[i]->next == NULL){
        return ;
    }
    p = top[i]->next;
    top[i]->next = p->next;
    x = p->next;
    free(p);
    return x;
}

在上边的两个算法中，当指定栈号i（0<=i<=M-1）时，只对第i个链栈操作

栈的应用

• 算数表达式求值
• 栈与递归（汉诺塔）
• 括号匹配
• 数制转换
• 行编辑程序