Skip to content

3-栈

栈是一种只允许在一端进行插入和删除操作的操作受限的线性表。

栈的主要特点是 先进后出 (FILO),就像子弹夹一样,最先压进去的子弹最后打出来。

栈有一个指针,永远指向栈的最顶部,称作 栈顶指针

栈的另外一个概念是 栈底指针,在顺序栈中可不实现,在链栈中必须实现。

对于栈的操作有插入和删除,也称作 入栈出栈,不能从中间取出,因为只有一个口。

  • 顺序栈:栈的每一个元素存储在一段连续的内存空间,用数组实现。

  • 链栈:栈的每一个元素不一定紧挨着,用链表实现。

栈的主要操作包括:创建、初始化、入栈、出栈、判空、判满、获取栈顶元素、清空栈

栈的应用非常广,例如函数调用就是用栈实现的。栈这种前进后出的特点非常适合解决匹配问题。

顺序栈

定义

#ifndef DATAELEMENT_H_INCLUDED
#define DATAELEMENT_H_INCLUDED
#define MAX_SIZE 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Bool;
typedef int Status;

/** 数据元素 */
typedef struct {
    int id;
    char* name;
} Element;


/** 栈 */
typedef struct {
    Element datas[MAX_SIZE];
    int top;    // 栈顶指针
} Stack;


#endif // DATAELEMENT_H_INCLUDED

创建

Status Create(Stack *s) {
    s->top = -1;
    return OK;
}

栈空条件有两种:s->top == -1s->top == 0

这里采用 -1 这种,原因是不需要浪费一个元素大小的空间,另外操作起来也方便,因为数组下标是从0开始的。

初始化

Status Init(Stack* s, Element* datas, int length) {
    if (length > MAX_SIZE)
        return ERROR;
    if (s->top != -1)
        Create(s);

    for (int i = 0; i < length; i++)
        push(s, datas[i]);

    return OK;
}

入栈

Status push(Stack* s, Element e) {
    if (s->top >= MAX_SIZE - 1)
        return ERROR;

    s->datas[++s->top] = e;
    return OK;
}

我们采用的是第一种栈空表示方式,栈顶指针永远指向栈顶元素,所以在将元素赋值压入栈之前,要先把栈顶指针抬起来 1 格,然后再把元素放进去。

s->datas[++s->top] = e 等价于

s->top++;
s->datas[s->top] = e

出栈

Element pop(Stack* s) {
    return s->datas[s->top--];
}

出栈的道理相同,先把元素取出来,然后栈顶指针降下去1格。

s->datas[s->top--] 等价于

s->datas[s->top]; 
s->top--;

获取栈顶元素

获取栈顶元素不会出栈,就像把弹夹取下来看一眼,并不是打出去。

Element get(Stack* s) {
    return s->datas[s->top];
}

判空

我们采用的是第一种栈空表示方式,所以只要判断栈顶指针是不是 s->top == -1 21即可。

Bool isEmpty(Stack* s) {
    return s->top == -1;
}

判满

Bool isFull(Stack* s) {
    return s->top == MAX_SIZE - 1 ? TRUE : FALSE;
}

清空栈

Status Clean(Stack* s) {
    s->top = -1;
    return OK;
}

顺序栈的清空很简单,只需要把栈顶指针指向栈底即可,虽然原本的数据没有被销毁,但是后续push的数据会将其覆盖。即使没有覆盖,在栈中我们只需要关注栈顶指针 top 的指向即可,top 所指即为栈顶,不论 top 之上有没有数据。

至于销毁栈,需要在定义 Stack s 的地方 free(s)

打印栈

void Show(Stack* s) {
    for (int i = 0; i <= s->top; i++)
        printf("%d \t %s \n", s->datas[i].id, s->datas[i].name);
}

测试数据

#include "SqStack.c"

Element datas[] = {
    { 1, "Iron Man" },
    { 2, "Green Man" },
    { 3, "Thor" },
    { 4, "Doctor" }
};

int main()
{
    Stack s;
    Create(&s);
    Init(&s, datas, sizeof datas / sizeof datas[0]);
    Show(&s);

    printf("\n----------------------------------\n");

    Element e = { 5, "Big Man" };
    push(&s, e);
    Show(&s);

    printf("\n----------------------------------\n");

    Element pe = pop(&s);
    pop(&s);
    Show(&s);

    return 0;
}

// ---------------------------------------------------
// Output:
1    Iron Man 
2    Green Man 
3    Thor 
4    Doctor 

----------------------------------
1    Iron Man 
2    Green Man 
3    Thor 
4    Doctor 
5    Big Man 

----------------------------------
1    Iron Man 
2    Green Man 
3    Thor 

链栈

定义

#ifndef DATAELEMENT_H_INCLUDED
#define DATAELEMENT_H_INCLUDED
#define MAX_SIZE 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int Bool;

/** 数据元素 */
typedef struct {
    int id;
    char* name;
} Element;


/** 链栈结点 */
typedef struct Node {
    Element data;
    struct Node* next;
} Node;


/** 链栈 */
typedef struct {
    Node* next;
    int top;
} LStack;

#endif // DATAELEMENT_H_INCLUDED

链栈稍微比顺序栈复杂一点点,但是换来不限栈大小的好处,所以在链栈中没有栈满的概念。

同时,链栈在入栈的时候需要手动分配空间,在出栈的时候需要把结点中的数据保存起来,销毁结点,再把数据返回。

创建

Status Create(LStack* s) {
    s->next = NULL;
    s->top = -1;
    return OK;
}

初始化

Status Init(LStack* s, Element* datas, int length) {
    if (s->top != -1)
        Create(s);

    for (int i = 0; i < length; i++) 
        push(s, datas[i]);

    return OK;
}

入栈

Status push(LStack* s, Element e) {
    // 建立新结点,分配空间
    Node* new = (Node*)malloc(sizeof(Node));
    // 判断分配空间是否成功
    if (!new)
        return ERROR;
    new->data = e;

    // 插入到链表的首元结点,成为栈顶元素
    new->next = s->next;
    s->next = new;
    s->top++;
}

这里的入栈使用的是头插法,即每个新插入的元素都会插在链表的首元结点的位置。

出栈

Element pop(LStack* s) {
    Element res;
    if (isEmpty(s)) {
        return res;
    }
    Element res = s->next->data;    // 将栈顶元素的数据复制一份
    // 改链,原本指向栈顶元素,现在指向栈顶的下一个元素,使其成为新的栈顶
    Node* p = s->next;
    s->next = p->next;
    // 将旧的栈顶元素释放空间
    free(p);
    s->top--;

    return res;
}

链栈的出栈操作要记得把被弹出栈的旧栈顶元素释放。

获取栈顶元素

Element get(LStack* s) {
    return s->next->data;
}

判空

Bool isEmpty(LStack* s) {
    return s->top == -1;
}

清空栈

Status Clean(LStack* s)
{
    if (s->top == -1) {
        return OK;
    }

    Node* deleted = s->next;
    Node* p;
    while (deleted) {
        p = deleted->next;
        free(deleted);
        deleted = p;
    }

    // s->next = NULL;
    // s->top = -1;
    Create(s);
    return OK;
}

清空链栈和销毁链表的操作是相同的,需要定义两个结点指针,相互配合实现整表销毁。

最后将栈置空,栈顶指针恢复到初试状态,所以这里调用了 Create(),等价于其上面两句表达式。

打印链栈

void Show(LStack* s) {
    if (s->top == -1) {
        printf("Stack is EMPTY!");
        return;
    }

    Node* p = s->next;
    for (int i = s->top; i > -1; i--) {
        printf("%d \t %s \n", p->data.id, p->data.name);
        p = p->next;
    }
}

测试数据

#include "LinkStack.c"

Element datas[] = {
    { 1, "Iron Man" },
    { 2, "Green Man" },
    { 3, "Thor" },
    { 4, "Doctor" }
};

int main()
{
    LStack s;
    Init(&s, datas, 4);
    Show(&s);

    printf("\n----------------------------------\n");

    Element e = { 5, "Big Man" };
    push(&s, e);
    Show(&s);

    printf("\n----------------------------------\n");

    Element pe = pop(&s);
    pop(&s);
    Show(&s);

    printf("\n----------------------------------\n");

    Clean(&s);
    Show(&s);


    return 0;
}

// ---------------------------------------------------
// Output:
4    Doctor 
3    Thor 
2    Green Man 
1    Iron Man 

----------------------------------
5    Big Man 
4    Doctor 
3    Thor 
2    Green Man 
1    Iron Man 

----------------------------------
3    Thor 
2    Green Man 
1    Iron Man 

----------------------------------
Stack is EMPTY!

共享栈

共享栈:指的是两个栈共用一个内存空间的一种栈结构。

共享栈不需要用链式结构,因为共享栈为的是 节省空间,用链式没有意义。

两个栈的栈底固定不变,讲两个栈顶设置在数组的两端,即 左边的栈 s0 的栈底设在 0 处,右边的栈 s1 的栈底设在 MAX_SIZE - 1 处。

创建共享栈时,左栈的栈顶指针 topL = -1,右栈的栈顶指针 topR = MAX_SIZE,当两个栈顶相遇时栈满,这样可以尽可能地利用空间。

栈空
栈空 (topL == -1 && topR == MAX_SIZE)

栈满
栈满 (topL == topR - 1)

普通状态
普通状态

定义

共享栈的定义稍稍不同。

#ifndef DATAELEMENT_H_INCLUDED
#define DATAELEMENT_H_INCLUDED
#define MAX_SIZE 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define LEFT 1    // 和顺序栈的定义相比多一个 LEFT 和 RIGHT 来标记方向
#define RIGHT 999

typedef int Bool;
typedef int Status;

typedef struct {
    int id;
    char* name;
} Element;

typedef struct {
    Element datas[MAX_SIZE];    // 栈的存储空间,用数组来存储
    int topL;    // 左栈的栈顶指针
    int topR;    // 右栈的栈顶指针
} ShareStack;

#endif // DATAELEMENT_H_INCLUDED

创建

Status Create(ShareStack* s)
{
    s->topL = -1;
    s->topR = MAX_SIZE;
    return OK;
}
创建时,将两个指针初始化

初始化

Status Init(ShareStack* s, Element* datas, int length, int direction)
{
    if (length > MAX_SIZE) {
        return ERROR;
    }

    if (direction == LEFT && !isEmptyL(s)) {
        s->topL == -1;
    }
    if (direction == RIGHT && !isEmptyR(s)) {
        s->topR = MAX_SIZE;
    }

    for (int i = 0; i < length; i++) {
        push(s, datas[i], direction);
    }
    return OK;
}

共享栈需要多一个参数 direction,来指定将元素放入左栈还是右栈。

入栈

Status push(ShareStack* s, Element e, int direction)
{
    if (isFull(s)) {
        return ERROR;
    }

    switch (direction) {
    case LEFT:
        s->datas[++s->topL] = e;
        return OK;

    case RIGHT:
        s->datas[--s->topR] = e;
        return OK;

    default:
        printf("Direction is ILLEGAL PARAMETER!");
        return ERROR;
    }
}

出栈

Element pop(ShareStack* s, int direction)
{
    Element e;
    switch (direction) {
    case LEFT:
        if (isEmptyL(s)) {
            return e;
        }
        e = s->datas[s->topL--];
        return e;

    case RIGHT:
        if (isEmptyR(s)) {
            return e;
        }
        e = s->datas[s->topR--];
        return e;

    default:
        printf("Direction is ILLEGAL PARAMETER!");
        break;
    }
}

获取栈顶元素

Element get(ShareStack* s, int direction)
{
    return s->datas[direction == LEFT ? s->topL : s->topR];
}

判空

Bool isEmpty(ShareStack* s)
{
    return s->topL == -1 && s->topR == MAX_SIZE;
}

Bool isEmptyL(ShareStack* s)
{
    return s->topL == -1;
}

Bool isEmptyR(ShareStack* s)
{
    return s->topR == MAX_SIZE;
}

判满

Bool isFull(ShareStack* s)
{
    return s->topL == s->topR - 1;
}

清空栈

Status Clean(ShareStack* s, int direction)
{
    if (isEmpty(s)) {
        return OK;
    }

    switch (direction) {
    case LEFT:
        s->topL = -1;
        break;

    case RIGHT:
        s->topR = MAX_SIZE;
        break;

    default:
        return ERROR;
    }
    return OK;
}

打印栈

void Show(ShareStack* s, int direction)
{
    if (isEmpty(s)) {
        printf("The Whole Share stack is EMPTY!\n");
    }

    switch (direction) {
    // 打印左栈
    case LEFT:
        if (isEmptyL(s)) {
            printf("The Left Share stack is EMPTY!\n");
            return;
        }

        for (int i = 0, j = 1; i <= s->topL; i++, j++) {
            printf("No. %d is: %d \t %s \n", j, s->datas[i].id, s->datas[i].name);
        }
        break;
    // 打印右栈
    case RIGHT:
        if (isEmptyR(s)) {
            printf("The Right Share stack is EMPTY!\n");
            return;
        }
        for (int i = s->topR, j = 1; i < MAX_SIZE; i++, j++) {
            printf("No. %d is: %d \t %s \n", j, s->datas[i].id, s->datas[i].name);
        }
        break;
    // 如果传进来的不是 LEFT 也不是 RIGHT,则打印整个栈
    default:
        for (int i = 0; i < MAX_SIZE; i++) {
            if (i > s->topL && i < s->topR) {    // 超过左栈没到右栈的这段空白
                printf("No. %d is EMPTY.\n", i + 1);
            } else {
                printf("No. %d is: %d \t %s \n", i + 1, s->datas[i].id, s->datas[i].name);
            }
        }
        break;
    }
}

测试数据

#include "ShareStack.c"
#define len(X) sizeof(X) / sizeof(X[0])

Element datas1[] = {
    { 1, "Iron Man" },
    { 2, "Green Man" },
    { 3, "Thor" },
    { 4, "Doctor" }
};

Element datas2[] = {
    { 12, "Spider Man" },
    { 24, "Wonder Woman" },
    { 35, "Bat Man" },
    { 40, "Super Man" }
};

int main()
{
    ShareStack ss;
    Create(&ss);
    Init(&ss, datas2, len(datas2), RIGHT);
    Show(&ss, RIGHT);

    printf("\n----------------------------------\n");

    Init(&ss, datas1, len(datas1), LEFT);
    Show(&ss, LEFT);

    printf("\n----------------------------------\n");

    Show(&ss, 10);
    return 0;
}

// ---------------------------------------------------
// Output:
No. 1 is: 40     Super Man 
No. 2 is: 35     Bat Man 
No. 3 is: 24     Wonder Woman 
No. 4 is: 12     Spider Man 

----------------------------------
No. 1 is: 1      Iron Man 
No. 2 is: 2      Green Man 
No. 3 is: 3      Thor 
No. 4 is: 4      Doctor 

----------------------------------
No. 1 is: 1      Iron Man 
No. 2 is: 2      Green Man 
No. 3 is: 3      Thor 
No. 4 is: 4      Doctor 
No. 5 is EMPTY.
No. 6 is EMPTY.
No. 7 is: 40     Super Man 
No. 8 is: 35     Bat Man 
No. 9 is: 24     Wonder Woman 
No. 10 is: 12    Spider Man