• 空スタック生成: (empty-stack)
• 先頭要素取得: (top stk)
• push(immutable): (push stk value)
• push(mutable): (push! stk value)
• pop(immutable): (pop stk)
• pop(mutable): (pop! stk)
• リスト変換: (stack->list stk)
• 空スタック？: (stack-empty? stk)
• スタック長: (stack-length stk)

> (require typed-stack)
> (define stk (empty-stack))
> stk
(Stack '())
> (push stk 0)
(Stack '(0))
> (push! stk 0)
> stk
(Stack '(0))
> (push stk 1)
(Stack '(1 0))
> (push! stk 1)
> stk
(Stack '(1 0))
> (push stk 2)
(Stack '(2 1 0))
> (push! stk 2)
> stk
(Stack '(2 1 0))
> (stack->list stk)
'(2 1 0)
> (top stk)
2
> (pop stk)
2
(Stack '(1 0))
> (pop! stk)
2
> (pop stk)
1
(Stack '(0))
> (pop! stk)
1
> (pop stk)
0
(Stack '())
> (pop! stk)
0
> stk
(Stack '())
> (stack-empty? stk)
#t
> (stack-length stk)
0

• 空スタック生成: Stack.create
• 先頭要素取得: Stack.top stk
• push(mutable): Stack.push value stk
• pop(mutable): Stack.pop stk
• 空スタック？: Stack.is_empty stk
• スタック長: Stack.length stk

# let stk = Stack.create ();;
val stk : '_weak1 Stack.t = 
# Stack.push 0 stk;;
- : unit = ()
# Stack.push 1 stk;;
- : unit = ()
# Stack.push 2 stk;;
- : unit = ()
# Stack.top stk;;
- : int = 2
# Stack.length stk;;
- : int = 3
# Stack.pop stk;;
- : int = 2
# Stack.pop stk;;
- : int = 1
# Stack.pop stk;;
- : int = 0
# Stack.length stk;;
- : int = 0
# Stack.is_empty stk;;
- : bool = true

C++

OCaml

Racket

• 空スタック:stkを作る。
• pushをn回繰り返し、stkの長さを見る。
• popをn回繰り返し、stkが空になったことを見る。

C++

#include <chrono>
#include <print>
#include <stack>
#include <stdexcept>
 
void test(long n) {
  // push
  auto start = std::chrono::high_resolution_clock::now();
  std::stack<long> stk;
  for (long i = 0l; i < n; ++i)
    stk.push(i);
  auto end = std::chrono::high_resolution_clock::now();
  std::chrono::duration<double> duration = end - start;
  std::println("length = {}", stk.size());
  std::println("push time:  {:9.6f} [sec]", duration.count());
  // pop
  start = std::chrono::high_resolution_clock::now();
  while (!stk.empty())
    stk.pop();
  end = std::chrono::high_resolution_clock::now();
  duration = end - start;
  std::println("length = {}", stk.size());
  std::println("pop time:   {:9.6f} [sec]", duration.count());
}
 
int main(int argc, char *argv[]) {
  try {
    if (argc != 2) {
      throw std::invalid_argument(
          "Usage: stack <positive integer>");
    }
    long n = std::stol(argv[1]);
    if (n <= 0l) {
      throw std::invalid_argument(
          "The argument must be a positive integer.");
    }
    test(n);
  } catch (const std::logic_error &e) {
    std::println(stderr, "Logic error: {}", e.what());
  } catch (const std::runtime_error &e) {
    std::println(stderr, "Runtime error: {}", e.what());
  } catch (const std::exception &e) {
    std::println(stderr, "Another std::exception: {}", e.what());
  } catch (...) {
    std::println(stderr, "Unknown exception.");
  }
  return 0;
}

CPPG = g++
CPPL = clang++
CPPFLAGS = -std=c++23 -O2
SRC = stack.cpp
EXES = stack_g stack_l
 
all: $(EXES)
 
stack_g: $(SRC)
	$(CPPG) $(CPPFLAGS) -o $@ $(SRC)
 
stack_l: $(SRC)
	$(CPPL) $(CPPFLAGS) -o $@ $(SRC)
 
clean:
	rm -f $(EXES)

$ measure ./stack_g 10000000
length = 10000000
push time:   0.060265 [sec]
length = 0
pop time:    0.014986 [sec]
======================================
Process exited with status: 0
total time:  0.084146 [sec]
mem  size:      84944 [KB]
code size:        128 [KB]

$ measure ./stack_l 10000000
length = 10000000
push time:   0.083953 [sec]
length = 0
pop time:    0.018322 [sec]
======================================
Process exited with status: 0
total time:  0.110900 [sec]
mem  size:      84992 [KB]
code size:        101 [KB]

OCaml

open Printf
 
let test n =
  (* push *)
  let start = Unix.gettimeofday () in
  let stk = Stack.create () in
  for i = 0 to n - 1 do
    Stack.push i stk
  done;
  let end_ = Unix.gettimeofday () in
  printf "length = %d\n" (Stack.length stk);
  printf "push time:  %9.6f [sec]\n" (end_ -. start);
  (* pop *)
  let start = Unix.gettimeofday () in
  while not (Stack.is_empty stk) do
    ignore (Stack.pop stk)
  done;
  let end_ = Unix.gettimeofday () in
  printf "length = %d\n" (Stack.length stk);
  printf "pop time:   %9.6f [sec]\n" (end_ -. start)
 
let () =
  try
    if Array.length Sys.argv <> 2 then
      raise (Invalid_argument
        "Usage: stack <positive integer>")
    else
      let n = int_of_string Sys.argv.(1) in
      if n <= 0 then
        raise (Invalid_argument
          "The argument must be a positive integer.")
      else
        test n
  with
    | Invalid_argument msg ->
        eprintf "Logic error: %s\n" msg
    | Failure msg ->
        eprintf "Runtime error: %s\n" msg
    | exn ->
        eprintf "Another exception: %s\n" (Printexc.to_string exn)

OCAMLOPT = ocamlopt
OCAMLFLAGS = -O2
LIBPATH = -I +unix
LIBS = unix.cmxa
SRC = stack.ml
EXES = stack
 
all: $(EXES)
 
stack: $(SRC)
	$(OCAMLOPT) $(OCAMLFLAGS) $(LIBPATH) -o $@ $(LIBS) $(SRC)
 
clean:
	rm -f $(EXES) *.o *.cmx *.cmi

$ measure ./stack 10000000
length = 10000000
push time:   0.630650 [sec]
length = 0
pop time:    0.598853 [sec]
======================================
Process exited with status: 0
total time:  1.251666 [sec]
mem  size:     288556 [KB]
code size:       3298 [KB]

Racket

#lang racket
(require iso-printf)
(require typed-stack)
 
(define (test n)
  ; push
  (define start (current-inexact-milliseconds))
  (define stk (empty-stack))
  (for ([i (in-range n)])
    (push! stk i))
  (define end (current-inexact-milliseconds))
  (printf "length = %d\n" (stack-length stk))
  (printf "push time:  %9.6f [sec]\n" (/ (- end start) 1000.0))
  ; pop
  (set! start (current-inexact-milliseconds))
  (let loop ()
    (unless (stack-empty? stk)
      (pop! stk)
      (loop)))
  (set! end (current-inexact-milliseconds))
  (printf "length = %d\n" (stack-length stk))
  (printf "pop time:   %9.6f [sec]\n" (/ (- end start) 1000.0)))
 
(define (main args)
  (with-handlers
    ([exn:fail? (λ (e) (eprintf "%s\n" (exn-message e)))]
     [exn? (λ (e) (eprintf "Unexpected: %s\n" (exn-message e)))])
  (cond
    [(not (= (vector-length args) 1))
      (error "Usage: stack <positive integer>")]
    [else
      (let ([n (string->number (vector-ref args 0))])
        (cond
          [(not (integer? n))
            (error "The argument must be an integer.")]
          [(<= n 0)
            (error "The argument must be a positive integer.")]
          [else
            (test n)]))])))
 
(main (current-command-line-arguments))

$ raco exe stack.rkt
$ measure ./stack 1000
length = 1000
push time:   0.395930 [sec]
length = 0
pop time:    0.950207 [sec]
======================================
Process exited with status: 0
total time:  2.315375 [sec]
mem  size:     218884 [KB]
code size:      25841 [KB]

Racket

#lang racket
(require iso-printf)
 
(define (make-stack)
  (box '()))
 
(define (push! stack item)
  (set-box! stack (cons item (unbox stack))))
 
(define (pop! stack)
  (let ([current-stack (unbox stack)])
    (if (null? current-stack)
        (error "Cannot pop from an empty stack")
        (begin
          (set-box! stack (cdr current-stack))
          (car current-stack)))))
 
(define (top stack)
  (let ([current-stack (unbox stack)])
    (if (null? current-stack)
        (error "Cannot peek into an empty stack")
        (car current-stack))))
 
(define (stack-empty? stack)
  (null? (unbox stack)))
 
(define (stack-length stack)
  (length (unbox stack)))
 
(define (test n)
  ; push
  (define start (current-inexact-milliseconds))
  (define stk (make-stack))
  (for ([i (in-range n)])
    (push! stk i))
  (define end (current-inexact-milliseconds))
  (printf "length = %d\n" (stack-length stk))
  (printf "push time:  %9.6f [sec]\n" (/ (- end start) 1000.0))
  ; pop
  (set! start (current-inexact-milliseconds))
  (let loop ()
    (unless (stack-empty? stk)
      (pop! stk)
      (loop)))
  (set! end (current-inexact-milliseconds))
  (printf "length = %d\n" (stack-length stk))
  (printf "pop time:   %9.6f [sec]\n" (/ (- end start) 1000.0)))
 
(define (main args)
  (with-handlers
    ([exn:fail? (λ (e) (eprintf "%s\n" (exn-message e)))]
     [exn? (λ (e) (eprintf "Unexpected: %s\n" (exn-message e)))])
  (cond
    [(not (= (vector-length args) 1))
      (error "Usage: stack2 <positive integer>")]
    [else
      (let ([n (string->number (vector-ref args 0))])
        (cond
          [(not (integer? n))
            (error "The argument must be an integer.")]
          [(<= n 0)
            (error "The argument must be a positive integer.")]
          [else
            (test n)]))])))
 
(main (current-command-line-arguments))

$ raco exe stack2.rkt
$ measure ./stack2 10000000
length = 10000000
push time:   0.534337 [sec]
length = 0
pop time:    0.070072 [sec]
======================================
Process exited with status: 0
total time:  1.171759 [sec]
mem  size:     294452 [KB]
code size:      12445 [KB]