五、栈和队列(一)、栈

2020-05-26 本文已影响0人默默_David

数据结构目录

1.定义

栈(stack)是一个后进先出(Last in first out,LIFO)的线性表，它要求只在表尾进行删除和插入操作。
栈在操作上有一些特殊的要求和限制:

栈的元素必须后进先出
栈的操作只能在这个线性表的表尾进行
对于栈来说，这个表尾成为栈的栈定(top),相应的表头称为栈底(bottom)

2.栈的插入和删除操作

栈的插入操作(push)，叫做进栈，也成为压栈，入栈。
栈的删除操作(pop),叫做出栈，也称为弹栈。

3. 栈的顺序存储结构

因为栈的本质是一个线性表，线性表有两种存储形式，那么栈也有分为栈的顺序存储结构和栈的链式存储结构
最开始栈中不含有任何数据，叫做空栈，此时栈顶就是栈底。然后数据从栈顶进入，栈顶栈底分离，整个栈的当前容量变大。数据出栈时从栈顶弹出，栈顶下移，整个栈的当前容量变小。

栈的顺序存储结构

(1)栈的结构定义

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct SqStack{
    ElemType *base;//栈底
    ElemType *top;//栈顶
    int stackSize;
}SqStack;

(2)初始化一个空栈

Status initStack(SqStack *s){
    s->base = (ElemType *)malloc(sizeof(ElemType) * STACK_INIT_SIZE);
    if (!(s->base)) {
        return ERROR;
    }
    s->top = s->base;//最开始，栈顶就是栈底，代表它是一个空栈
    s->stackSize = STACK_INIT_SIZE;
    return OK;
}

(3)入栈操作

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

Status Push(SqStack *s,ElemType e){
    //如果空间不够，要动态追加空间
    if (s->top - s->base >= s->stackSize) {
        s->base = (ElemType *)realloc(s->base, sizeof(ElemType)*(s->stackSize + STACKINCREMENT));
        if (!s->base) {
            return ERROR;
        }
        s->top = s->base + s->stackSize;
        s->stackSize = s->stackSize + STACKINCREMENT;
    }
    //压入值
    *(s->top) = e;
    //移动栈顶指针
    s->top++;
    return OK;
}

(4)出栈操作

出栈操作就是在栈顶取出数据，栈顶指针随之下移的操作。
每当从栈内弹出一个数据，栈的当前容量就-1

Status Pop(SqStack *s,ElemType *e){
    if (s->base == s->top) {
        //空栈直接返回
        return ERROR;
    }
    //先栈顶下移一位后再取值才是正确的
    *e = *(--s->top);
    return OK;
}

(5)清空一个栈

所谓清空一个栈，就是将栈中的元素全部作废，但栈本身物理空间并不发生改变（不是销毁）。
因此我们只要将s->top的内容赋值为s->base即可，这样s->base等于s->top，也就表明这个栈是空的了。这个原理跟高级格式化只是但单纯地清空文件列表而没有覆盖硬盘的原理是一样的。

void clearStack(SqStack *s){
    s->top = s->base;
}

(6)销毁一个栈

销毁一个栈与清空一个栈不同，销毁一个栈是要释放掉该栈所占据的物理内存空间

void DestroyStack(SqStack *s){
    int length = s->stackSize;
    for (int i = 0; i < length; i++) {
        //循环将所有内存都释放
        free(s->base++);
    }
    //将指针都置为空
    s->base = s->top = NULL;
    s->stackSize = 0;
}

(7)计算一个栈的当前容量

计算栈的当前容量也就是计算栈中元素的个数，因此只要返回s.top-s.base即可。
注意，栈的最大容量是指该栈占据内存空间的大小，其值是s.stackSize，它与栈的当前容量不是一个概念哦。

int stackLenth(SqStack s){
    //同类型指针的相加减就是它们之间所隔的此类元素的个数
    return (int)(s.top - s.base);
}

4.栈的链式存储结构

通常我们用的都是栈的顺序存储结构存储，链式存储结构只作为一个知识点，有所了解就好。
栈的链式存储结构，简称栈链。
栈因为只是栈顶来做插入和删除操作，所以比较好的方法就是将栈顶放在单链表的头部，栈顶指针和单链表的头指针合二为一。

栈的链式存储结构

(1)定义

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

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

(2)进栈操作

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

Status Push(LinkStack *s,ElemType e){
    LinkStackPtr p = (LinkStackPtr)malloc(sizeof(StackNode));
    if (!p) {
        return ERROR;
    }
    p->data = e;
    p->next = s->top;
    s->top = p;
    s->count++;
    
    return OK;
}

(3)出栈操作

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

Status Pop(LinkStack *s,ElemType *e){
    if (s->count == 0 ) {
        return ERROR;
    }
    LinkStackPtr p = s->top;
    *e = p->data;
    s->top = p->next;
    free(p);
    s->count--;
    return OK;
}