【数据结构】栈和队列之链栈

该系列文章主要作数据结构（C语言版）学习的笔记。里面代码的注释很详细，同时提供给大家参考，欢迎指正和指教。

栈的链式存储结构

栈的链式存储结构，简称为链栈。

栈因为只是栈顶来做插入和删除操作，所以比较好的方法是将栈顶放在单链表的头部，栈顶指针和单链表的指针合二为一。

栈的链式存储结构

栈的链式存储结构代码实现

typedef int SElemType;
// 定义链栈
typedef struct StackNode{
    
    SElemType data; // 存放栈的数据
    struct StackNode * next;
    
}StackNode, *LinkStackPtr;

typedef struct LinkStack{
    
    LinkStackPtr top; // top指针
    int count; // 栈元素计数器
    
}linkStack;

---

栈的链式存储结构操作

一、链栈的基本操作：初始化、获取链栈的长度、判断是否为空、获取栈顶元素等

/**
 * 初始化
 */
Status InitStack(linkStack *S){
    S->top = (LinkStackPtr)malloc(sizeof(StackNode));
    if(!S->top)
        return ERROR;
    S->top=NULL;
    S->count=0;
    return OK;
}

/**
 * 获取元素
 */
Status visit(SElemType c){
    printf("%d ",c);
    return OK;
}

/**
 * 清空栈
 */
Status ClearStack(linkStack *S){
    LinkStackPtr p,q;
    p=S->top;
    while(p)
    {
        q=p;
        p=p->next;
        free(q);
    }
    S->count=0;
    return OK;
}

/**
 * 判断栈是否问空
 */
Status StackEmpty(linkStack S){
    if (S.count==0)
        return TRUE;
    else
        return FALSE;
}

/**
 * 计算栈的长度
 */
int StackLength(linkStack S){
    return S.count;
}
/**
 * 获取栈顶并返回
 */
Status GetTop(linkStack S,SElemType *e){

    if (S.top == NULL) {
        return ERROR;
    }else{
        *e = S.top->data;
    }
    return OK;
}

二、进栈操作(Push)

对于链栈的进栈(Push)操作，假设元素值为e的新节点是s，top为栈顶指针，插入元素e的代码如下

/**
 * 插入元素 e 为新的栈顶元素
 */
Status Push(linkStack * S, SElemType e){
    
    LinkStackPtr p = (LinkStackPtr)malloc(sizeof(StackNode));
    p->data = e;
    p->next = S->top;   //把当前的栈顶元素赋值给新结点的直接后继
    S->top = p;        // 将新节点p赋值给栈顶指针。
    S->count++;
    
    return OK;
}

三、出栈操作(Pop)

至于链栈的出栈操作，也是简单的三句操作。

• 假设变量p用来存储要删除的栈顶结点。
• 将栈顶指针下移一位
• 释放p。

/**
 * 出栈
 */
Status Pop(linkStack * S, SElemType *e){
    
    LinkStackPtr p;
    
    if (StackEmpty(*S)) // 栈为空
        return ERROR;
    
    *e = S->top->data;
    p = S->top;           // 栈顶结点赋值给p
    S->top = S->top->next; //栈顶指针下移一位
    free(p);
    S->count--;
    return OK;
}

四、遍历链栈操作(Traverse)

/**
 * 遍历
 */
Status StackTraverse(linkStack S){
    LinkStackPtr p;
    p=S.top;
    while(p)
    {
        visit(p->data);
        p=p->next;
    }
    printf("\n");
    return OK;
}

---

测试代码

int main(int argc, const char * argv[]) {
    @autoreleasepool {

        int j;
        linkStack s;
        int e;
        if (InitStack(&s)) {  //将1到10依次进栈
            for (j = 1; j <= 10; j++) {
                Push(&s, j);
            }
        }
        printf("栈中的元素依次为：");
        StackTraverse(s);
        Pop(&s,&e);
        printf("弹出的栈顶元素 e=%d\n",e);
        printf("栈空否：%d(1:空 0:否)\n",StackEmpty(s));
        GetTop(s,&e);
        printf("栈顶元素 e=%d 栈的长度为%d\n",e,StackLength(s));
        ClearStack(&s);
        printf("清空栈后，栈空否：%d(1:空 0:否)\n",StackEmpty(s));
    }
    return 0;
}

测试结果

---

对比顺序栈和链栈

• 时间复杂度：均为O(1)
• 空间性能：
  • 顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题。但是它的优势在于存取的时候很方便。
  • 链栈要求每个元素都有指针域，也增加了内存开销，但是对于栈的长度无限制。
• 总体而言：如果栈的使用过程中元素变化不可预料，有时很小，有时很大，那么最好用链栈，反之，如果变化在可控范围，使用顺序栈更好。