什么是棧

棧是一種運(yùn)算受限的線性表。限定僅在表尾進(jìn)行插入和刪除操作的線性表。這一端被稱為棧頂，相對(duì)地，把另一端稱為棧底。向一個(gè)棧插入新元素又稱作進(jìn)棧、入?；驂簵?，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個(gè)棧刪除元素又稱作出?；蛲藯＃前褩ｍ斣貏h除掉，使其相鄰的元素成為新的棧頂元素。一句話描述棧的特性就是先進(jìn)后出

如何實(shí)現(xiàn)棧

實(shí)現(xiàn)一個(gè)棧我們一般有兩種方法：

順序結(jié)構(gòu)

顧名思義，就是使用數(shù)組來實(shí)現(xiàn)棧的特性。數(shù)組實(shí)現(xiàn)簡(jiǎn)單，我們只需要預(yù)先定義好數(shù)組的大小、在數(shù)組的末尾進(jìn)行元素的入棧操作或者出棧操作即可。時(shí)間復(fù)雜度為 O(1)。但是我們棧的大小有限，動(dòng)態(tài)調(diào)整棧大小的代價(jià)較高，且要求有連續(xù)的地址空間。

鏈?zhǔn)浇Y(jié)構(gòu)

我們可以使用鏈表來實(shí)現(xiàn)。我們?cè)谶M(jìn)行出棧操作和入棧操作的時(shí)間復(fù)雜度都是 O(1)。同時(shí)可以動(dòng)態(tài)的管理?xiàng)５拇笮　?/p>

棧的實(shí)現(xiàn)

元素節(jié)點(diǎn)定義（這是展示的是鏈表實(shí)現(xiàn)的方式）：

#include <stdio.h>
#include <stdlib.h>

// 棧節(jié)點(diǎn)元素
typedef struct Node
{
    /* data */
    int val;

    struct Node *next;
    struct Node *prev;
} Node;

// 頭節(jié)點(diǎn)元素
Node *head = NULL;
// 記錄棧元素的數(shù)量
int size = 0;

棧的初始化操作

void init()
{
    head = NULL;
    size = 0;
}

入棧操作

void push(int val)
{
    Node *node = (Node *)malloc(sizeof(Node));
    node->val = val;
    node->prev = node->next = NULL;
    if (head == NULL)
    {
        head = node;
    }
    else
    {
        head->next = node;
        node->prev = head;
        head = node;
    }
    size++;
}

出棧操作

int pop()
{
    if (head == NULL)
    {
        return 0xFFFFFF;
    }
    Node *old = head;
    head = head->prev;
    if (head != NULL)
    {
        head->next = NULL;
    }

    old->prev = NULL;
    int val = old->val;
    size--;
    free(old);
    return val;
}

獲取棧容量

int stackSize()
{
    return size;
}

啟動(dòng)函數(shù)

int main()
{
    init();
    push(1);
    push(2);
    printf("%d\n", pop());
    printf("%d\n", pop());
    printf("%d", stackSize());
    return 0;
}
/*
2
1
0
*/

棧的應(yīng)用

棧在計(jì)算機(jī)中十分常見。比如我們寫代碼的遞歸就會(huì)使用到棧。瀏覽器頁(yè)面的前進(jìn)后退都會(huì)使用到棧?？梢姉５牡闹匾赃€是比較高的，需要我們好好掌握。后續(xù)有時(shí)間會(huì)結(jié)合棧和算法寫一篇文章，歡迎閱讀。

數(shù)據(jù)結(jié)構(gòu)中相關(guān)的代碼我已上傳到 gitlab:
https://gitlab.com/BitLegend/c-data-structure.git

此后的數(shù)據(jù)結(jié)構(gòu)代碼我都會(huì)上傳在這個(gè)倉(cāng)庫(kù)中，需要的同學(xué)可以自己下載

以上就是本期的全部?jī)?nèi)容。在這里給大家拜個(gè)早年，祝大家新的一年牛氣沖天！

感謝你能看到這里，歡迎關(guān)注我的微信公眾號(hào)：BitLegend，學(xué)習(xí)更多的知識(shí)！我們下期再見！