各言語でQueue - HHeLiBeXの日記正道編

手元にある各言語で、標準入力からの数値列をQueueに放り込んで、入力と同順になるように標準出力に吐き出すプログラムを書いてみようと思ったメモ。

標準入力から入力される数値列の要件は以下の通り。

1行に1つの数値が書かれている
- 不正入力のチェックは不要とする
いくつの数値が入力されるかは不明（ただし、メモリがあふれることが無い程度に手加減する）
入力される数値は符号付32ビット整数とする

入力をそのまま標準出力に放り出せばいいじゃないかという突っ込みもあるだろうが、Queue構造を扱ってみようというのが今回の目的。

環境

手元にあるものということで、環境は以下のものに限定する。

CentOS 7
- Java (openjdk version "1.8.0_151")
- C (gcc (GCC) 4.8.5)
  - -std=gnu11でコンパイル
- C++ (g++ (GCC) 4.8.5)
  - -std=gnu++1yでコンパイル
- PHP (PHP 5.4.16 (cli))
- Python 2 (Python 2.7.5)
- Python 3 (Python 3.6.3)
  - ソースからビルドしたもの
- Ruby (ruby 2.0.0p648)
- Perl (v5.16.3)
- Go (go version go1.8.3 linux/amd64)
- bash (4.2.46(1)-release)

入力ファイルの例

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行のデータを食わせたら全然返ってこなかったので、大量のデータを処理する際には素直に他の言語で書いた方が良い。あと、キューからの取り出しが面倒だったので、他の言語と違って、「末尾に追加」「先頭から削除」という形になっているので注意。