数据结构与算法 - 栈

我们都知道函数都是存放在栈上,由系统帮我们管理,那么栈到底是一种什么样的数据结构呢?它是如何管理数据的? 日常开发中我们或许并没有直接的用上栈这种数据结构,但是它却能帮我们解决一些很棘手的问题,这篇文章主要分享一下个人对栈的理解以及如何用 c去实现一个栈的结构。本文涉及的代码可以前往 示例代码 处查看。

栈结构

栈结构就像一个桶一样,我们可以往桶里边塞东西,但是往往后塞进去的东西会在最上面,所以当我们取东西的时候往往先取出最后放进去的东西,如图:

我们知道栈其实也是一种线性结构,接下来我们从两种逻辑来实现它,顺序存储链式存储

顺序栈

顺序存储通常都要借助于数组,因为数组中的数据在内存中都是连续的,为了方便我们对于栈的查询以及遍历,我们加入一个指向栈顶的元素 top, 那么其数据结构应该是这样:

typedef int Status;
typedef int Data;

typedef struct {
    Data data[MAXSIZE];
    int top;
}Stack;

其结构很简单,用一个数组能保存栈中每个位置的数据,然后用一个 top 来记录当前栈的顶位于何处,这样我们就能通过一系列的方法对栈进行操作。

// 初始化空栈
Status InitStack (Stack *S) {
    S->top = -1;
    return SUCCESS;
}

// 清空栈
Status ClearStack (Stack *S) {
    S->top = -1;
    return SUCCESS;
}

// 判断是否为空栈
bool IsEmpty(Stack S) {
    if (S.top == -1) {
        return true;
    } else {
        return false;
    }
}

// 返回栈长度
int StackLength(Stack s) {
    return s.top+1;
}

// 获取栈顶元素
Status GetStackTop(Stack S,Data *data) {
    if (S.top == -1)return ERROR;
    *data = S.data[S.top];
    return SUCCESS;
}

// 入栈
Status PushData(Stack *S,Data data) {
    if (S->top == MAXSIZE-1return ERROR;
    int top = S->top+1;
    S->data[top] = data;
    S->top++;
    return SUCCESS;
}

// 出栈
Status Pop(Stack *S,Data *data) {
    if (S->top == -1return ERROR;
    *data = S->data[S->top];
    S->top--;
    return SUCCESS;
}

// 从栈底到栈顶打印栈
Status PrintStack(Stack S) {
    if (S.top == -1) {
        printf("空栈 \n");
        return ERROR;
    }
    for (int i = 0; i <= S.top; i ++) {
        printf("%d--",S.data[i]);
    }
    printf("\n");
    return SUCCESS;
}

验证

int main(int argc, const char * argv[]) {
    // insert code here...
    Stack S;
    InitStack(&S);
    for (int i = 0; i < 10; i ++) {
        PushData(&S, i);
    }
    PrintStack(S);

    Data data;
    Pop(&S, &data);
    PrintStack(S);
    printf("出栈的数据是: %d \n",data);

    GetStackTop(S, &data);
    printf("栈顶的数据是: %d \n",data);
    return 0;
}
------------------------打印数据
栈中数据是:0--1--2--3--4--5--6--7--8--9--
栈中数据是:0--1--2--3--4--5--6--7--8--
出栈的数据是: 9 
栈顶的数据是: 8 

有几个小细节点需要我们注意:

  • 线性栈的置空不用清空每个位置的数据,只需要修改 top 即可
  • 返回栈的长度不用判断 top = -1 的情况,因为 -1+1 = 0 其最终结果是一样的

其实通过上述实现我们可以发现,栈的处理核心逻辑在于 top 的处理。

链式栈

分析了顺序栈之后我们再来看看链式栈,顾名思义,链式栈用的结构就是链式存储,内部必不可少的用到指针,其在内存中不是连续的,靠的是指针的指向,所以其数据结构可以是这样:

// 栈中每个位置的数据
typedef struct Node {
    Data data;
    Node *next;
} Node;

// 栈的结构
typedef struct {
    Node *top; // 栈顶节点
    int count; // 栈的数据量
} Stack;

这里的链式栈的结构就由一个 指向栈顶的指针 和其 数据长度 构成,栈的指针指向栈顶,由上往下通过 next 指针相连,看起来应该是这样:

根据前面几篇文章链表的相关内容,我们很容易写出它的相关方法:

// 创建一个空栈
Status InitStack(Stack *S) {
    S->top = (Node *)malloc(sizeof(Node));
    if (!S->top) return ERROR;
    S->top = NULL;
    S->count = 0;
    return SUCCESS;
}

// 入栈
Status PushData(Stack *S, Data data) {
    if (!S) return ERROR;
    Node *newTop = (Node *)malloc(sizeof(Node));
    newTop->data = data;
    newTop->next = S->top;
    S->top = newTop;
    S->count++;
    return SUCCESS;
}

// 出栈
Status Pop(Stack *S,Data *data) {
    if (!S) return ERROR;
    Node *temp = S->top;
    S->top = temp->next;
    S->count--;
    *data = temp->data;
    free(temp);
    return SUCCESS;
}

// 获取栈顶元素
Status GetTop(Stack S,Data *data) {
    if (S.count == 0return ERROR;
    *data = S.top->data;
    return SUCCESS;
}

// 清空栈
Status ClearStack(Stack *S) {
    Node *temp = S->top;
    while (temp) {
        Node *target = temp;
        temp = temp->next;
        free(target);
    }
    S->top = NULL;
    S->count = 0;
    return SUCCESS;
}

// 从栈顶到栈底打印
Status PrintStack(Stack S) {
    if (S.count <= 0return ERROR;
    printf("栈的数据从顶到底是:");
    Node *temp = S.top;
    while (temp) {
        printf("%d - ",temp->data);
        temp = temp->next;
    }
    printf("\n");
    return SUCCESS;
}

验证

int main(int argc, const char * argv[]) {
    // insert code here...
    Stack S;
    InitStack(&S);
    if (InitStack(&S) == SUCCESS) {
        for (int i = 1; i < 10; i++) {
            PushData(&S, i);
        }
    }
    PrintStack(S);

    Data data;
    Pop(&S, &data);
    PrintStack(S);
    printf("出栈的元素是: %d \n",data);

    GetTop(S, &data);
    printf("栈顶的元素是: %d \n",data);
    return 0;
}
--------------------- 打印数据
栈的数据从顶到底是:9 - 8 - 7 - 6 - 5 - 4 - 3 - 2 - 1 - 
栈的数据从顶到底是:8 - 7 - 6 - 5 - 4 - 3 - 2 - 1 - 
出栈的元素是: 9 
栈顶的元素是: 8 

总结

这篇文章主要讲述了栈的结构以及栈的 顺序存储实现链式存储实现 ,希望能够讲述明白。