限定性线性结构 - 栈小结

栈是一种运算受限的线性表。限定仅在表尾进行插入和删除操作。这一端被称为栈顶，相对的，把另一端称为栈底。

向栈插入新元素又称为压栈、入栈、进栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素。

向栈删除新元素又称为出栈、退栈。

代码仓库地址

栈的特性：后进先出 LIFO

借用栈特性”LIFO“的思想，能帮助我们去解决一些算法题，比如：括号匹配，去重字符串、每日气温等

栈模型：

顺序栈结构设计（C语言）：就是一种操作受限的顺序表。

typedef struct {
    ElemType data[MAXSIZE];
    int top;
}SeqStack;

链式栈结构设计（C语言）：就是一种操作受限的单向链表。

typedef struct StackNode{
    ElemType data;
    struct StackNode *next;
}StackNode;

typedef struct {
    StackNode *top;		/* 栈顶指针 */
    StackNode *bottom;	/* 栈底指针 */
    int length;		/* 栈大小 */
}StackLink;

顺序栈的基本操作（C语言）

1. 构建一个空的顺序栈

Status initStack(SeqStack *S) {
    S->top = -1;
    return OK;
}

2. 清空栈

Status clearStack(SeqStack *S) {
    S->top = -1;
    return OK;
}

3. 判断栈是否为空

Status isEmptyStack(SeqStack S) {
    if (S.top == -1) {
        return TRUE;
    }
    return FALSE;
}

4. 栈的长度

int lengthOfStack(SeqStack *S) {
    return S->top+1;
}

5. 获取栈顶元素

Status getTop(SeqStack S, ElemType *e) {
    if (S.top == -1) {
        return ERROR;
    }
    *e = S.data[S.top+1];
    return OK;
}

6. 压栈

Status pushStack(SeqStack *S, ElemType e) {
    if (S->top == MAXSIZE - 1) {
        return ERROR;
    }
    
    S->data[++S->top] = e;
    return OK;
}

7. 出栈

Status popStack(SeqStack *S, ElemType *e) {
    if (S->top == -1) {
        return ERROR;
    }
    
    *e = S->data[S->top--];
    return OK;
}

8. 遍历栈----自顶至底

void traverseStack(SeqStack S) {
    if (S.top == -1) {
        printf("空栈\n");
        return;
    }
    int count = S.top;
    while (count > -1) {
        printf("%d ", S.data[count]);
        count--;
    }
    printf("\n");
}

链式栈的基本操作（C语言）

1. 构建一个空的链式栈

Status initStack(StackLink *S) {
    
    S->top = NULL;
    S->bottom = NULL;
    S->top = 0;
    return OK;
}

2. 清空栈

Status clearStack(StackLink *S) {
     
    StackNode *p, *q;
    p = S->top;
    while (p) {
        q = p;
        p = p->next;
        free(q);
    }
    S->bottom = NULL;
    S->length = 0;
    return OK;
}

3. 判断栈是否为空

Status isEmptyStack(StackLink S) {
    if (S.length == 0) {
        return TRUE;
    }else return FALSE;
}

4. 栈的长度

int lengthOfStack(StackLink S) {
    return S.length;
}

5. 获取栈顶元素

Status getTop(StackLink S, ElemType *e) {
    if (S.length == 0) {
        return ERROR;
    }
    
    *e = S.top->data;
    return OK;
}

6. 压栈

Status pushStack(StackLink *S, ElemType e) {
    StackNode *temp = malloc(sizeof(StackNode));
    if (temp == NULL) {
        return ERROR;
    }
    temp->data = e;
    temp->next = S->top;


    if (S->length == 0) {
        S->top = S->bottom = temp;
    }else {
        S->top = temp;
    }
    
    S->length++;
    
    return OK;
}

7. 出栈

Status popStack(StackLink *S, ElemType *e) {
    
    if (S->length == 0) {
        printf("空栈，无法出栈\n");
        return ERROR;
    }
    
    if (S->top == S->bottom) {
        // 最后一个元素
        *e = S->top->data;
        free(S->top);
        S->top = S->bottom = NULL;
    }else {
        *e = S->top->data;
        StackNode *popNode = S->top;
        S->top = popNode->next;
        free(popNode);
    }
    
    S->length--;
    return OK;
}

8. 遍历栈----自顶至底

void traverseStack(StackLink S) {
    StackNode *p;
    p = S.top;
    
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

总结

顺序栈和链式栈在时间复杂度均为O(1)
在初始时，空间上比较：
- 顺序栈必须确定一个专固定的长度，所以有存储元素个数的限制和空间浪费的问题
- 链栈无栈满问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构属性开销

一般结论：当栈在使用过程中元素个数变化较大时，用链栈比较好，反之，应该采用顺序栈。