§2. ArrayStack/ArrayQueue/ArrayDeque

ArrayStack

ArrayStackはbacking arrayを使ったListインターフェース

get(i)およびset(i, x)の実行時間はO(1)，

add(i, x)およびremove(i)の実行時間はO(1+n-i)

add(n, x)はpush(x),

remove(n-1)はpop()

code:arraystack.cpp

T get(int i) {

return ai;

}

T set(int i, T x) {

T y = ai;

ai = x;

return y;

}

void add(int i, T x){

if (n+1 >= a.length) resize();

for (int j = n; j>i; j--)

aj = aj-1;

ai = x;

n++;

}

T remove(int i){

T x = ai;

for (int j = i; j < n - 1; j++)

aj = aj+i;

n--;

if (a.length >= 3*n) resize();

return x;

}

void resize(){

array<T> b(max(2*n, 1));

for (int i = 0; i < n; i++)

bi = ai;

a = b;

}

ArrayQueue

Queueインターフェースの実装．一方の端からは追加を，他方の端からは削除を効率的に行うような列を表すデータ構造．resize()コストを無視するとArrayQueueはadd(x), remove()の実行時間はO(1)になる．また空のArrayQueueに対して長さmの任意のadd(x)およびremove()からなる操作の列を実行する時，resize()にかかる時間の合計はO(m)になる

code:arrayqueue.cpp

array<T> a;

int j;

int n;

bool add(T x) {

if(n + 1 >= a.length) resize();

a(j+n) % a.length = x;

n++;

return true;

}

T remove(){

T x = aj;