动态栈的存储结构及算法C语言实现

动态栈的存储结构及算法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;  
}