AK: Add CircularDeque.

This class inherits from CircularQueue and adds the ability dequeue
from the end of the queue using dequeue_end().

Note that I had to make some of CircularQueue's fields protected to
properly implement dequeue_end.

2 files changed, 25 insertions, 1 deletions

diff --git a/AK/CircularDeque.h b/AK/CircularDeque.h
new file mode 100644
index 0000000000..7f7f4d7f19
--- /dev/null
+++ b/AK/CircularDeque.h
@@ -0,0 +1,24 @@
+#pragma once
+
+#include <AK/Assertions.h>
+#include <AK/CircularQueue.h>
+#include <AK/Types.h>
+
+namespace AK {
+
+template<typename T, int Capacity>
+class CircularDeque : public CircularQueue<T, Capacity> {
+
+public:
+    T dequeue_end()
+    {
+        ASSERT(!this->is_empty());
+        T value = this->m_elements[(this->m_head + this->m_size - 1) % Capacity];
+        this->m_size--;
+        return value;
+    }
+};
+
+}
+
+using AK::CircularDeque;
diff --git a/AK/CircularQueue.h b/AK/CircularQueue.h
index 7f1ce3ccf9..e48249bf5e 100644
--- a/AK/CircularQueue.h
+++ b/AK/CircularQueue.h
@@ -77,7 +77,7 @@ public:
 
     int head_index() const { return m_head; }
 
-private:
+protected:
     friend class ConstIterator;
     T m_elements[Capacity];
     int m_size { 0 };