キュー

でことで、前のエントリ通り、deleteの挙動がようわからんくて、どうすればちゃんと解放されんのかがいまいちわからないからdeqの部分が未完成なんだけどとりあえず書いてみた。
あとdeq時の範囲のチェックをしていない。。

STLとか見たけど、STLのqueueは、汎用のsetのラッパーってかんじだったなー。まあちゃんとは読んでないけど。


とりあえずクラスつかってそろそろコード書こうと思ったのでなんか書いてみたかんじ。

// queue.cpp
#include <iostream>

/**
 * queue class
 */
class queue_items
{
    public:
        int data;
        queue_items *next_ptr;

        queue_items(const int i);
};

queue_items::queue_items(const int i = 0)
{
    data = i;
    next_ptr = NULL;
}

class queue
{
    public:
        queue_items *last_ptr;
        queue_items *first_ptr;

        queue();
        queue(queue_items *);
        static queue* initialize(int);
        //~queue();
        void enq(const int i);
        int deq();
        void print_all();

    private:
};

queue::queue()
{
    first_ptr = new queue_items();
    last_ptr = first_ptr;
}

queue::queue(queue_items *i)
{
    first_ptr = i;
    last_ptr = first_ptr;
}

queue* queue::initialize(const int i = 0)
{
    queue_items *q =  new queue_items(i);
    return new queue(q);
}

void queue::enq(const int i)
{
    //next_ptr = new queue(i);
    last_ptr->next_ptr = new queue_items(i);
    last_ptr = last_ptr->next_ptr;
}

int queue::deq()
{
    int tmp = first_ptr->data;
    first_ptr = first_ptr->next_ptr;

    // あれれれれれれれ
    // メモリの解放どうしたらいいんだ!?
    // delete first_ptr;

    return tmp;
}

void queue::print_all()
{
    queue_items *current_ptr = first_ptr;
    while (current_ptr != NULL) {
        std::cout << current_ptr->data << " -> ";
        current_ptr = current_ptr->next_ptr;
    }

    std::cout << "end." << std::endl;
}

int main()
{
    queue *q; 
    q = queue::initialize(0);
    //q = new queue(1);

    std::cout << "after initialize: " << std::endl;
    q->print_all();

    int i = 1, test_max = 30; 
    for(;i < test_max; ++i) {
        q->enq(i);
        if (i%5 == 0) {
            std::cout << i << " => ";
            q->print_all();
        }   
    }   

    for(;i > 0; --i) {
        if (i%5 == 0) {
            std::cout << i << " => ";
            q->print_all();
        }   
        q->deq();
    }   

    std::cout << "end of test" << std::endl;
    q->print_all();
    return 0;
}

実行すると。

after initialize: 
0 -> end.
5 => 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> end.
10 => 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> end.
15 => 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> end.
20 => 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 -> 18 -> 19 -> 20 -> end.
25 => 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 -> 18 -> 19 -> 20 -> 21 -> 22 -> 23 -> 24 -> 25 -> end.
30 => 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 -> 18 -> 19 -> 20 -> 21 -> 22 -> 23 -> 24 -> 25 -> 26 -> 27 -> 28 -> 29 -> end.
25 => 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 -> 18 -> 19 -> 20 -> 21 -> 22 -> 23 -> 24 -> 25 -> 26 -> 27 -> 28 -> 29 -> end.
20 => 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 -> 18 -> 19 -> 20 -> 21 -> 22 -> 23 -> 24 -> 25 -> 26 -> 27 -> 28 -> 29 -> end.
15 => 15 -> 16 -> 17 -> 18 -> 19 -> 20 -> 21 -> 22 -> 23 -> 24 -> 25 -> 26 -> 27 -> 28 -> 29 -> end.
10 => 20 -> 21 -> 22 -> 23 -> 24 -> 25 -> 26 -> 27 -> 28 -> 29 -> end.
5 => 25 -> 26 -> 27 -> 28 -> 29 -> end.
end of test
end.