線性結構的應用-棧

定義

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

主要操作

• 壓棧 / 入棧 / 進棧：插入元素
• 出棧 / 退棧：删除元素

性質

• 先進後出：最先進棧的元素，隻可以最後出棧

棧的分類

• 靜态棧：用數組來實作的棧
• 動态棧：用連結清單來實作的棧

動态棧的實作

棧結構

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <stdbool.h>
/**
    定義結點資料類型
*/
typedef struct Node{
    int data;
    struct Node * pNext;
}NODE,*PNODE;

/**
    定義棧結構
*/
typedef struct stack{
    PNODE pTop;
    PNODE pBottom;
}STACK,*PSTACK;

/**
    聲明函數
*/
void init_stack(PSTACK); //初始化一個棧,即建構一個棧結構
void push_stack(PSTACK,int); //把一個元素壓棧
void traverse_stack(PSTACK); //周遊棧
bool isEmpty(PSTACK);   //判斷棧空
bool pop_stack(PSTACK,int *); //出棧
void clear_stack(PSTACK);   //清空棧

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

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

    //測試 周遊棧
    traverse_stack(&s);


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

    //測試 出棧
    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){
    //為棧生成一個不存放任何資料的頭結點，并且用棧棧底指針指向它
    pStack->pBottom = (PNODE)malloc(sizeof(NODE));
    if(pStack->pBottom == NULL){
        printf("記憶體配置設定失敗，程式結束！");
        exit(-1);
    }
    //記憶體配置設定成功，也把棧頂指針指向頭結點
    pStack->pTop = pStack->pBottom;

    //初始化頭結點，把頭結點的指針域設為NULL
    pStack->pTop->pNext=NULL;
}

/**
    把一個元素壓棧
*/
void push_stack(PSTACK pStack,int element){
    //為新結點動态配置設定一個存儲空間
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if(pNew == NULL){
        printf("記憶體配置設定失敗，程式結束！");
        exit(-1);
    }

    //把新插入元素的值放入到資料域中
    pNew->data = element;

    //壓棧：把新結點挂到頭結點後面
    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;
    }
    //定義一個值儲存删除的結點
    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;
}