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;
}