利用单链表实现栈

冷不防 2022-05-29 06:35 244阅读 0赞

栈是一种仅限于在头尾操作的数据结构，和队列相反，栈的特点是“现金后出”，因此又称为LIFO。

和队列一样，栈也有链表和数组两种实现方式，各自的优缺点和介绍队列时提到的基本相同。以下介绍使用链表实现栈的方式（链式栈）。下面是链式栈的示意图：

因为栈的特点是“先进后出”，因此我们只需要一个指针指示栈顶即可，因为无论插入或者删除都是针对顶部的节点而已，也就是说，我们需要实现一个“头节点”会变化的链表，并且每次变化后都可以拿到头节点最新地址即可。

明确了这一点后，只需要在单链表的基础上稍稍改进即可实现基本的栈和对应的操作。

下面是利用单链表实现栈的源码：

#include <string.h>
    #include <malloc.h>
    #include <iostream>
    
    using namespace std;
    
    typedef struct stack{
        int data;
        struct stack* nextNode;
    }stack_t;
    
    static stack_t* s;
    
    void stack_Init(stack_t** top){
        /*
    
        */
    }
    
    bool stack_push(stack_t** top, int data){
        stack_t* node = (stack_t*)malloc(sizeof(stack_t));
        if(!node){
            return false;   
        }   
        node->data = data;
        node->nextNode = *top;
        *top = node;
        return true;
    }
    
    bool isEmpty(stack_t* top){
        return (top == NULL);
    }
    
    bool stack_pop(stack_t** top){
        if(isEmpty(*top)){
            return false;
        }
        stack_t* tmp = *top;
        *top = (*top)->nextNode;
        if(tmp){
            free(tmp);  
        }
        return true; 
    }
    
    void printStackData(stack_t* top){
        stack_t* tmp = top;
        while(tmp){
            cout << tmp->data << " ";
            tmp = tmp->nextNode;
        }
        cout << endl;
    }
    
    void stack_Deinit(stack_t** top){
        stack_t* tmp = *top;
        while(tmp){
            cout << "free node, data is:" << tmp->data << endl;
            free(tmp);
            *top = (*top)->nextNode;
            tmp =*top;
        }
    }
    
    bool topValue(stack_t* top, int& val){
        if(isEmpty(top)){
            return false;
        }
        val = top->data;
        return true;
    }
    
    int main(){
        stack_t* s = NULL;
        stack_push(&s,1);
        stack_push(&s,2);
        int val;
        if(topValue(s, val))
            cout << "now top value of stack is:" << val << endl; 
        stack_push(&s,3);
        printStackData(s);
    
        stack_pop(&s);
        printStackData(s);
    
        stack_push(&s,100);
        stack_push(&s,201);
        if(topValue(s, val))
            cout << "now top value of stack is:" << val << endl;
        stack_push(&s,303);
        printStackData(s);
    
        stack_Deinit(&s);
        printStackData(s);
    
        cout << "stack empty? " <<  isEmpty(s) << endl;

`}````转自：http://blog.csdn.net/keheinash/article/details/51163932`