数据结构与算法06——栈

栈的结构

image.png

栈是限定仅在表尾进行插入和删除操作的线性表。把允许插入和删除的一端称为栈顶（top），另一端称为栈底，不含任何数据元素的栈为空栈。

栈是一个特殊的线性表，其栈元素具有线性关系，即前驱后继关系，仅可以在其表尾进行插入和删除操作，这里的表尾指的就是栈顶top，而不是栈底。

image.png

栈的插入操作，叫做进栈，也称压栈、入栈。
栈的删除操作，叫做出栈，也称弹栈。

栈的顺序存储结构实现
栈是线性表的特例，栈的顺序存储是线性表顺序存储的简化，简称为顺序栈。

• 栈的结构定义

typedef struct {
    SElemType data[MAXSIZE];
    int top;  // 用于栈顶指针
}SqStack;

• 初始化一个空栈

// 初始化:创建一个空栈
Status InitStack(SqStack *S){
    S->top = -1;
    return OK;
}

• 进栈

// 入栈
Status PushStack(SqStack *S,SElemType e){
    // 需要判断栈内是否还有空间
    if (S->top == MAXSIZE-1) {
        return ERROR;
    }
    S->top++;
    S->data[S->top] = e;
    
    return OK;
}

出栈

// 出栈
Status PopStack(SqStack *S,SElemType *e){
    if (S->top < 0) {
        return ERROR;
    }
    *e = S->data[S->top];
    S->top--;
    return OK;
}

置空

// 置空顺序栈
Status ClearStack(SqStack *S){
    S->top = -1;
    return OK;
}

获取栈的长度

// 获取长度
int GetStackLength(SqStack S){
    return S.top+1;
}

栈的链式存储结构实现

栈的链式存储结构，简称为链栈。对于链栈来说，基本不会存在，像顺序栈那样的，栈空间被占满的情况。

image.png

• 链栈的结构定义

typedef struct StackNode{
    SElemType data;
    struct StackNode *next;
}StackNode,*LinkStackNode;

typedef struct {
    LinkStackNode top; // 链栈栈顶指针
    int count;         // 链栈结点个数长度
}LinkStackList;

• 初始化链栈

// 初始化链式栈
Status InitStackList(LinkStackList *S){
    S->top = NULL;
    S->count = 0;
    return OK;
}

• 链栈进栈

// 链式入栈
Status PushStackList(LinkStackList *S,SElemType e){
    
    LinkStackNode temp = (LinkStackNode)malloc(sizeof(LinkStackNode));
    temp->data = e;        // 赋值
    temp->next = S->top;   // 要压入链表栈的栈顶位置，所以新进栈的结点next指向栈顶
    S->top = temp;         // 栈顶调整为新的结点
    S->count++;            // 栈长度加一

    return OK;
}

• 链式出栈

// 链式出栈
Status PopStackList(LinkStackList *S,SElemType *e){
    if (S->count==0) {
        return ERROR;
    }
    
    LinkStackNode temp = S->top;   // 拿到要删除的栈顶元素
    *e = temp->data;
    S->top = S->top->next;         // 调整栈顶元素为next下一个
    S->count--;
    free(temp);                    // 释放要删除的元素给内存
    return OK;
}

image.png

• 链栈的置空

// 链式栈置空
Status ClearStackList(LinkStackList *S){
    
    if (S->count == 0) {
        return ERROR;
    }
    
    LinkStackNode temp = S->top;
    while (temp) {
        LinkStackNode nextNode = temp->next;
        free(temp);    // 置空要把所有的元素都释放
        temp = nextNode;
    }
    S->count = 0;
    return OK;
}

顺序栈和链栈的对比

• 顺序栈和链栈在时间复杂度上都是O(1)
• 对于空间性能，顺序栈需要实现确定一个固定的长度，可能会存在内存浪费的问题，但顺序栈在存取时定位很方便（top加或者top减）。
• 链栈中每个元素都有指针域，增加了内存开销，但对于栈的长度无限制。
• 如果栈的使用过程中元素变化不可预料，有时很大有时很小，则最好使用链栈，反之变化在可控范围内，使用顺序栈更好。