C语言实现使用带头结点的单链表来模拟栈结构

我在前面两篇博客中分别使用了静态数组、动态数组两种方式来构造栈，实现起来很方便，但总觉得灵活性还不够，因为无论怎样，我们都是要指定数组的长度。这篇博客中我们将会使用带头结点的单链表来模拟栈。为什么选用单链表呢？因为对于栈来说，弹出、压入等操作都是对栈顶来操作的。而单链表对第一个节点的操作是最为方便的。两者刚好能对应起来。代码上传至 https://github.com/chenyufeng1991/Stack_LinkedList。

（1）声明节点类型、函数

 

typedef int elemType;
typedef struct NodeList{

    int element;
    struct NodeList *next;
}Node;

void createStack(Node **pNode);
void destroyStack(Node *pNode);
void push(Node *pNode,int value);
void pop(Node *pNode);
void top(Node *pNode);
int isEmpty(Node *pNode);
int isFull(Node *pNode);
void printStack(Node *pNode);

（2）初始化单链表

 

 

//初始化带头结点的单链表
void createStack(Node **pNode){

    *pNode = (Node *)malloc(sizeof(Node));
    if (*pNode == NULL) {
        printf("%s函数执行，内存分配失败，初始化单链表失败\n",__FUNCTION__);
    }else{

        (*pNode)->next = NULL;
        printf("%s函数执行，带头结点的单链表初始化完成\n",__FUNCTION__);
    }
}

（3）压入一个元素

 

 

//压入一个元素
void push(Node *pNode,int value){

    Node *pInsert;
    pInsert = (Node *)malloc(sizeof(Node));//需要检测分配内存是否成功 pInsert == NULL  ?
    memset(pInsert, 0, sizeof(Node));
    pInsert->next = NULL;
    pInsert->element = value;

    pInsert->next = pNode->next;
    pNode->next = pInsert;
}

（4）弹出一个元素

 

 

//弹出一个元素
void pop(Node *pNode){

    if (!isEmpty(pNode)) {

        Node *pNext;
        pNext = pNode->next;

        pNode->next = pNext->next;
        free(pNext);
        pNext = NULL;
    }
}

（5）打印栈元素

 

 

//打印栈元素
void printStack(Node *pNode){

    if (!isEmpty(pNode)) {

        Node *pMove;
        pMove = pNode->next;
        while (pMove != NULL) {
            printf("%d ",pMove->element);
            pMove = pMove->next;
        }
        printf("\n");
    }else{
        printf("栈为空，打印失败\n");
    }
}

（6）清空栈元素

 

 

//清空栈元素
void destroyStack(Node *pNode){

    Node *pMove;
    pMove = pNode->next;
    while (pMove != NULL) {

        pNode->next = pMove->next;
        free(pMove);
        pMove = pNode->next;
    }
}

（7）判断栈是否为空

 

 

//判断栈是否为空
int isEmpty(Node *pNode){
    /**
     *  当只有一个头结点的时候，该链表就为空
     */
    if (pNode->next == NULL) {
        return 1;
    }
    return 0;
}

（8）取栈顶元素

 

 

//取栈顶元素
void top(Node *pNode){
    if (!isEmpty(pNode)) {
        printf("栈顶元素为%d\n",pNode->next->element);
    }
}

（8）测试代码

 

 

int main(int argc, const char * argv[]) {

    Node *pList;
    createStack(&pList);

    push(pList, 3);push(pList, 1);push(pList, 9);push(pList, 4);push(pList, 7);
    printStack(pList);

    pop(pList);pop(pList);
    printf("经过pop后栈的元素为:\n");
    printStack(pList);

    top(pList);
    
    destroyStack(pList);
    printStack(pList);
    
    return 0;
}