手元にある各言語で、標準入力からの数値列をQueueに放り込んで、入力と同順になるように標準出力に吐き出すプログラムを書いてみようと思ったメモ。
標準入力から入力される数値列の要件は以下の通り。
- 1行に1つの数値が書かれている
- いくつの数値が入力されるかは不明（ただし、メモリがあふれることが無い程度に手加減する）
- 入力される数値は符号付32ビット整数とする
入力をそのまま標準出力に放り出せばいいじゃないかという突っ込みもあるだろうが、Queue構造を扱ってみようというのが今回の目的。
環境
手元にあるものということで、環境は以下のものに限定する。
入力ファイルの例
0
1
-1
256
-256
32768
-32768
2147483647
-2147483648
期待される出力の例
0
1
-1
256
-256
32768
-32768
2147483647
-2147483648
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言語は当然自前実装。
#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
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を使わずに、先頭のインデックスを持っておいてインクリメントしていく方がいいのかも。
(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()
(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())
(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には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ってしてやらないと、カレントディレクトリのソースを参照してくれないのは注意点の一つ。
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行のデータを食わせたら全然返ってこなかったので、大量のデータを処理する際には素直に他の言語で書いた方が良い。
あと、キューからの取り出しが面倒だったので、他の言語と違って、「末尾に追加」「先頭から削除」という形になっているので注意。
