スタックによるキューの実装

2つのスタックを使用してキューの操作を実現します。入力用スタックと出力用スタックを用意し、要素の追加と取り出しを効率的に行います。

class QueueWithStacks {
private:
    std::stack<int> inputStack;
    std::stack<int> outputStack;
    
public:
    void enqueue(int value) {
        inputStack.push(value);
    }
    
    int dequeue() {
        if (outputStack.empty()) {
            while (!inputStack.empty()) {
                outputStack.push(inputStack.top());
                inputStack.pop();
            }
        }
        int front = outputStack.top();
        outputStack.pop();
        return front;
    }
    
    bool isEmpty() {
        return inputStack.empty() && outputStack.empty();
    }
};

キューによるスタックの実装

単一のキューを使用してスタックの操作を模倣します。プッシュ操作は単純ですが、ポップ操作ではキューの要素を再配置します。

from collections import deque

class StackWithQueue:
    def __init__(self):
        self.q = deque()
    
    def push(self, val):
        self.q.append(val)
    
    def pop(self):
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())
        return self.q.popleft()
    
    def top(self):
        return self.q[-1]
    
    def empty(self):
        return len(self.q) == 0

括弧の有効性チェック

スタックを使用して括弧の対応関係を検証します。開き括弧には対応する閉じ括弧をスタックに保存する方法が効率的です。

public boolean isValidParentheses(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '(') stack.push(')');
        else if (c == '[') stack.push(']');
        else if (c == '{') stack.push('}');
        else if (stack.isEmpty() || stack.pop() != c) return false;
    }
    return stack.isEmpty();
}

隣接重複文字の削除

文字列を走査しながらスタックを用いて隣接する重複文字を効率的に削除します。

std::string removeAdjacentDuplicates(std::string s) {
    std::string result;
    for (char c : s) {
        if (!result.empty() && result.back() == c) {
            result.pop_back();
        } else {
            result.push_back(c);
        }
    }
    return result;
}