数据结构(八)栈

- 日理万妓 2022-05-31 01:48 147阅读 0赞

**1、算法**

栈是后入先出的规则，在代码实现的时候，构造栈链表的时候，节点指向前面的节点，而队列节点指向后面的节点，以便出栈的时候，代码实现方便。

**2、代码示例**

#ifndef DATA_STRUCT_STACK_H
    #define DATA_STRUCT_STACK_H
    #include <iostream>
    using namespace std;
    class Stack{
        class node{//链表节点
        public:
            node(int tvalue)
            {
                value=tvalue;
                pre=NULL;
            };
            ~node(){};
            node* pre;//区别
            int value;
    
        };
    public:
        Stack(){
            qhead=NULL;
            qrear=NULL;
        };
        ~Stack(){};
    
        //队列四大元素
        node* qhead;//队头
        node* qrear;//队尾
    
    
        void push(int value)//插入元素的时候，主要是更新栈尾
        {
            node * n1=new node(value);
            if(!qhead){
                qhead=n1;
                qrear=n1;
                return;
            }
    
            n1->pre=qrear;//需要注意这个地方与队列的区别
            qrear=n1;
        }
        node * pop(){//出栈的时候，主要是更新栈尾
            if (!qrear)
            {
                return NULL;
            }
    
            node* temp=qrear;
            qrear=qrear->pre;
    
            return temp;
        }
    
        bool empty(){//队列弹出，要判断是否队列已经为空
            return !qrear;
        }
    
        void main(){//用于测试
            int data[10]={1,2,3,4,5,6,7,8,9,10};
            for (int i = 0; i <10 ; ++i) {
                push(data[i]);
            }
    
            while(!empty())
            {
                node* n=pop();
                std::cout<<n->value<<std::endl;
                delete n;
            }
    
    
        }
    
    };
    
    #endif //DATA_STRUCT_STACK_H