数据结构笔记 4. 栈

1、 栈的定义：

栈（stack）是限定仅在表尾进行插入和删除操作的线性表。

我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。

栈又称为后进先出（Last In First Out)的线性表，简称LIFO结构。

栈的插入操作，叫进栈，也称压栈、入栈

栈的删除操作，叫出栈，也叫弹栈。

2. 栈的抽象数据类型

ADT 栈(stack)
Data
    同线性表。 元素具有相同的类型，相邻元素具有前驱和后继关系
Operation
    InitStack(*S); 初始化操作，建立一个空栈S
    DestroyStack(*S); 若栈存在，则销毁它。
    ClearStack(*S):将栈清空 
    StackEmpty(S) 若栈为空，返回true,否则返回false
    GetTop(S, *e)；若栈存在且非空，用e返回S的栈顶元素
    Push(*S, e);若栈S存在，插入新元素e到栈S中并成为栈顶元素
    Pop(*S,*e) 删除栈S中栈顶元素，并用e返回其值
    StackLength(S) 返回栈S的元素个数
endADT

3. 栈的顺序存储结构定义

typedef int SElemType; /*SElemType类型根据实际情况而定，这里假设为int*/
typedef struct {
    SElemType data[MAXSIZE];
    int top;  //用于栈顶指针
}SqStack;

若现在有一个栈，StackSize是5，则栈普通情况、空栈和栈满如下图

3.1 进栈操作

//插入元素e为新的栈顶元素
Status Push(SqStack *S, SELemType e) {
    if (S->top == MAXSIZE-1) {    //栈满
        return ERROR;
    }
    S->top++;      //格顶指针增加1
    S->data[S->top] = e;   //将新插元素赋值给栈顶空间
    return OK;
}

3.2 出栈操作

//若栈不空，则删除S的栈顶元素， 用e返回其值，并返回OK， 否则返回ERROR
Status Pop(SqStack *S, SELemType *e) 
{
    if (S->top == -1) {
        return ERROR;
    }
    *e = S->data[S->top];   //将要删除的栈顶元素赋给e
    S->top--;
    return OK;
}

进栈和出栈操作，没有循环语句，时间复杂度均是O(1)。

3.3 . 两栈共享空间

数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈底为数组的末端，即下标为数组长度n-1处。这样两个栈如果增加元素，就是两端点向点间延伸。

关键思路：它们是在数组的两端，向中间靠拢。 top1和top2是栈1和栈2的栈顶指针，可以想象，只要它们俩不见面，两个栈就可以一直使用。

栈1空： top1=-1

栈2空：top2 = n

极端情况：若栈2是空栈，栈1的top1等于n-1时，就是栈1满了。反之，当栈1为空栈时，top2等于0时，为栈2满。

一般情况：两个栈见面时，即top1+1 == top2为栈满。

//两栈共享空间结构
typedef struct
{
    SELemType data[MAXSIZE];
    int top1;   //栈1栈顶指针
    int top2;   //栈2栈顶指针
}SqDoubleStack;

/*
push压栈
1. 判断插入元素
2. 判断栈1还是栈2的栈号参数stackNumber
*/
Status Push(SqDoubleStack *S, SELemType e, int stackNumber)
{
    if (S->top1+1 == S->top2) { // 栈满，不能再push新元素了
        return ERROR;
    }
    if (stackNumber == 1){  //栈1有元素进栈
         S->data[++S->top1] = e; //先top1+1后给数组元素赋值
    } else if (stackNumber == 2) {
         S->data[--S->top2] = e;
    }
    return OK;
}

//只判断栈1栈2的参数stackNumber
Status Pop(SqDoubleStack *S, SELemType *e, int stackNumber) {
     if (stackNumber == 1) {
        if(S->top1 == -1) {
            return ERROR;   //说明栈1已经是空栈，溢出
        }
        *e = S->data[S->top1--]; //将栈1的栈顶元素出栈
     } else if (stackNumber == 2) {
        if (S->top2 == MAXSIZE) {
             return ERROR;
        }
        *e = S->data[S->top2++];
     }
     return OK;
}

使用这样的数据结构，通常都是当两个栈的空间需求有相反关系时，也就是一个栈增长时另一个栈在缩短的情况。就像买卖股票一样，你买入时，一定有人在做卖出操作。

4. 栈的链式存储结构

栈的链式存储结构，简称链栈

不存在栈满

空栈：top=NULL

//链栈结构定义
typedef struct StackNode 
{
    SElemType data;
    struct StackNode *next;
}StackNode, *LinkStackPtr;

typedef struct LinkStack
{
    LinkStackPtr top;
    int count;
}LinkStack;

4.1 进栈操作

Status Push(LinkStack *S, SElemType e)
{
    LinkStackPtr s = (LinkStackPtr) malloc(sizeof(StackNode));
    S->data = e;
    S->next = S->top; //把当前的栈顶元素赋值给新结点的直接后继
    S->top = s;  //将新的结点s赋栈顶指针
    S->count++;
    return OK;
}

4.2 出栈操作

//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK,否则ERROR
Status Pop(LinkStack *S, SElemType *e)
{
    LinkStackPtr p;
    if (StackEmpty(*S))
         return ERROR;
    *e = S->top->data;
    p = S->top;   //将栈顶结点赋值给p
    S->top = S->top->next;   //使栈顶指针下移一位，指向后一结点。
    free(p);
    S->count--;
    return OK;
}

进栈出栈操作时间复杂度均为O(1).

如果栈的使用过程中元素变化不可预料,有时很小,有时非常大,那么最好是用链栈,反之,如果它的变化在可控范围内,建议使用顺序栈会更好一些.

5. 栈的作用

5.1 递归

我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数,称递归函数.

每个递归定义必须至少有一个条件,满足时递归不再进行,即不再引用自身而是返回值退出.

5.2 斐波那契数列实现

举例: 新出生的一对小兔子分析: 第一个月小兔子没有繁殖能力,所以还是一对; 两个月后生下一对小兔子共有两对;…

表中数字1, 1, 2, 3, 5, 8, 13—-构成一个序列.即斐波那契数列

//打印前40位斐波那契数列
int main() 
{
    int i;
    int a[40];
    a[0] = 0;
    a[1] = 1;
    printf("%d ", a[0]);
    printf("%d ", a[1]);
    for (i = 2; i<40; i++ {
        a[i] = a[i-1] + a[i-2];
        printf("%d ", a[i]);
    }
    return 0;
}

//递归实现
int Fbi(int i) {
    if (i<2) {
        return i ==0 ? 0 : 1;
    }
    return Fbi(i-1) + Fbi(i-2);
}
int main() {
    int i;
    for(int i=0; i<40; i++) {
         printf("%d ", Fbi(i));
   }
   return 0;
}

这里的递归实现不如循环实现, 斐波那契实现时间复杂度O(2^n), 第一种的时间复杂度为O(n)