栈 | 队列

PCwqyy · 2022-11-19 08:04:54 · 算法·理论

<目录

栈，和队列，是两个基本的数据结构……

栈 \sf\color{grey}Stack

定义

想象你在洗盘子，你从最上面拿下来一个盘子洗 \sf\color{gray}pop ，新来的盘子也往上堆 \sf\color{gray}push 。

手模

template<typename Tp,int maxlength>
class Stack
{
    private:
        Tp Data[maxlength+5];
        Tp*top=Data;
    public:
        Stack(){}
        Stack(Stack<Tp,maxlength>&m)
        {
            for(int i=0;i<maxlength;i++)
                Data[i]=m.Data[i];
            top=m.top;
        }
        ~Stack(){}
        int Length(){return top-Data;}
        void Push(Tp m)
        {
            if(Length()>=maxlength)
                return;
            *(top++)=m;
            return;
        }
        void Pop()
        {
            if(Length()<=0)
                return;
            top--;
            return;
        }
        bool Empty(){return top==Data;}
        Tp Top(){return *(top-1);}
        void operator=(Stack m)
        {
            for(int i=0;i<maxlength;i++)
                Data[i]=m.Data[i];
            top=m.top;
        }
        Tp& operator[](int p){return Data[p];}
};

队列 \sf\color{grey}Queue

定义

想想平时你排队是怎么排的？

是不是最前面那个人办完事情就走了 \sf\color{gray}pop ，新来的得排在后面 \sf\color{gray}push ？
是不是先来的先办事，后来的后办事？
很好，你已经理解了 \sf\color{red}FIFO \sf\color{gray}FirstInFirstOut 。

手模

template<typename Tp,int maxlength>
class Queue
{
    private:
        Tp Data[maxlength+5];
        Tp *front=Data,*back=Data;
    public:
        Queue(){}
        Queue(Queue<Tp,maxlength>&m)
        {
            for(int i=0;i<maxlength;i++)
                Data[i]=m.Data[i];
            front=m.front,back=m.back;
        }
        ~Queue(){}
        int Length()
        {
            if(front>=back) return front-back;
            else            return front-back+maxlength+1;
        }
        void Push(Tp m)
        {
            if(Length()>=maxlength)
                return;
            *(back--)=m;
            if(back<Data)   back+=maxlength+1;
        }
        void Pop()
        {
            if(Length()<=0)
                return;
            front--;
            if(front<Data)  front+=maxlength+1;
        }
        Tp Front(){return *front;}
        bool empty(){return front==back;}
        void operator=(Queue m)
        {
            for(int i=0;i<maxlength;i++)
                Data[i]=m.Data[i];
            front=m.front,back=m.back;
        }
        Tp& operator[](int p)
        {
            Tp* o=back+p;
            if(o>=Data+maxlength+1)
                o-=maxlength+1;
            return *o;
        }
};