手元にある各言語で、標準入力からの数値列をQueueに放り込んで、入力と同順になるように標準出力に吐き出すプログラムを書いてみようと思ったメモ。
標準入力から入力される数値列の要件は以下の通り。
- 1行に1つの数値が書かれている
- 不正入力のチェックは不要とする
- いくつの数値が入力されるかは不明（ただし、メモリがあふれることが無い程度に手加減する）
- 入力される数値は符号付32ビット整数とする
入力をそのまま標準出力に放り出せばいいじゃないかという突っ込みもあるだろうが、Queue構造を扱ってみようというのが今回の目的。
環境
手元にあるものということで、環境は以下のものに限定する。
- CentOS 7
入力ファイルの例
- 001.txt
0 1 -1 256 -256 32768 -32768 2147483647 -2147483648
期待される出力の例
- 001.txt
0 1 -1 256 -256 32768 -32768 2147483647 -2147483648
Java
import java.io.PrintWriter; import java.util.ArrayDeque; import java.util.Queue; import java.util.Scanner; public class Main { public static void main(String[] args) { try (Scanner in = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out) ) { Queue<Integer> queue = new ArrayDeque<>(); while (in.hasNextInt()) { queue.offer(in.nextInt()); } while (queue.peek() != null) { out.println(queue.poll()); } } } }
Javaには、Queueとして使えるjava.util.Queueの実装クラスがあるので、それを使って簡単に書ける。
C
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct { int capacity; int lastIndex; int curIndex; int* elemData; } IntQueue; IntQueue* IntQueue_new(int capacity) { IntQueue* queue = (IntQueue*)calloc(sizeof(IntQueue), 1); queue->elemData = (int*)calloc(sizeof(int), capacity); queue->capacity = capacity; queue->lastIndex = 0; queue->curIndex = 0; return queue; } void IntQueue_destroy(IntQueue* queue) { free(queue->elemData); free(queue); } int IntQueue_isEmpty(IntQueue* queue) { return queue->curIndex >= queue->lastIndex; } void IntQueue_push(IntQueue* queue, int elem) { // 先頭の方の使わなくなった領域をつぶして再利用。 if (queue->lastIndex + 1 >= queue->capacity && queue->curIndex > 0) { if (queue->lastIndex - queue->curIndex > 0) { memmove(queue->elemData, &(queue->elemData[queue->curIndex]), sizeof(int) * (queue->lastIndex - queue->curIndex)); } queue->lastIndex -= queue->curIndex; queue->curIndex = 0; } // それでも領域が足りない場合は増やす。 if (queue->lastIndex + 1 >= queue->capacity) { int newCapacity = queue->capacity * 2; int* newElemData = (int*)calloc(sizeof(int), newCapacity); memcpy(newElemData, &(queue->elemData[queue->curIndex]), sizeof(int) * (queue->lastIndex - queue->curIndex)); free(queue->elemData); queue->elemData = newElemData; queue->capacity = newCapacity; queue->lastIndex -= queue->curIndex; queue->curIndex = 0; } queue->elemData[(queue->lastIndex)++] = elem; } int IntQueue_pop(IntQueue* queue) { return queue->elemData[(queue->curIndex)++]; } int main(int argc, char** argv) { IntQueue* queue = IntQueue_new(256); int num; while (scanf("%ld", &num) == 1) { IntQueue_push(queue, num); } while (!IntQueue_isEmpty(queue)) { printf("%d\n", IntQueue_pop(queue)); } IntQueue_destroy(queue); return 0; }
C言語は当然自前実装。
C++
#include <algorithm> #include <iostream> #include <queue> using namespace std; int main(int argc, char** argv) { queue<int> queue; int num; while (cin >> num) { queue.push(num); } while (!queue.empty()) { cout << queue.front() << endl; queue.pop(); } return EXIT_SUCCESS; }
C++にはqueueがあるので、それを使って簡単に書ける。
PHP
<?php class Queue { private $elemData = array(); public function isEmpty() { return count($this->elemData) === 0; } public function push($value) { array_push($this->elemData, $value); } public function pop() { return array_shift($this->elemData); } } $lines = file('php://stdin'); $queue = new Queue(); foreach ($lines as $line) { $queue->push((int)$line); } while (!$queue->isEmpty()) { printf("%d\n", $queue->pop()); }
PHPには標準ではQueueクラスが無いので書いてみた。単なる配列のラッパー。
ただ、65536個の数値を食わせてみたら、array_shiftで時間を食っているのか、返ってくるのに3分強かかったので、大量データに対しては実用的ではないかも。array_shiftを使わずに、先頭のインデックスを持っておいてインクリメントしていく方がいいのかも。
Python 2
(2017/11/18追記) よくよく調べてみたら、Queueモジュールがあったので、その実装を追記。
自前実装版
import sys class Queue: elemData = [] def push(self, value): self.elemData.append(value) def pop(self): return self.elemData.pop(0) def isEmpty(self): return len(self.elemData) == 0 queue = Queue() while True: line = sys.stdin.readline() if line == '': break queue.push(int(line)) while queue.isEmpty() != True: print queue.pop()
Python 2ではQueueクラスが見当たらなかったので書いてみた。単なる配列のラッパー。
Queueモジュール版
import sys import Queue aQueue = Queue.Queue() while True: line = sys.stdin.readline() if line == '': break aQueue.put(int(line)) while aQueue.empty() != True: print aQueue.get()
Python 3
(2017/11/18追記) よくよく調べてみたら、queueモジュールがあったので、その実装を追記。
自前実装版
import sys class Queue: elemData = [] def push(self, value): self.elemData.append(value) def pop(self): return self.elemData.pop(0) def isEmpty(self): return len(self.elemData) == 0 queue = Queue() while True: line = sys.stdin.readline() if line == '': break queue.push(int(line)) while queue.isEmpty() != True: print(queue.pop())
Python 3ではQueueクラスが見当たらなかったので書いてみた。単なる配列のラッパー。
queueモジュール版
import sys import queue aQueue = queue.Queue() while True: line = sys.stdin.readline() if line == '': break aQueue.put(int(line)) while aQueue.empty() != True: print(aQueue.get())
Ruby
(2017/11/18追記) よくよく調べてみたら、Queueクラス(Thread::Queueのエイリアス)があったので、その実装を追記。
自前実装版
class Queue def initialize @elemData = [] end def push(value) @elemData.push(value) end def pop @elemData.shift end def isEmpty return @elemData.size == 0 end end queue = Queue.new while line = STDIN.gets num = line.to_i queue.push(num) end while !queue.isEmpty print queue.pop(),"\n" end
RubyではQueueクラスが見当たらなかったので書いてみた。単なる配列のラッパー。
Thread::Queue版
queue = Queue.new while line = STDIN.gets num = line.to_i queue.push(num) end while !queue.empty? print queue.pop(),"\n" end
Perl
Perlにはpush/shift関数があるということだが、なんか微妙なので、2パターン書いてみた。
push/shift関数バージョン
my @queue = (); my $line; while ($line = readline(STDIN)) { my $num = $line + 0; push @queue, $num; } while ($#queue + 1 > 0) { my $value = @queue[0]; shift @queue; print "$value\n"; }
Queueモジュールバージョン
Queue.pm
package Queue; sub new { my %self; my $class = shift; $self->{elemData} = (); $self->{cur} = 0; $self->{last} = 0; return bless $self, $class; } sub push { my $self = shift; my $value = shift; $self->{elemData}[$self->{last}] = $value; ++$self->{last}; } sub front { my $self = shift; return $self->{elemData}[$self->{cur}]; } sub pop { my $self = shift; delete $self->{elemData}[$self->{cur}]; ++$self->{cur}; } sub isEmpty { my $self = shift; return $self->{cur} >= $self->{last}; } 1;
Main.pl
require "Queue.pm"; my $queue = Queue->new; my $line; while ($line = readline(STDIN)) { my $num = $line + 0; $queue->push($num); } while (!$queue->isEmpty()) { my $value = $queue->front(); $queue->pop(); print "$value\n"; }
Go
listをキュー代わりに直接使うということを考えたが、せっかくなので、Queueパッケージを作ってみた。
src/queue/queue.go
package queue; import ( "container/list" ) type Queue struct { elemData *list.List } func (s *Queue) Init() *Queue { s.elemData = list.New() return s } func New() *Queue { return new(Queue).Init() } func (s *Queue) Push(v interface{}) { s.elemData.PushBack(v) } func (s *Queue) Pop() interface{} { e := s.elemData.Front() s.elemData.Remove(e) return e.Value } func (s *Queue) IsEmpty() bool { return s.elemData.Len() == 0 }
Main.go
package main import ( "bufio" "fmt" "io" "os" "strconv" "queue" ) func main() { aQueue := queue.New() stdin := bufio.NewReader(os.Stdin) buf := make([]byte, 0, 1024) for { line, prefix, err := stdin.ReadLine() if err == io.EOF { break } buf = append(buf, line...) if prefix { continue } s := string(buf) num, err2 := strconv.Atoi(s) if err2 != nil { panic(err2) } buf = make([]byte, 0, 1024) aQueue.Push(num) } for !aQueue.IsEmpty() { fmt.Println(aQueue.Pop()) } }
実行するときに、GOPATH=$(pwd) go run Main.goってしてやらないと、カレントディレクトリのソースを参照してくれないのは注意点の一つ。
bash
#! /bin/bash queue=() while IFS=$'\n' read line ; do num=$(echo ${line} | sed -e 's/^\([+-]*[0-9][0-9]*\).*/\1/') num=$((num+0)) queue=("${queue[@]}" ${num}) done while [ ${#queue[@]} -gt 0 ]; do echo ${queue[0]} queue=("${queue[@]:1}") done
あえて配列を使って書いたが、65536行のデータを食わせたら全然返ってこなかったので、大量のデータを処理する際には素直に他の言語で書いた方が良い。 あと、キューからの取り出しが面倒だったので、他の言語と違って、「末尾に追加」「先頭から削除」という形になっているので注意。
