Size-limited queue

Categories:
Tags:

Problem

Implement size-limited queue.

Requirements

  • Interface:
    • push — add an element to the queue.
    • pop — remove an elemtn from the queue and return it.
  • Complexity:
    • Time:
      • push: \(O(1)\) (amortized).
      • pop: \(O(1)\) (amortized).
    • Space: \(O(n)\).
  • Do not use standard containers except std::vector.

Solution 1

Two stacks:

limited_queue.h
 1#include <optional>
 2#include <vector>
 3
 4template<typename T>
 5class limited_queue {
 6    std::size_t max_size;
 7    std::vector<T> a, b;
 8
 9    void move(std::size_t n = 0) {
10        while (a.size() > n) {
11            b.push(a.back());
12            a.pop_back();
13        }
14        a.clear();
15    }
16
17public:
18    limited_queue() = delete;
19    limited_queue(std::size_t size) : max_size{size} {}
20
21    void push(const T& value) {
22        a.push(value);
23        if (a.size() >= max_size) move(1);
24        if (a.size() + b.size() >= max_size) b.pop_back();
25    }
26
27    std::optional<T> pop() {
28        if (a.empty() && b.empty()) return std::nullopt;
29        if (b.empty()) move();
30
31        T t = b.back();
32        b.pop_back();
33
34        return t;
35    }
36};

Solution 2

Deque:

limited_queue.h
 1#include <deque>
 2#include <optional>
 3
 4template<typename T>
 5class limited_queue {
 6    std::size_t max_size;
 7    std::deque<T> data;
 8
 9public:
10    limited_queue() = delete;
11    limited_queue(std::size_t size) : max_size{size} {}
12
13    void push(const T& value) {
14        data.push_back(value);
15        if (data.size() >= max_size)
16            data.pop_front();
17    }
18
19    std::optional<T> pop() {
20        if (data.empty()) return std::nullopt;
21        T t = data.front(); data.pop_front();
22        return t;
23    }
24};