#include <vector>
#include <stdexcept>

/**
 * TwoQueues<T>
 * ---------------------------------------------
 * Stores two independent FIFO queues in ONE
 * fixed-size buffer with O(1) ops and 0 wasted
 * slots.  Throwing interfaces keep the demo
 * short; production code may prefer std::optional.
 */
template <typename T>
class TwoQueues {
public:
    explicit TwoQueues(std::size_t capacity)
        : buf_(capacity),
          head1_(0),                // queue-1 is empty ⇒ head1 > tail1
          tail1_(-1),
          head2_(static_cast<int>(capacity) - 1), // queue-2 empty ⇒ tail2 == buf_.size()
          tail2_(static_cast<int>(capacity))      //   and head2 = last valid index
    {}

    /* ----- Queue-1 (left → right) ------------------------------ */

    void enqueue1(const T& val) {
        if (full()) throw std::overflow_error("buffer full");
        buf_[++tail1_] = val;                 // advance tail, then write
    }

    T dequeue1() {
        if (empty1()) throw std::underflow_error("queue-1 empty");
        T out = buf_[head1_++];               // read, then advance head
        if (empty1()) reset1();               // optional compaction
        return out;
    }

    bool empty1() const { return head1_ > tail1_; }

    /* ----- Queue-2 (right → left) ------------------------------ */

    void enqueue2(const T& val) {
        if (full()) throw std::overflow_error("buffer full");

        if (empty2()) {                       // first element → claim slot n-1
            tail2_ = head2_;                  // tail2_ becomes n-1
        } else {
            --tail2_;                         // move tail left one slot
        }
        buf_[tail2_] = val;
    }

    T dequeue2() {
        if (empty2()) throw std::underflow_error("queue-2 empty");
        T out = buf_[head2_--];               // read front, move head left
        if (empty2()) reset2();               // compact when queue-2 empties
        return out;
    }

    bool empty2() const { return tail2_ == static_cast<int>(buf_.size()); }

    /* ----- Shared helpers -------------------------------------- */

    bool full() const { return tail1_ + 1 == tail2_; }
    std::size_t capacity() const { return buf_.size(); }

private:
    /* Bring indices back to their pristine “empty” state
       so they don’t wander off to ±∞ over time. */
    void reset1() { head1_ = 0; tail1_ = -1; }
    void reset2() {
        head2_ = static_cast<int>(buf_.size()) - 1;
        tail2_ = static_cast<int>(buf_.size());
    }

    std::vector<T> buf_;   // the single fixed-size buffer

    // Queue-1 indices (left-growing)
    int head1_;            // oldest item
    int tail1_;            // newest item

    // Queue-2 indices (right-growing)
    int head2_;            // oldest item
    int tail2_;            // newest item (one past front when empty)
};

Complexity summary
Enqueue / Dequeue (either queue): O(1) time, O(1) extra space.

Overall space: O(N) — the one fixed-size buffer; every slot is either live data or immediately usable, so zero waste.