キュー
でことで、前のエントリ通り、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.