定義

• 棧是一種運(yùn)算受限的線性表
• 其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算
• 允許進(jìn)行操作的一端被稱為棧頂，另一端則稱為棧底

主要操作

• 壓棧 / 入棧 / 進(jìn)棧：插入元素
• 出棧 / 退棧：刪除元素

性質(zhì)

• 先進(jìn)后出：最先進(jìn)棧的元素，只可以最后出棧

棧的分類(lèi)

• 靜態(tài)棧：用數(shù)組來(lái)實(shí)現(xiàn)的棧
• 動(dòng)態(tài)棧：用鏈表來(lái)實(shí)現(xiàn)的棧

動(dòng)態(tài)棧的實(shí)現(xiàn)

棧結(jié)構(gòu)

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <stdbool.h>
/**
    定義結(jié)點(diǎn)數(shù)據(jù)類(lèi)型
*/
typedef struct Node{
    int data;
    struct Node * pNext;
}NODE,*PNODE;

/**
    定義棧結(jié)構(gòu)
*/
typedef struct stack{
    PNODE pTop;
    PNODE pBottom;
}STACK,*PSTACK;

/**
    聲明函數(shù)
*/
void init_stack(PSTACK); //初始化一個(gè)棧,即構(gòu)建一個(gè)棧結(jié)構(gòu)
void push_stack(PSTACK,int); //把一個(gè)元素壓棧
void traverse_stack(PSTACK); //遍歷棧
bool isEmpty(PSTACK);   //判斷?？?bool pop_stack(PSTACK,int *); //出棧
void clear_stack(PSTACK);   //清空棧

int main()
{
    STACK s; //定義一個(gè)棧
    //測(cè)試 初始化棧
    init_stack(&s);

    //測(cè)試 壓棧
    push_stack(&s,2);
    push_stack(&s,5);
    push_stack(&s,4);
    push_stack(&s,8);

    //測(cè)試 遍歷棧
    traverse_stack(&s);


    //測(cè)試清空棧
    clear_stack(&s);

    //測(cè)試 出棧
    int element;  //保存刪除的元素
    if(pop_stack(&s,&element)){
        printf("刪除成功，你刪除的元素是：%d \n",element);
    }else{
        printf("刪除失?。n");
    }
    traverse_stack(&s);
    printf("Hello world!\n");
    return 0;
}

/**
    初始化棧
*/
void init_stack(PSTACK pStack){
    //為棧生成一個(gè)不存放任何數(shù)據(jù)的頭結(jié)點(diǎn)，并且用棧棧底指針指向它
    pStack->pBottom = (PNODE)malloc(sizeof(NODE));
    if(pStack->pBottom == NULL){
        printf("內(nèi)存分配失敗，程序結(jié)束！");
        exit(-1);
    }
    //內(nèi)存分配成功，也把棧頂指針指向頭結(jié)點(diǎn)
    pStack->pTop = pStack->pBottom;

    //初始化頭結(jié)點(diǎn)，把頭結(jié)點(diǎn)的指針域設(shè)為NULL
    pStack->pTop->pNext=NULL;
}

/**
    把一個(gè)元素壓棧
*/
void push_stack(PSTACK pStack,int element){
    //為新結(jié)點(diǎn)動(dòng)態(tài)分配一個(gè)存儲(chǔ)空間
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if(pNew == NULL){
        printf("內(nèi)存分配失敗，程序結(jié)束！");
        exit(-1);
    }

    //把新插入元素的值放入到數(shù)據(jù)域中
    pNew->data = element;

    //壓棧：把新結(jié)點(diǎn)掛到頭結(jié)點(diǎn)后面
    pNew->pNext = pStack->pTop;

    //把棧頂指針指向棧頂元素
    pStack->pTop = pNew;

    return;
}

/**
    遍歷棧
*/
void traverse_stack(PSTACK pStack){
    //得到棧頂元素的位置
    PNODE p = pStack->pTop;

    //遍歷棧
    while(p != pStack->pBottom){
        printf("%d\t",p->data);
        p = p->pNext;
    }
    printf("\n");

    return;
}

/**
    判斷棧是否為空
*/
bool isEmpty(PSTACK pStack){
    if(pStack->pBottom == pStack->pTop)
        return true;
    else
        return false;
}


/**
    出棧，并保存出棧元素
*/
bool pop_stack(PSTACK pStack,int *pElement){
    if(isEmpty(pStack)){
        printf("出棧失敗！棧為空！");
        return false;
    }
    //定義一個(gè)值保存刪除的結(jié)點(diǎn)
    PNODE p = pStack->pTop;
    *pElement = p->data;
    pStack->pTop = p->pNext;
    free(p);
    p=NULL;

    return true;

}

/**
    清空棧
*/
void clear_stack(PSTACK pStack){
    if(isEmpty(pStack))
        return;

    PNODE p = pStack->pTop;
    PNODE q = NULL;

    while(p != pStack->pBottom){
        q = p->pNext;
        free(p);
        p=q;
    }
    pStack->pTop = pStack->pBottom;
    return;
}