この章について

「スタックとキュー」というタイトルになっています。問題数は少ないが果たして。

Question 3.1

1つの配列を使って3つのスタックを実装するにはどのようにすればよいのか述べてください。

この手の実装に慣れていなさすぎる。とりあえずできるだけのことはした。
コードにもあるように、stackで(個人的に)よく使うpush,pop,empty,top,sizeのみを実装した。
入力した整数$n(\ge 0)$に対し、要素数が$3n$の配列を確保する。
$0 \le index < n$にstack1、$n \le index < 2n$にstack2、$2n \le index < 3n$にstack3を割り当てる。なのでこの実装だと各stackに最大$n$個の要素しか格納できないのがざんねん。

3-1.cpp

#include<stack>
#include<iostream>
using namespace std;

//push,pop,empty,top,sizeだけ実装しておく

class ThreeStacks{
    private:
    int Capacity;
    int *stacks;
    int index1, index2, index3;

    public:
    ThreeStacks(int Size){
        Capacity = Size;
        stacks = new int[3 * Capacity];
        //各stackの最初の添字
        index1 = 0;
        index2 = Capacity;
        index3 = 2 * Capacity;
    }

    bool empty1(){
        return (index1==0);
    }

    bool empty2(){
        return (index2==Capacity);
    }

    bool empty3(){
        return (index3==2 * Capacity);
    }

    void push1(int n){
        if(index1==Capacity){
            cout<<"Stack 1 is full"<<endl;
        }
        else{
            stacks[index1] = n;
            index1++;
        }
    }

    void push2(int n){
        if(index2==2 * Capacity){
            cout<<"Stack 2 is full"<<endl;
        }
        else{
            stacks[index2] = n;
            index2++;
        }
    }

    void push3(int n){
        if(index3==3 * Capacity){
            cout<<"Stack 3 is full"<<endl;
        }
        else{
            stacks[index3] = n;
            index3++;
        }
    }

    void top1(){
        if(index1 > 0){cout<<stacks[index1 - 1]<<endl;}
        else{cout<<"Stack 2 is empty"<<endl;}

    }

    void top2(){
        if(index2 > Capacity){cout<<stacks[index2 - 1]<<endl;}
        else{cout<<"Stack 2 is empty"<<endl;}

    }

    void top3(){
        if(index3 > 2 * Capacity){cout<<stacks[index3 - 1]<<endl;}
        else{cout<<"Stack 3 is empty"<<endl;}

    }

    void pop1(){
        stacks[index1] = 0;//わからないので0に置き換えることにした
        index1--;
    }

    void pop2(){
        stacks[index2] = 0;
        index2--;
    }

    void pop3(){
        stacks[index3] = 0;
        index3--;
    }

    int size1(){
        return index1;
    }

    int size2(){
        return index2 - Capacity;
    }

    int size3(){
        return index3 - 2 * Capacity;
    }
};

Question 3.2

pushとpopに加えて、最小の要素を返す関数minを持つスタックをどのようにデザインしますか？ただしpush,pop,min関数はすべてO(1)の実行時間になるようにしてください。

push,popの計算時間は償却計算時間(平均して$O(1)$とみなせる?)らしいのでminの計算時間を$O(1)$にするのが本質っぽい？
そういうわけでこれを目指して書きます。

まず、stackが空の状態からminを保持するのは簡単だが、状態の変化によっては普通の値の持ち方ではstackのminを定数時間で求められなくなる。
例)
8つ値をpushして stack = {5, 4, 6, 8, 7, 3, 9, 3} とする(min = 3)
$\rightarrow$3つ値をpopして stack = {5, 4, 6, 8, 7} とする。
このとき、2行目の操作の後のstackのminは4だが、どこにもその値を保持してないので再計算する必要がある。これはもちろんstackを走査しないとわからないので計算量は$O(N)$となる。

$\rightarrow$もう一つのstack(=minkeep)を用意する。最小値が更新されたとき、最小値と等しい値がpushされた時のみこのstackにその値をpush。
また、stackからpopする値とminkeep.top()が等しいとき、その値を同時にminkeepからもpopする。
上の例でいくと、minkeepにpushされる値は順に5, 4, 3, 3となるのでminkeep = {5, 4, 3, 3}
次にstackから3, 9, 3を順にpopするので、minkeepからは3, 3がpopされ、minkeep = {5, 4}になる。
このとき、minkeepは常にそのときの最小値を保持していたのでminkeep.top()が現在のstackの状態に対する最小値を与えることになる。

一部メンバ関数端折って実装してみた。

3-2.cpp

#include<stack>
#include<limits>
#include<iostream>

using namespace std;

class StackWithMin{
    private:
    stack<int> stck;
    stack<int> minkeep;
    int minvalue;

    public:
    StackWithMin(stack<int> st){
        stck = st;
        minvalue = numeric_limits<int>::max();
    }

    void PUSH(int n){
        stck.push(n);
        if(n <= minvalue){
            minkeep.push(n);
            minvalue = n;
        }
    }

    void POP(){
        if(stck.top()==minkeep.top()){minkeep.pop();}
        stck.pop();
    }

    int TOP(){
        return stck.top();
    }

    bool EMPTY(){
        return stck.empty();
    }

    int MIN(){
        return minkeep.top();
    }
};

Question 3.3

皿が積み上がっている状況をイメージしてください。もし、高く積み上がりすぎたら倒れてしまうでしょう。ですから、実生活ではスタックがある領域を超えたとき、新しいスタックを用意することになるでしょう。これをまねたデータ構造SetOfStacksを実装してください。SetOfStacksはいくつかのスタックを持ち、スタックのデータがいっぱいになったらスタックを新たに作らなければなりません。また、SetOfStacks.push()とSetOfStacks.pop()は普通のスタックのようにふるまうようにしてください。(つまり、pop()は通常の1つのスタックの場合と同じ値を返さなければなりません)。

stackを一杯になった順に管理しないといけないので、listで管理することにした。listのsizeがいくつまで増えるか分からないことを考えると、vectorや配列で管理するより良さそう。

3-3.cpp

#include<stack>
#include<list>
#include<forward_list>
#include<iostream>
using namespace std;

class SetOfStacks{
    private:
    int Capa;
    list<stack<int>> stacklist;
    stack<int> EmptyStack;//新しいスタックを生成するときの空のスタック
    stack<int> NowStack;//常にここに積んでいき、いっぱいになったらstacklistにemplace_back

    public:
    SetOfStacks(int Capacity){
        Capa = Capacity;
    }

    void PUSH(int n){
        NowStack.push(n);
        //スタックがいっぱいになった時に次のスタックを用意
        if(NowStack.size() == Capa){
            stacklist.emplace_back(NowStack);
            NowStack = EmptyStack;
            }
    }

    void POP(){
        if((NowStack == EmptyStack)&&(stacklist.begin() == stacklist.end()));//何もしない
        
        //今見てるスタックは空だが、stacklistには1つ以上のスタックが並んでいるとき
        //stacklistの一番後ろにあるスタックのtop()が最新の値を返す
        else if(NowStack == EmptyStack){
            list<stack<int>>::iterator End = stacklist.end();
            End--;
            NowStack = *End;
            NowStack.pop();
            stacklist.pop_back();
        }
        else{
            NowStack.pop();
        }
    }

    int TOP(){
        //POP()と同様の場合分け
        if((NowStack == EmptyStack)&&(stacklist.begin() == stacklist.end())){
            return 0;//0を返しておく
        }
        else if(NowStack == EmptyStack){
            list<stack<int>>::iterator End = stacklist.end();
            End--;
            return (*End).top();
        }
        else{
            return NowStack.top();
        }
    }

    bool EMPTY(){
        //今見てるスタックもstacklistも空のときのみtrue
        return (NowStack == EmptyStack && stacklist.begin()== stacklist.end());
    }
};

Question 3.4

MyQueueというクラス名で、2つのスタックを用いてキューを実装してください。

これも一部関数(push, pop, front, empty)のみ実装。
ご存知stackは後入れ先出し、queueは先入れ先出しというのが一番の違いで、ここをどう実装するかになる。
つまりstackでは一番最初にpushした要素が、いわゆる一番奥にあるのでそこへのアクセスを実現させなければならない。
1つのアイデアとして、2つのstack(ここではOrderedStack, ReversedStackという名前)を用意する。

値をpushする時はOrderedStackに"普通に"積み続ける。

MyQueueの先頭の要素にアクセス(FRONT())したいとき、関数REVERSE()でOrderedStackの中身をReversedStackに上から順に移すことで、ReversedStackの一番上に積んである要素がMyQueue.FRONT()の値となる。

POP()はこの値をpopするだけなのでそのまま。

また、この実装の仕方から、MyQueueはOrderedStack, ReversedStackの2つが同時に空の時のみ空であるとわかるので、EMPTY()は以下のような実装になる。

3-4.cpp

#include<stack>
#include<iostream>
using namespace std;

class MyQueue{
    private:
    stack<int> OrderedStack;
    stack<int> ReversedStack;

    /*OrderedStackの中身をReversedStackに上から積んでいくことで
     *最初にpushした要素がReversedStackの一番上に来る*/
    void REVERSE(){
        //ReversedStackが空でないとき、すでに一番古い要素がReversedStackの一番上にある
        if(ReversedStack.empty()){
            //空なら全部逆順にするために1つずつ積んでいく
            while(!OrderedStack.empty()){
                ReversedStack.push(OrderedStack.top());
                OrderedStack.pop();
            }
        }
    }

    public:
    void PUSH(int n){
        OrderedStack.push(n);
    }

    void POP(){
        REVERSE();
        ReversedStack.pop();
    }

    int FRONT(){
        REVERSE();
        return ReversedStack.top();
    }

    bool EMPTY(){
        //同時に空でないといけない
        return !(OrderedStack.size()+ReversedStack.size());
    }
};

Question 3.5

最も小さい項目がトップに来るスタックを並べ替えるプログラムを書いてください。別のスタックを1つ用意してもかまいません。スタック以外のデータ構造(配列など)にスタック上のデータをコピーしてはいけません。また、スタックは以下の操作のみ使用できます。
push, pop, top, empty

(赤字の部分は、本では"peek", "isEmpty"だったが、今回はC++なのでC++でのstackのメンバ関数名に書き直した。)

stackを3つ用意できればハノイの塔みたいに並べ換えることもできそうだなあと思った。
しかし今回はstackが2つしか使えない。それにハノイの塔だと最悪計算量が$O(2^N)$ぐらいになる気がするのでどっちにしろ不採用。

バブルソート的な実装となった。
void型にしたらなぜかソートしてくれなかったのでメモリの使用量が増えてざんねん。計算量は$O(N^2)$

3-5.cpp

#include<stack>
#include<iostream>
using namespace std;

stack<int> SortStack(stack<int> st){
    stack<int> keep,ret;
    ret = st;
    //keep.top()が変な値を返さないように先にひとつpushしておく
    keep.push(ret.top());
    ret.pop();

    while(!ret.empty()){
        int tmp = ret.top();//この値がどこに入るかを順に調べていく
        ret.pop();

        while(!keep.empty() && keep.top() > tmp){
            ret.push(keep.top());
            keep.pop();
        }
        keep.push(tmp);
    }

    //keepに降順に値が並んでいるのでretに上からpushすると昇順になる
    while(!keep.empty()){
        ret.push(keep.top());
        keep.pop();
    }
        
    return ret;
}

Question 3.6

イヌとネコしか入ることのできない動物保護施設があります。この施設は「先入れ先出し」の操作を厳格に行います。施設からは一番長い時間入っている動物を外に出すか、イヌとネコの好きなほう(で一番長い時間入っているもの)を外に出すことができます。どの動物でも好きなように連れ出せるわけではありません。このような仕組みを扱うデータ構造を作ってください。さらにenqueue, dequeueAny, dequeueDog, dequeueCatの操作を実装してください。あらかじめ用意された連結リストのデータ構造は用いてよいものとします。

そのまま書けばよさそう。メンバ関数の型とか引数の取り方は好み(?)
Orderという名のlistを作り、犬が格納されたら0、猫が格納されたら1をemplace_backする。
こうすることで、犬と猫が格納された順番を持っておける。動物の合計数が少なそうだったらint型整数のbitを立てたりしてもこの順番は持てるので、その辺も条件次第。

3-6.cpp

#include<queue>
#include<list>
#include<iostream>
using namespace std;

class AnimalShelter{

    private:
    list<int> Order;
    queue<string> DogShelter;
    queue<string> CatShelter;
    
    public:
    void enqueue(int num,string animal){
        //numの偶奇で犬か猫か識別
        if(num%2 == 0){
            DogShelter.push(animal);
        }

        else if(num%2 == 1){
            CatShelter.push(animal);
        }
        //num%2を格納しておけば犬と猫が格納された順がわかる
        Order.emplace_back(num%2);
    }

    string dequeAny(){
        string ret;

        if(Order.front() == 0){
            ret = DogShelter.front();
            DogShelter.pop();
        }

        else if(Order.front() == 1){
            ret = CatShelter.front();
            CatShelter.pop();
        }

        Order.pop_front();

        return ret;
    }

    string dequeDog(){
        string ret = DogShelter.front();
        DogShelter.pop();
        return ret;
    }

    string dequeCat(){
        string ret = CatShelter.front();
        CatShelter.pop();
        return ret;
    }
};