链栈的基本操作及实现

一、定义和特点

链栈是一种基于链表实现的栈，在链表头部作为栈顶，每次入栈和出栈时更改链表头的指向即可。链栈和数组栈相比，具有动态性和灵活性，不需要确定栈的最大长度，同时插入和删除元素的时间复杂度是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;
}