数据结构基础--链式栈

链式栈是一种数据存储结构，可以通过单链表的方式来实现，使用链式栈的优点在于它能够克服用数组实现的顺序栈空间利用率不高的特点，但是需要为每个栈元素分配额外的指针空间用来存放指针域。

• 宏定义

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */

• 节点的设计

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

• 链式栈结构设计

typedef struct
{
    LinkStackPtr top;//栈顶指针：永远指向栈顶元素
    int count;//记录栈里面多少元素
}LinkStack;

创建一个空栈

• 创建头结点
• 将top=0，count = 0

Status InitStack(LinkStack *S)
{
   S->top =(LinkStackPtr)malloc(sizeof(StackNode));
   if(S->top == NULL) return ERROR;
    S->top=NULL;
    S->count=0;
    return OK;
}

如何将栈置为空栈

• 先将获取栈顶结点
• 循环遍历栈结点
• 利用中间变量将便利的结点全部free
• 将count=0

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

如何判断栈是否为空

• 判断栈的长度count是否为0

/* 若栈S为空栈,则返回TRUE, 否则返回FALSE*/
Status StackEmpty(LinkStack S){
    if (S.count == 0)
        return TRUE;
    else
        return FALSE;
}

如何获取栈顶元素

• 若链栈S不为空,则用e返回栈顶元素,并返回OK ,否则返回ERROR

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

如何获取栈元素的个数，即栈的长度

int StackLength(LinkStack S){
    return S.count;
}

插入元素e到链栈S (成为栈顶新元素)

• push入栈

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

若栈不为空,则删除S的栈顶元素,用e返回其值. 并返回OK,否则返回ERROR

• pop出栈

Status Pop(LinkStack *S,SElemType *e){
    LinkStackPtr p;
    if (StackEmpty(*S)) {
        return ERROR;
    }
    
    //将栈顶元素赋值给*e
    *e = S->top->data;
    //将栈顶结点赋值给p
    p = S->top;
    //使得栈顶指针下移一位, 指向后一结点. 
    S->top= S->top->next;
    //释放p
    free(p);
    //个数--
    S->count--;
    
    return OK;
}

遍历链式栈

• 本质就是遍历链表

Status StackTraverse(LinkStack S){
    LinkStackPtr p;
    p = S.top;
    while (p) {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}