スタックとキュー

備忘録

C++でスタックとキューの簡単な実装を行なった．

スタックとキューの簡単な説明

スタック

後入れ先出しのデータ構造

操作
push(item) 配列の最後にitemを挿入する．
pop() 配列の最後の要素を消去する．
peek() 配列の最後の要素を取り出す．
isFull() 配列が満タンかどうかをチェックする．
isEmpty() 配列に要素があるかチェックする．

キュー

先入れ先出しのデータ構造
enqueue() 配列の最後に要素を挿入する．
dequeue() 配列の最初の要素を取り出す．
isFull() 配列が満タンかどうかをチェックする．
isEmpty() 配列に要素があるかチェックする．

スタックとキューはほとんど同じように実装できるがキューの場合はdequeueをする度にデータの始まりがどんどん変化していくため，注意が必要である．
リングバッファとみなして実装することもできる．

スタックの実装

stack.cpp

template<typename T>
class stack
{
    private:
    T data[1000];
    int index=0;
    public:
    void push(T item)
    {
        if(!isFull())
        {
            data[index]=item;
            index++;
        }
    }
    void pop()
    {
        if(!isEmpty())
        {
            data[index]==NULL;
            index--;
        }
    }
    T peek()
    {
        return data[index-1];
    }
    bool isEmpty()
    {
        if(index==0)
        {
            return true;
        }
        return false;
    }
    bool isFull()
    {
        if(index>=1000)
        {
            return true;
        }
        return false;
    }

    int Index()
    {
        return index;
    }
};

キューの実装

queue.cpp

template<typename T>
class queue
{
    private:
    int start=0;
    int last=0;
    T data[100];
    public:
    void dequeue(T item)
    {
        if(!isFull())
        {
            last++;
            data[last]=item;
        }
    }
    T enqueue()
    {
        if(!isEmpty())
        {
            start++;
            return data[start--];
        }
    }
    bool isEmpty()
    {
        if((last-start)==0)
        {
            return true;
        }
        return false;
    }
    bool isFull()
    {
        if((last-start)>=100)
        {
            return true;
        }
        return false;
    }

};