栈之数据结构

#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 initStack(PSTACK);
void push(PSTACK, int);
void traverseStack(PSTACK);
bool popStack(PSTACK, int *);
bool isEmpty(PSTACK);
void clearStack(PSTACK);

int main()
{
    STACK s;
    int val;
    initStack(&s);
    push(&s, 2);
    push(&s, 3);
    push(&s, 4);
    push(&s, 5);
    traverseStack(&s);
    popStack(&s, &val);
    printf("\npopStack value is %d \n", val);
    traverseStack(&s);
    printf("\n");
    clearStack(&s);
    traverseStack(&s);

    return 0;
}

/**
 * 初始化空栈思路：
 *
 * 创建一个空结点，让pTop和pBottom都指向它
 * 并清空空结点的指针域
 *
**/
void initStack(PSTACK pS)
{
    //创建一个空结点，让pTop指向它
    pS->pTop = (PNODE)malloc(sizeof(PNODE));
    if (NULL != pS->pTop)
    {
        //将pBottom也指向空节点
        pS->pBottom = pS->pTop;
        //清空空结点的指针域
        pS->pTop->pNext = NULL;
    }
    else
    {
        printf("内存分配失败!程序退出!\n");
        exit(-1);
    }
}

/**
 * 压栈思路：
 *
 * 创建一个新结点，将新结点的指针域指向之前建的空节点,再将pTop指向新的结点
 * 相当于在pTop和之前的空节点之间插入这个新节点(在压第一个元素时，这么理解)
 * 通用说法是在pTop和栈顶元素之间插入这个新节点
 *
**/
void push(PSTACK pS, int val)
{
    PNODE pNew = (PNODE)malloc(sizeof(PNODE));
    if (NULL != pNew)
    {
        pNew->data = val;
        pNew->pNext = pS->pTop;
        //重新设置pTop，将pTop指向新的结点
        pS->pTop = pNew;
    }
    else
    {
        printf("内存分配失败!程序退出!\n");
        exit(-1);
    }

}

/**
 * 遍历栈思路：
 *
 * 在遍历栈的时候不能更改栈的内部指向，所以将栈顶赋给一个临时结点
 *
**/
void traverseStack(PSTACK pS)
{
    PNODE pNode = pS->pTop;
    while (pNode != pS->pBottom)
    {
        printf("%d ",pNode->data);
        pNode = pNode->pNext;
    }
    return;
}

bool isEmpty(PSTACK pS)
{
    if(pS->pTop == pS->pBottom)
        return true;
    else
        return false;
}

/**
 * 出栈思路：
 *
 * 先保存栈顶元素的地址，然后将pTop指向下一元素,最后释放之前栈顶元素的内存
 * 相当于删除栈顶元素
 *
**/
bool popStack(PSTACK pS, int * pVal)
{
    if (isEmpty(pS))
    {
        return false;
    }
    else
    {
        PNODE pNode = pS->pTop;
        *pVal = pNode->data;
        pS->pTop = pNode->pNext;
        free(pNode);
        pNode = NULL;

        return true;
    }

}

/**
 * 清空栈思路：
 *
 * 使用两个结点指针变量用来释放栈中元素的内存
 * 最后将栈顶指向栈底(此时栈底元素还是指向initStack时创建的空节点)
 *
**/
void clearStack(PSTACK pS)
{
    if (isEmpty(pS))
    {
        return;
    }
    else
    {
        PNODE p = pS->pTop;
        PNODE q = NULL;
        while(p != pS->pBottom)
        {
            q = p->pNext;
            free(p);
            p = q;
        }
        //将栈顶指向栈底(此时栈底元素还是指向initStack时创建的空节点)
        pS->pTop = pS->pBottom;

        return;
    }

}