動态棧的存儲結構及算法C語言實作

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

//棧的每個結點結構定義
typedef struct Node
{
    int data;
    struct Node *pNext;
}NODE, *PNODE;


//棧結構定義
typedef struct Stack
{
    PNODE pTop;     //指向棧頂元素的指針
    PNODE pBottom;  //指向棧底元素的下一個元素的指針（友善操作）
}STACK, *PSTACK;


//初始化棧
void init(PSTACK pS)
{
    PNODE p = (PNODE)malloc(sizeof(NODE));  //為棧底元素的下一個元素配置設定記憶體
    if (p == NULL)
    {
        printf("記憶體配置設定失敗，程式将終止\n");
        exit(-1);
    }
    pS->pTop = pS->pBottom = p;
    p->pNext = NULL;
    return pS;
}

//判斷棧是否為空
int isEmpty(PSTACK pS)
{
    if (pS->pTop == pS->pBottom)
    {
        return 0;
    }
    else
    {
        return -1;
    }
}

//壓棧
void push(PSTACK pS, int val)
{
    PNODE p = (PNODE)malloc(sizeof(NODE));
    if (p == NULL)
    {
        printf("記憶體配置設定失敗，程式将終止\n");
        exit(-1);
    }

    p->pNext = pS->pTop;
    p->data = val;
    pS->pTop = p;
    return;
}

//彈棧
void pop(PSTACK pS)
{
    if (isEmpty(pS) == -1)
    {
        PNODE p = pS->pTop;     //暫時存放待删結點
        pS->pTop = p->pNext;
        free(p);
    }
    else
    {
        printf("棧為空\n");
    }
}

//清空棧
void clear(PSTACK pS)
{
    while (isEmpty(pS) != 0)
    {
        pop(pS);
    }
}

//周遊整個棧
void traverse(PSTACK pS)
{
    PNODE p = pS->pTop;        //定義p始終指向即将周遊的元素
    while (p != pS->pBottom)
    {
        printf("%d ", p->data);
        p = p->pNext;
    }
    printf("\n");
}

int main()
{
    PSTACK pS;
    init(pS);

    push(pS, 1);
    push(pS, 2);
    push(pS, 3);
    push(pS, 4);
    push(pS, 5);
    traverse(pS);
    clear(pS);
    traverse(pS);
    return 0;
}