AdvancedDataStructures/QueueWithExtremal.cpp at master · sajeruk/AdvancedDataStructures · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// created by Maxim Busel @sajeruk
#include "QueueWithExtremal.h"

template <typename T, typename Comparator>
void QueueWithExtremal<T, Comparator>::enqueue(const T& element) {
  if(empty())
    head_.push(element);
  else
    tail_.push(element);
}

template <typename T, typename Comparator>
const T& QueueWithExtremal<T, Comparator>::extremum() const {

  if (empty()) {
    throw std::logic_error("No extremum in empty queue");
  } else if (head_.empty()) {
    return tail_.extremum();
  } else if (tail_.empty()) {
    return head_.extremum();
  } else {
    return std::min(head_.extremum(), tail_.extremum(), Comparator());
  }
}

template <typename T, typename Comparator>
const T& QueueWithExtremal<T, Comparator>::front() const {
  if (head_.empty()) {
        throw std::logic_error("No front"
        "element in empty queue");
  }
  return head_.top();
}

template <typename T, typename Comparator>
void QueueWithExtremal<T, Comparator>::dequeue() {
  if (head_.empty()) {
    throw std::logic_error("Cannot dequeue empty queue");
  }
  head_.pop();
  if (head_.empty())
    transfer_();
}

template <typename T, typename Comparator>
void QueueWithExtremal<T, Comparator>::transfer_() {
  if(tail_.empty())
    return;

  head_.push(tail_.top());
  tail_.pop();

  while (!tail_.empty()) {
    head_.push(tail_.top());
    tail_.pop();
  }
}

template <typename T, typename Comparator>
bool QueueWithExtremal<T, Comparator>::empty() const {
  return head_.empty() && tail_.empty();
}