【メモ】

スタック:後進先出LIFO
キュー:FIFO先出

template<typename ITEM>
class stack {
private:
    ITEM S[MAXN];
    int tp;
public:
    stack() {
        tp = 0;
    }
    bool empty() {
        return tp == 0;
    }
    void push(ITEM x) {
        if (tp == MAXN) throw "stack overflow";
        S[tp++] = x;
    }
    ITEM top() {
        if (tp == 0) throw "stack empty";
        return S[tp-1];
    }
    void pop() {
        if (tp == 0) throw "stack underflow";
        tp--;
    }
    int size() {
        return tp;
    }
};

template<typename ITEM>
class queue {
private:
    ITEM Q[MAXN];
    int head,tail;
    int sz;
public:
    queue() {
        head = tail = sz = 0;
    }
    bool empty() {
        return sz == 0;
    }
    void push(ITEM x) {
        if (sz == MAXN) throw "queue overflow";
        Q[tail++] = x;
        sz++;
        if (tail == MAXN) tail = 0;
    }
    ITEM front() {
        if (sz == 0) throw "queue empty";
        return Q[head];
    }
    void pop() {
        if (sz == 0) throw "queue underflow";
        head++;
        sz--;
        if (head == MAXN) head = 0;
    }
    int size() {
        return sz;
    }
};

【練習】

10.1−1は、配列S[1..6]に格納された、最初は空のスタックSに対して、PUSH(S,4)、PUSH(S,1)、PUSH(S,3)、POP(S)、PUSH(S,8)、およびPOP(S)操作を順次実行した結果を説明する.
4 1 3
4 1
4 1 8
POPは3を返す
10.1-2は、2つのスタックの要素の合計数がn未満の場合、両方ともオーバーフローしないように、1つの配列A[1..n]で2つのスタックを実現する方法を説明する.注意PUSHとPOPの操作時間はO(1)であること.
2つのスタックはそれぞれA[1]とA[n]でスタックの底を作り,PUSH操作時には中間に要素を挿入し,2つのスタック要素の総数がnのときに配列がいっぱいになり,オーバーフローが発生する.
10.1−3は、配列Q[1..6]に格納された、最初は空のキューQに対して、ENQUEUE(Q,4)、ENQUEUE(Q,1)、ENQUEUE(Q,3)、DEQUEUE(Q)、ENQUEUE(Q,8)、およびDEQUEUE(Q)の動作を順次実行した結果を説明する.
4
4 1
4 1 3
1 3
1 3 8
DEQUEUE(Q)は4を返す
10.1-4 ENQUEUEとDEQUEUEを書き換え、キューのオーバーフローとオーバーフローを処理できるようにする.
コードを参照してください.
10.1-5スタックの挿入と削除はいずれも一端で行われ、キューの挿入と削除は確かに両端で行われる.両端に挿入と削除が可能な両端キューもあります.配列で構成された両端キューについて、両端で挿入と削除操作を行う4つのプロセスを書き出し、実行時間がO(1)であることを要求します.

template <typename ITEM>
class deque {
private:
    ITEM D[MAXN];
    int head,tail;
    int sz;
public:
    deque() {
        head = tail = 0;
        sz = 0;
    }
    bool empty() {
        return sz == 0;
    }
    ITEM front() {
        if (sz == 0) throw "deque empty";
        return D[head];
    }
    ITEM back() {
        if (sz == 0) throw "deque empty";
        return D[tail-1];
    }
    void push_front(ITEM x) {
        if (sz == MAXN) throw "deque overflow";
        if (head == 0) head = MAXN;
        head--;
        sz++;
        D[head] = x;
    }
    void push_back(ITEM x) {
        if (sz == MAXN) throw "deque overflow";
        D[tail++] = x;
        sz++;
        if (tail == MAXN) tail = 0;
    }
    void pop_front() {
        if (sz == 0) throw "deque underflow";
        head++;
        if (head == MAXN) head = 0;
        sz--;
    }
    void pop_back() {
        if (sz == 0) throw "deque underflow";
        if (tail == 0) tail = MAXN;
        tail--;
        sz--;
    }
    int size() {
        return sz;
    }
};

10.1〜6は、2つのスタックを使用して1つのキューを実装し、キュー操作の実行時間を分析する方法を示す.

template <typename ITEM>
class queuebytwostack{
private:
    stack<ITEM> stkin;
    stack<ITEM> stkout;
    void readyToPop() {
        while (!stkin.empty()) {
            stkout.push(stkin.top());
            stkin.pop();
        }
    }
public:
    bool empty() {
        if (stkin.empty()&&stkout.empty()) return true;
        return false;
    }
    void push(ITEM x){
        try {
            stkin.push(x);
        }
        catch (const char *e) {
            throw e;
        }
    }
    ITEM front() {
        try {
            if (stkout.empty()) readyToPop();
            return stkout.top();
        }
        catch (const char *e) {
            throw e;
        }
    }
    void pop() {
        try {
            if (stkout.empty()) readyToPop();
            stkout.pop();
        }
        catch (const char *e) {
            throw e;
        }
    }
    int size() {
        return stkin.size()+stkout.size();
    }
};

PUSH O(1)
POP O(n)
10.1〜7は、2つのキューを使用して1つのスタックを実装し、スタック動作の実行時間を分析する方法を示す.

template <typename ITEM>
class stackbytwoqueue {
private:
    queue<ITEM> que[2];
    int p;
public:
    stackbytwoqueue() {
        p = 0;
    }
    bool empty() {
        if (que[0].empty()&&que[1].empty()) return true;
        return false;
    }
    void push(ITEM x) {
        try {
            que[p].push(x);
        }
        catch (const char *e) {
            throw e;
        }
    }
    ITEM top() {
        try {
            int sz = que[p].size();
            ITEM res;
            for (int i=1;i<=sz;i++) {
                if (i==sz) res = que[p].front();
                que[p^1].push(que[p].front());
                que[p].pop();
            }
            p^=1;
            return res;
        }
        catch (const char *e) {
            throw e;
        }
    }
    void pop() {
        try {
            int sz = que[p].size();
            for (int i=1;i<=sz-1;i++) {
                que[p^1].push(que[p].front());
                que[p].pop();
            }
            que[p].pop();
            p^=1;
        }
        catch (const char *e) {
            throw e;
        }
    }
    int size() {
        return que[p].size()+que[p^1].size();
    }
};

PUSH O(1)
POP O(n)