動態(tài)棧的存儲結(jié)構(gòu)及算法C語言實現(xiàn)

#include <stdio.h>  
#include <stdlib.h>  
#include <malloc.h>  
  
//棧的每個結(jié)點結(jié)構(gòu)定義  
typedef struct Node  
{  
    int data;  
    struct Node *pNext;  
}NODE, *PNODE;  
  
  
//棧結(jié)構(gòu)定義  
typedef struct Stack  
{  
    PNODE pTop;     //指向棧頂元素的指針  
    PNODE pBottom;  //指向棧底元素的下一個元素的指針（方便操作）  
}STACK, *PSTACK;  
  
  
//初始化棧  
void init(PSTACK pS)  
{  
    PNODE p = (PNODE)malloc(sizeof(NODE));  //為棧底元素的下一個元素分配內(nèi)存  
    if (p == NULL)  
    {  
        printf("內(nèi)存分配失敗，程序?qū)⒔K止\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èi)存分配失敗，程序?qū)⒔K止\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;     //暫時存放待刪結(jié)點  
        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;  
}