数据结构与算法(五) -- 栈

Glen_
492 阅读5分钟

一、栈的定义

栈是一种数据结构, 它遵循着一个规则, 就是先进后出. 好比往盒子里放东西, 最先放入的只能最后拿出来. 由于这种特性, 我们也会经常看到这种结构. 例如 浏览器的返回前进等.

二、顺序栈与链式栈

顺序栈:

顺序栈与int[]类似, 它存储数据的形式是在一个固定的空间里进行存储.

链式栈:

顺序栈与int *类似, 它存储的一个数据是放在一个指针空间里, 然后在用链表的形式去扩充这个数据空间.

2.1、顺序栈

首先我们来创建一个顺序栈. 因为顺序栈的存储是连续的. 所以可以用一个数组去存储.

typedef int Status;
typedef int StackData;

#define OK 1
#define ERROR 0

#define TRUE 1
#define FALSE 0

#define STACKSIZE 20//栈容量大小

//顺序存储栈
typedef struct {
    StackData data[STACKSIZE];//数据域
    int top;//栈顶的位置
} SeqStack;

2.1.1、顺序栈的初始化

因为在栈里, 我们进行操作只能对栈顶进行, 所以我们无需管理栈的其他空间的数据. 直接将栈顶标记记为-1.

//创建一个栈
Status CreateStack(SeqStack *s) {
    if (s == NULL) {
        return ERROR;
    }
    s->top = -1;
    return OK;
}

2.1.2、顺序栈的清空

同初始化一样, 对一个栈的清空也是无需管理这片空间是否存什么东西, 只需要管理栈顶标记

//清空栈
Status ClearStack(SeqStack *s) {
    if (s == NULL) {
        return ERROR;
    }
    s->top = -1;
    return OK;
}

2.1.3、顺序栈的空判断与长度

要知道一个栈是否为空和长度, 实际上我们通过栈顶标记就可以知道

//判断栈是否为空
Status IsEmptyStack(SeqStack s) {
    return s.top == -1 ? TRUE : FALSE;
}

//返回栈的长度
void StackLength(SeqStack s, int *L) {
    if (L != NULL) {
        (*L) = s.top + 1;
    }
}

2.1.4、顺序栈的栈顶元素获取

栈的栈顶标记就是获取栈顶元素用的

//获取栈顶元素
Status GetTopElement(SeqStack s, StackData *L) {
    if (s.top == -1 || L == NULL) {
        return ERROR;
    }
    (*L) = s.data[s.top];//通过栈顶标记去数组中取值
    return OK;
}

2.1.5、顺序栈的压栈

顾名思义, 压栈就是对一个栈向里面存放数据. 因为栈对特性, 新对数据只能存放在最上面. 也就是当前对栈顶标记读取到的元素就是新元素

//压栈
Status PushStackData(SeqStack *s, StackData L) {
    if (s == NULL || s->top == STACKSIZE - 1) {
        return ERROR;
    }
    s->top++;//栈顶位置的下一个即为新栈顶
    s->data[s->top] = L;
    return OK;
}

2.1.6、顺序栈的出栈

出栈是指将栈顶元素从栈中‘去掉’, 此时因为数据空间是固定的, 无需管理空间值.

//出栈
Status PopStackData(SeqStack *s, StackData *L) {
    if (s == NULL || s->top == - 1) {
        return ERROR;
    }
    if (L != NULL) {
        *L = s->data[s->top];//读取到当前栈顶元素
    }
    s->top--;//栈顶标记-1
    return OK;
}

2.1.7、顺序栈的遍历

顺序栈遍历直接去空间域遍历至栈顶即可

//遍历栈元素
Status StackTraversal(SeqStack s) {
    if (s.top == -1) {
        return ERROR;
    }
    for (int i = 0; i <= s.top; i++) {
        printf("Stack [%d] : %d\n", i, s.data[i]);
    }
    return OK;
}

2.2、链式栈

链式栈的数据域是一个链表的形式, 所以还要额外的去些一个链节点. 因为链式栈不可以通过栈顶标记去取值, 所以我们只能记录一下链式栈的长度

//链式存储栈
typedef struct StackNode {
    StackData data;
    struct StackNode *next;
} StackNode;

typedef struct {
    StackNode *topElement;
    int count;
} ListStack;

2.2.1、链式栈的创建

创建一个节点指针, 此时长度为0

//创建一个链式栈
Status CreateListStack(ListStack *s) {
    if (s == NULL) {
        return ERROR;
    }
    s->topElement = (StackNode *)malloc(sizeof(StackNode));
    if (!s) return ERROR;
    s->topElement = NULL;
    s->count = 0;
    return OK;
}

2.2.2、链式栈的清空

无需管理数据域. 长度设置为0即可

//清空链栈
Status ClearListStack(ListStack *s) {
    if (s == NULL) {
        return ERROR;
    }
    s->count = 0;
    return OK;
}

2.2.3、链式栈的空判断与长度

这里理解应该比顺序栈更为直接, 因为直接定义来一个长度

//判断链栈是否为空
Status IsEmptyListStack(ListStack s) {
    return s.count == 0 ? TRUE : FALSE;
}

//返回链栈的长度
void StackListLength(ListStack s, int *L) {
    if (L != NULL) {
        (*L) = s.count;
    }
}

2.1.4、链式栈的栈顶元素获取

在链式栈中, 我们记录的数据域最好是以栈顶为起始, 因为栈的操作是从栈顶开始的, 方便数据的读取存放

//获取链栈顶元素
Status GetTopElementForListStack(ListStack s, StackData *L) {
    if (s.count == -1 || L == NULL) {
        return ERROR;
    }
    *L = s.topElement->data;
    return OK;
}

2.1.5、链式栈的压栈

在链表中, 我们会通常的习惯采用尾插法来进行链表的增加. 但是在链式栈中, 首先操作的永远是栈顶, 如果采用尾插法, 我们每次都要去链表的最后面去读取到栈顶元素, 造成极大的不便, 所以这里采用头插法比较适合.

//压栈(链栈)
Status PushListStackData(ListStack *s, StackData L) {
    if (s == NULL || s->count == STACKSIZE - 1) {
        return ERROR;
    }
    StackNode *temp = (StackNode *)malloc(sizeof(StackNode));//生成一个节点
    temp->data = L;
    temp->next = s->topElement;//节点的下一个即为目前的栈顶
    s->topElement = temp;//将新节点设置为栈顶
    s->count++;
    return OK;
}

2.1.6、链式栈的出栈

由于采用头插法来设计链式栈, 所以出栈也会变的简易了许多, 直接将栈顶元素移除

//出栈(链栈)
Status PopListStackData(ListStack *s, StackData *L) {
    if (s == NULL || s->count == - 1) {
        return ERROR;
    }
    if (L != NULL) {
        StackNode *temp = s->topElement;//拿到当前栈顶
        s->topElement = temp->next;//将栈顶设置为第二个元素
        *L = temp->data;
        free(temp);//释放旧栈顶元素
        s->count--;
    }
    return OK;
}

2.1.7、链式栈的遍历

同链表遍历一样, 依次读取节点数据

//遍历链栈元素
Status ListStackTraversal(ListStack s) {
    if (s.count == -1) {
        return ERROR;
    }
    StackNode *temp = s.topElement;
    for (int i = 0; i <= s.count; i++) {
        printf("Stack [%d] : %d\n", i, temp->data);
        temp = temp->next;
    }
    return OK;
}
avatar
文章
阅读
粉丝