python-deque

Warning

This implementation is inspired by a homework assignment from 15-213 at Carnegie Mellon University. It is intended for educational purposes only and is not suitable for production use.

A simple naive implementation of a deque (double-ended queue) in Python.

The purpose of this repo is to serve as an example of how to set up a GitHub Actions workflow.

Definition

A linear list for which all insertions and deletions (and usually all accesses) are made at the ends of the list.

— Paul E. Black, deque, Dictionary of Algorithms and Data Structures [online], NIST.

When to Use

A deque is the right structure when you need O(1) insertion and removal at both ends, making it a strict generalization of both the stack and the queue:

• Sliding window algorithms — problems like "maximum of all subarrays of size k" use a deque to maintain a window of candidates, pushing to the back and popping stale entries from the front in O(1).
• Work-stealing schedulers — multi-threaded runtimes (like Java's ForkJoinPool) give each thread a deque: the owner pushes and pops from the back while idle threads steal from the front.
• Palindrome checking — comparing characters from both ends of a string is natural with a deque, popping from front and back simultaneously.
• Browser history with forward/back — unlike a plain stack, a deque allows navigation in both directions while still supporting O(1) push and pop at each end.
• Implementing both stacks and queues — a deque subsumes both; use push_back/pop_back for stack semantics and push_back/pop_front for queue semantics.

Requirements

• Python 3.6+

Installation

Clone the repository and install dependencies:

git clone https://github.com/icaoberg/python-deque.git
cd python-deque
pip install -r requirements.txt

Usage

from Deque import Deque

d = Deque()
d.push_back(1)
d.push_back(2)
d.push_front(0)

print(d.size())       # 3
print(d.tolist())     # [0, 1, 2]
print(d.peek_front()) # 0
print(d.peek_back())  # 2
print(d.pop_front())  # 0
print(d.pop_back())   # 2
print(d.tolist())     # [1]
print(d.is_empty())   # False
print(len(d))         # 1

Methods

Method	Description
push_front(element)	Insert an element at the front
push_back(element)	Insert an element at the back
pop_front()	Remove and return the front element
pop_back()	Remove and return the back element
peek_front()	Return the front element without removing it
peek_back()	Return the back element without removing it
tolist()	Return the contents as a Python list
is_empty()	Return True if the deque has no elements
size()	Return the number of elements

Testing

pytest tests.py

Support

If you found this project helpful, consider buying me a coffee!

Copyright © icaoberg at Carnegie Mellon University. All rights reserved.