鏈棧的基本操作及實現

一、定義和特點

鏈棧是一種基於鏈表實現的棧，在鏈表頭部作為棧頂，每次入棧和出棧時更改鏈表頭的指向即可。鏈棧和數組棧相比，具有動態性和靈活性，不需要確定棧的最大長度，同時插入和刪除元素的時間複雜度是O(1)。

二、棧的基本操作

1、初始化棧

（1）棧的數據結構

typedef struct StackNode
{
    int data;
    struct StackNode *next;
}StackNode, *LinkStackPtr;

typedef struct LinkStack
{
    LinkStackPtr top;
    int count;
}LinkStack;

（2）初始化函數實現

初始化需要分配一個頭結點，將top指向NULL，表示棧為空。

void InitStack(LinkStack *S)
{
    S->top = (LinkStackPtr)malloc(sizeof(StackNode));
    S->top->next = NULL;
    S->count = 0;
}

2、判斷棧空

當棧頂指針指向頭結點時，說明棧為空。

bool StackEmpty(LinkStack S)
{
    return S.top->next == NULL;
}

3、入棧

每次在棧頂插入一個元素，需要注意順序。

bool Push(LinkStack *S, int data)
{
    LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));
    s->data = data;
    s->next = S->top->next;
    S->top->next = s;
    S->count++;
    return true;
}

4、出棧

每次從棧頂刪除一個元素，並返回該元素的值。

bool Pop(LinkStack *S, int *data)
{
    if(StackEmpty(*S)) return false;

    LinkStackPtr p = S->top->next;
    S->top->next = p->next;
    *data = p->data;
    free(p);
    S->count--;
    return true;
}

5、獲取棧頂元素值

只需要返回棧頂元素的值即可。

bool GetTop(LinkStack S, int *data)
{
    if(StackEmpty(S)) return false;

    *data = S.top->next->data;
    return true;
}

三、簡單應用

下面是鏈棧的一個簡單應用，判斷括弧序列是否合法。

bool BracketsMatch(char str[])
{
    LinkStack S;
    InitStack(&S);

    int i = 0;
    char c;
    while(str[i] != '\0')
    {
        switch(str[i])
        {
            case '(':
            case '[':
            case '{':
                Push(&S, str[i]);
                break;
            case ')':
            case ']':
            case '}':
                if(StackEmpty(S)) return false;
                Pop(&S, &c);
                if(str[i]-c != 1 && str[i]-c != 2) return false;
                break;
            default:
                break;
        }
        i++;
    }

    if(!StackEmpty(S)) return false;

    return true;
}

四、完整代碼

#include 
#include 

typedef struct StackNode
{
    int data;
    struct StackNode *next;
}StackNode, *LinkStackPtr;

typedef struct LinkStack
{
    LinkStackPtr top;
    int count;
}LinkStack;

void InitStack(LinkStack *S)
{
    S->top = (LinkStackPtr)malloc(sizeof(StackNode));
    S->top->next = NULL;
    S->count = 0;
}

bool StackEmpty(LinkStack S)
{
    return S.top->next == NULL;
}

bool Push(LinkStack *S, int data)
{
    LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));
    s->data = data;
    s->next = S->top->next;
    S->top->next = s;
    S->count++;
    return true;
}

bool Pop(LinkStack *S, int *data)
{
    if(StackEmpty(*S)) return false;

    LinkStackPtr p = S->top->next;
    S->top->next = p->next;
    *data = p->data;
    free(p);
    S->count--;
    return true;
}

bool GetTop(LinkStack S, int *data)
{
    if(StackEmpty(S)) return false;

    *data = S.top->next->data;
    return true;
}

bool BracketsMatch(char str[])
{
    LinkStack S;
    InitStack(&S);

    int i = 0;
    char c;
    while(str[i] != '\0')
    {
        switch(str[i])
        {
            case '(':
            case '[':
            case '{':
                Push(&S, str[i]);
                break;
            case ')':
            case ']':
            case '}':
                if(StackEmpty(S)) return false;
                Pop(&S, &c);
                if(str[i]-c != 1 && str[i]-c != 2) return false;
                break;
            default:
                break;
        }
        i++;
    }

    if(!StackEmpty(S)) return false;

    return true;
}

int main()
{
    LinkStack S;
    int x;
    InitStack(&S);
    Push(&S,1);
    Push(&S,2);
    Pop(&S,&x);
    printf("%d\n",x);
    GetTop(S, &x);
    printf("%d\n",x);

    char str[] = "[{(())}]";
    printf("%d\n", BracketsMatch(str));

    return 0;
}