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

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

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

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

前回と要件ややることは一緒だが、Stack構造を扱ってみようというのが今回の目的。

環境

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

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

-2147483648
2147483647
-32768
32768
-256
256
-1
1
0

Java

import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Deque;
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)
        ) {
            Deque<Integer> stack = new ArrayDeque<>();

            while (in.hasNextInt()) {
                stack.push(in.nextInt());
            }

            while (stack.peek() != null) {
                out.println(stack.pop());
            }
        }
    }
}

Javaには、Stackとして使えるjava.util.Dequeの実装クラスがあるので、それを使って簡単に書ける。

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int capacity;
    int size;
    int* elemData;
} IntStack;

IntStack* IntStack_new(int capacity) {
    IntStack* stack = (IntStack*)calloc(sizeof(IntStack), 1);
    stack->elemData = (int*)calloc(sizeof(int), capacity);
    stack->capacity = capacity;
    stack->size = 0;
    return stack;
}
void IntStack_destroy(IntStack* stack) {
    free(stack->elemData);
    free(stack);
}
int IntStack_isEmpty(IntStack* stack) {
    return stack->size == 0;
}
void IntStack_push(IntStack* stack, int elem) {
    if (stack->size + 1 > stack->capacity) {
        int newCapacity = stack->capacity * 2;
        int* newElemData = (int*)calloc(sizeof(int), newCapacity);
        memcpy(newElemData, stack->elemData, sizeof(int) * stack->size);
        free(stack->elemData);
        stack->elemData = newElemData;
        stack->capacity = newCapacity;
    }

    stack->elemData[(stack->size)++] = elem;
}
int IntStack_pop(IntStack* stack) {
    return stack->elemData[--(stack->size)];
}

int main(int argc, char** argv) {
    IntStack* stack = IntStack_new(256);

    int num;
    while (scanf("%ld", &num) == 1) {
        IntStack_push(stack, num);
    }

    while (!IntStack_isEmpty(stack)) {
        printf("%d\n", IntStack_pop(stack));
    }

    IntStack_destroy(stack);

    return 0;
}

C言語は当然自前実装。

C++

#include <algorithm>
#include <iostream>
#include <stack>

using namespace std;

int main(int argc, char** argv) {
    stack<int> stack;
    int num;

    while (cin >> num) {
        stack.push(num);
    }

    while (!stack.empty()) {
        cout << stack.top() << endl;
        stack.pop();
    }

    return EXIT_SUCCESS;
}

C++にはstackがあるので、それを使って簡単に書ける。

PHP

<?php

class Stack {
    private $elemData = array();
    public function isEmpty() {
        return count($this->elemData) === 0;
    }
    public function push($value) {
        array_push($this->elemData, $value);
    }
    public function pop() {
        $value = array_pop($this->elemData);
        return $value;
    }
}

$lines = file('php://stdin');

$stack = new Stack();

foreach ($lines as $line) {
    $stack->push((int)$line);
}

while (!$stack->isEmpty()) {
    printf("%d\n", $stack->pop());
}

PHPには標準ではStackクラスが無いので書いてみた。単なる配列のラッパー。

Python 2

import sys

class Stack:
    elemData = []
    def push(self, value):
        self.elemData.append(value)
    def pop(self):
        return self.elemData.pop()
    def isEmpty(self):
        return len(self.elemData) == 0

stack = Stack()
while True:
    line = sys.stdin.readline()
    if line == '':
        break
    stack.push(int(line))

while stack.isEmpty() != True:
    print stack.pop()

Python 2ではStackクラスが見当たらなかったので書いてみた。単なる配列のラッパー。

Python 3

import sys

class Stack:
    elemData = []
    def push(self, value):
        self.elemData.append(value)
    def pop(self):
        return self.elemData.pop()
    def isEmpty(self):
        return len(self.elemData) == 0

stack = Stack()
while True:
    line = sys.stdin.readline()
    if line == '':
        break
    stack.push(int(line))

while stack.isEmpty() != True:
    print(stack.pop())

Python 3ではStackクラスが見当たらなかったので書いてみた。単なる配列のラッパー。

Ruby

class Stack
    def initialize
        @elemData = []
    end
    def push(value)
        @elemData.push(value)
    end
    def pop
        @elemData.pop
    end
    def isEmpty
        return @elemData.size == 0
    end
end

stack = Stack.new
while line = STDIN.gets
    num = line.to_i
    stack.push(num)
end

while !stack.isEmpty
    print stack.pop(),"\n"
end

RubyではStackクラスが見当たらなかったので書いてみた。単なる配列のラッパー。

Perl

Perlにはpush/pop関数があるということだが、なんか微妙なので、2パターン書いてみた。

push/pop関数バージョン

my @stack = ();

my $line;
while ($line = readline(STDIN)) {
    my $num = $line + 0;
    push @stack, $num;
}

while ($#stack + 1 > 0) {
    my $value = @stack[$#stack];
    pop @stack;
    print "$value\n";
}

Stackモジュールバージョン

Stack.pm

package Stack;

sub new {
    my %self;
    my $class = shift;
    $self->{elemData} = ();
    $self->{size} = 0;
    return bless $self, $class;
}
sub push {
    my $self = shift;
    my $value = shift;
    $self->{elemData}[$self->{size}] = $value;
    ++$self->{size};
}
sub top {
    my $self = shift;
    return $self->{elemData}[$self->{size} - 1];
}
sub pop {
    my $self = shift;
    --$self->{size};
    delete $self->{elemData}[$self->{size}];
}
sub isEmpty {
    my $self = shift;
    return $self->{size} == 0;
}

1;

Main.pl

require "Stack.pm";

my $stack = Stack->new;

my $line;
while ($line = readline(STDIN)) {
    my $num = $line + 0;
    $stack->push($num);
}

while (!$stack->isEmpty()) {
    my $value = $stack->top();
    $stack->pop();
    print "$value\n";
}

Go

listをスタック代わりに直接使うということを考えたが、せっかくなので、Stackパッケージを作ってみた。

src/stack/stack.go

package stack;

import (
    "container/list"
)

type Stack struct {
    elemData *list.List
}

func (s *Stack) Init() *Stack {
    s.elemData = list.New()
    return s
}

func New() *Stack {
    return new(Stack).Init()
}

func (s *Stack) Push(v interface{}) {
    s.elemData.PushBack(v)
}

func (s *Stack) Pop() interface{} {
    e := s.elemData.Back()
    s.elemData.Remove(e)
    return e.Value
}

func (s *Stack) IsEmpty() bool {
    return s.elemData.Len() == 0
}

Main.go

package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "strconv"
    "stack"
)

func main() {
    aStack := stack.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)

        aStack.Push(num)
    }

    for !aStack.IsEmpty() {
        fmt.Println(aStack.Pop())
    }
}

実行するときに、GOPATH=$(pwd) go run Main.goってしてやらないと、カレントディレクトリのソースを参照してくれないのでちょっとハマった。

bash

#! /bin/bash

stack=()

while IFS=$'\n' read line ; do
    num=$(echo ${line} | sed -e 's/^\([+-]*[0-9][0-9]*\).*/\1/')
    num=$((num+0))
    stack=(${num} "${stack[@]}")
done

while [ ${#stack[@]} -gt 0 ]; do
    echo ${stack[0]}
    stack=("${stack[@]:1}")
done

あえて配列を使って書いたが、65536行のデータを食わせたら全然返ってこなかったので、大量のデータを処理する際には素直に他の言語で書いた方が良い。