数据结构 第5节 栈 Stack

一、静态栈：数组实现

二、动态栈：链表实现

push操作 step_01 push操作 step_02 push result pop

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

typedef struct Node {
    int data;               //数据域
    struct Node * pNext;    //指针域
} NODE, * PNODE;


/**
    5-   pTop  删除元素就将pTop下移，增加元素就将pTop上移一个
    4-
    3-
    2-
    1-   pBottom NULL 不动  pHead
*/
typedef struct Stack {
    PNODE pTop;
    PNODE pBottom;
} STACK, * PSTACK;

void init(PSTACK);
void show(PSTACK);

void push(PSTACK pS, int val);
bool pop(PSTACK, int * pVal);

/*init的结果是：pTop 和 pBottom都指向了同一个无值的头节点**/
void init(PSTACK pStack) {
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    pHead->pNext = NULL;
    if(NULL == pHead) {
        printf("动态内存分配失败！\n");
        exit(-1);
    } else {
        pStack->pTop = pHead;
        pStack->pBottom = pHead;
    }
}

void push(PSTACK pS, int val) {
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if(NULL == pNew) {
        printf("动态内存分配失败！\n");
        exit(-1);
    }
    pNew->data = val;
    pNew->pNext = pS->pTop;
    pS->pTop = pNew;
}

/**/
void show(PSTACK pS) {
    PNODE p = pS->pTop;
    while(p != pS->pBottom) {
        printf("%d ", p->data);
        p=p->pNext;
    }
    printf("\n");
}

bool empty(PSTACK pS){
    if(pS->pTop == pS->pBottom)
        return true;
    else
        return false;
}

bool pop(PSTACK pS, int * pVal) {
    if(empty(pS)) {
        return false;
    } else {
        PNODE r = pS->pTop;
        *pVal = r->data;
        pS->pTop = r->pNext;
        free(r);
        r = NULL;
        return true;
    }
}

void clear(PSTACK pS) {
    /*
        while(pS->pTop != pBottom) {
            PSTACK p = pS->pTop;        //1. 用一个变量存pTop
            pS->pTop = p->pTop->pNext;  //2. 将pTop 指向下一个元素
            free(p);                    //3. 释放变量p
            //以上方式是?的，等价于：
            //PSTACK p = pS->pTop = p->pTop->pNext
            //所以最终free(p)的值free的是下一个

        }
    */
    if(empty(pS))
    {
        return;
    }
    else
    {
        PNODE p = pS->pTop;
        PNODE q = NULL;
        while(p != pS->pBottom) {
            q = p->pNext;
            free(p);
            p = q;
        }
        pS->pTop = pS->pBottom;
    }
}

int main(void) {
   STACK s;
   init(&s);
   push(&s,1);
   push(&s,2);
   push(&s,3);
   push(&s,4);
   push(&s,5);
   show(&s);
    int i;
   pop(&s, &i);
   printf("pop element: %d\n" , i);
  
   show(&s);


   clear(&s);
    printf("after clear:\n");
   show(&s);
   return 0;
}

三、应用：

• 生产者消费者
• 函数调用
• 中断
• 算术表达式求值
• 内存分配
• 缓冲处理
• 迷宫