Data Structures Part 2: Stack, Queue, and Deque ADTs
In Data Structures Part 1, we focused on Concrete Data Types. We discussed Arrays, Singly Linked Lists, Doubly Linked Lists, and Circular Linked Lists. Please read Part 1 for context before starting with Part 2.
Stack ADT
A Stack is a linear data structure that stores arbitrary objects. Stack operations are performed based on the Last In First Out (LIFO) principle. Data is inserted at the top (last node) and removed at the top (last node) of the stack. A Stack can be implemented using either an Array or a Singly Linked List as the underlying data structure.
History and applications of a Stack
The name “Stack” was derived from the metaphor of a stack of plates in a spring-loaded plate dispenser. A plate dispenser’s operations involve pushing and popping plates on the stack.
The Stack data structure is used by text editors for the undo or redo operations, string reversal, and web browsers for page-visited history. A Stack can also be used indirectly as an auxiliary data structure when writing algorithms or as a component of other data structures.
Operations
A Stack supports the following two main methods:
push(e): Insert element e, to be the top of the stack.
pop(): Removes the topmost element from the stack, or null if the stack is empty.
A Stack supports the following three auxiliary methods:
size(): Returns the number of elements in the stack.
isEmpty: Returns a Boolean value indicating if the stack is empty or not.
top(): Returns the topmost element in the stack or null if the stack is empty.
Performance and memory usage
A Stack can be implemented using either an Array or a Singly Linked List CDTs.
Array-Based: An ArrayStack is easy to implement and efficient. Each operation runs in time O(1). The memory usage is O(n), where n represents the number of elements. The drawbacks of this implementation are the capacity of the stack needs to be set at compile-time and cannot be changed, and if we try to push a new element onto an already full stack it will throw an exception.
Singly Linked List: Singly Linked List Stack aims to solve the problem identified in the ArrayStack implementation. By using a Singly Linked List under the hood, the capacity of the Stack is dynamic. The top of the will be set to the head of the Singly Linked List since we can insert (push(e)) and delete (pop()) in constant time O(1) at the head. For the size() and isEmpty() methods to run in constant time we can keep track of the number of elements in an instance variable. Therefore, a Stack backed by a Singly Linked List is the most efficient implementation since all operations run in O(1) and memory usage is O(n).
Kotlin Implementation
Queue ADT
A Queue is a linear data structure that stores arbitrary objects. Queue operations are performed based on the First In First Out (FIFO) principle. Data is inserted at the tail (last node) and removed at the head (first node) of the queue. A Queue can be implemented using either an Array or a Singly Linked List as the underlying data structure.
History and Applications of a Queue
The name “Queue” is derived from a line of people waiting to purchase a movie ticket at the Movie Theatre. The first customer in the queue will be removed from the front of the queue. New customers will join the queue from the back (rear).
The Queue data structure is used to access shared resources (printer), message queues, and process scheduling. A Queue can also be used indirectly as an auxiliary data structure when writing algorithms or as a component of other data structures.
Operations
A Queue supports the following operations:
enqueue(e): Inserts the element e at the rear of the queue.
dequeue(): Removes and returns the element at the front of the queue, and returns null if the queue is empty.
front(): Returns the element at the front of the queue, and returns null if the queue is empty.
size(): Returns the number of elements in the queue.
isEmpty(): Returns a Boolean value that indicates whether the queue is empty.
Performance and memory usage
A Queue can be implemented using either an Array, Array-List, or a Singly Linked List CDTs.
Array-Based: To avoid the dequeue() operation from taking O(n) time to run, where n represents the number of elements needed to shift forward, we need to define two variables f and r which have the following meaning.
f: refers to the index of the first element in the Queue, which is next to be dequeued unless the Queue is empty (f = r=0). Initially set to 0. When an element is dequeued we need to increment the f index to the next element in the Queue.
r: refers to the index of the next available cell in the Queue. Initially set to 0. When a new element is enqueued we need to increment the r index to the next available cell in the Queue.
By using the f and r variables we are able to implement the front(), enqueue(e), and dequeue() methods in constant time, O(1). This implementation has two drawbacks. The first drawback is that if we repeatedly enqueue and dequeue element N until f =r=N. If were then to enqueue once more, an IndexOutOfBounds error would be thrown. The second drawback is we have to specify the maximum size of the Queue.
The memory usage in a normal Array-Based Queue is O(n), where n represents the number of elements.
Circular Queue (Array-Based): The Circular Queue implementation aims to solve the first problem identified in the normal Array-Based Queue implementation. To implement a Circular Queue the modulo (%) operator is used, to wrap indices around the end of the Array, (f + 1) % N or (r + 1) % N. Each method in a Circular Queue runs in constant time, O(1).
The memory usage in a Circular Queue is O(n), where n represents the number of elements. Since this implementation also uses an Array under the hood, the second drawback identified in the Array-Based implementation still exists here.
Singly Linked List: The Singly Linked List implementation aims to solve the drawbacks identified in the previous two implementations. By using a Singly Linked List under the hood, each Queue operation runs in time O(1) and we don’t have to specify the maximum size of the Queue. This benefit comes at the expense of increasing the amount of space used as new elements are added to the Queue. The memory usage is O(n), where n represents the number of elements.
To implement a Queue using a Singly Linked List we need to maintain references to both head and tail nodes in the list. In this way, we can remove from the head and add new nodes at the tail efficiently.
Deque ADT
A Deque, also known as a double-ended queue, is a data structure that supports insertion and deletion operations at both the front and back of the queue. A Deque is usually pronounced as “deck” to avoid confusion with the dequeue method of a Queue ADT.
History and Applications of a Queue
A Deque can be used to implement a waitlist feature in a Restaurant application. The restaurant usher might remove the first customer from the queue to find that there are no tables available. Thus, the usher will reinsert the customer at the front of the queue. The customer at the end of the queue might feel that the queue is too long and leave the restaurant.
We can also think of its application in a web browser's history, where the most recently visited sites are added to the front of the deque and the sites at the back of the deque are removed after N minutes.
Operations
A Deque supports the following operations:
addFirst(e): Inserts a new element e at the front of the deque.
addLast(e): Inserts a new element e at the back of the deque.
removeFirst(): Removes and returns the first element of the deque. Returns null if the deque is empty.
removeLast(): Removes and returns the last element of the deque. Returns null if the deque is empty.
first(): Returns the first element of the deque. Returns null if the deque is empty.
last(): Returns the last element of the deque. Returns null if the deque is empty.
size(): Returns the number of elements in the deque.
isEmpty(): Returns a boolean value indicating whether or not the deque is empty.
Performance and memory usage
A Deque ADT using a Doubly Linked List under the hood, does not have a predefined size. Thus, the space used by a list with n elements is O(n). All Deque operations run in constant time, O(1).
Kotlin Implementation
Conclusion
In Data Structures Part 3: List Abstractions, we’ll discuss Array-List ADT, Position & Positional List ADT, and Iterators.
2313. Java Core — Stack, Queue and Deque Queue, Stack, Queue, and Heap
Java Stack extends Vector class with the following five operations only.
- boolean empty(): Tests if this stack is empty.
- E peek(): Looks at the object at the top of this stack without removing it from the stack.
- E pop() : Removes the object at the top of this stack and returns that object as the value of this function.
- E push(E item) : Pushes an item onto the top of this stack.
- int search(Object o) : Returns the 1-based position where an object is on this stack.
1.2 Deque Interface and LinkedList Class
Deque interface supports adding and removing elements from both ends of the queue. If we only use the push and pop methods, it behaves just like a stack.
2. Queue
2.1 Java Queue Categories
Bounded Queues are queues which are bounded by capacity that means we need to provide the max size of the queue at the time of creation. For example ArrayBlockingQueue.
- Bounded Queues
- Unbounded Queues
All Queues which implement BlockingQueue interface are BlockingQueues and rest are Non-Blocking Queues.
- Blocking Queues
- Non-Blocking Queues
2.2 Constructing Queue
2.3 Common Operations
Java Queue supports all operations supported by Collection interface and some more operations. It supports almost all operations in two forms.
Шпаргалка по структурам данных в Java
К каждому собеседованию важно готовиться и проще всего это делать, когда перед глазами есть готовый материал. В данной публикации я хочу поделиться с вами своей шпаргалкой, которую использую перед собеседованиями для повторения структур данных в Java.
Что такое структуры данных, для чего они и какие есть в Java?
Под структурами данных подразумевается хранение данных и их организация таким образом, чтобы решать поставленную задачу наиболее эффективным способом. В Java есть следующие структуры данных:
Список (Динамический массив)
HashTable и HashMap
Массив
Массив — это нумерованный набор переменных одного типа.
Объявляется следующем образом:
Все массивы в Java одномерные. В случае с многомерными массивами каждый элемент содержит только ссылку на вложенный массив
Можно создать нулевого размера, может быть полезно если нужно вернуть пустой массив из какого-либо метода
Оператор new используется для создания ссылочного типа данных. Ссылка хранится на стеке, а объект в куче. Если на объект нет ссылок, то он будет удалён автоматически. Удаление объекта может быть осуществлено с задержкой
Список (Динамический массив)
Идея списка или же динамического массива заключается в автоматическом расширении емкости .
Объявляется следующем образом:
Примитивный тип данных передать не можем, поэтому передаем класс обертку. О классах обертках, можно прочитать здесь. При желании можно написать универсальную реализацию ArrayList, сделать его массивом Object и тогда можно будет хранить еще и примитивы благодаря автоупаковке
Если не указать в конструктор начальную емкость, то будет создан пустой список с емкостью в 10 элементов
В случае, когда зарезервированной емкости не хватает, при достижении максимального количества элементов будет создан новый массив с емкостью: новая_емкость = (старая_емкость * 3) / 2 + 1. Существующие элементы списка будут скопированы в новый массив
Чтобы не тратить память напрасно, при удалении элементов следует вызывать метод trimToSize()
+ доступ к элементам по индексу за O(1), к элементам по значению за O(n);
+ можно хранить любые значения и даже null.
— вставка или удаление элемента в середину списка вызывает перезапись всех элементов, работает за O(n);
— поиск за O(n);
— не синхронизирован.
Очередь работает по принципу LIFO. В Java наследуется от Vector<E>, реализует следующие интерфейсы: Iterable<E>, Collection<E>, List<E>, RandomAccess, Serializable, Cloneable.
Объявляется следующем образом:
push() — добавляет в конец очереди;
peek() — возвращает последний элемент и не удаляет его;
pop() — удаляет последний элемент и возвращает его;
empty() — вернет true — если очередь пуста и false — в противном случае;
search() — возвращает номер позиции с конца очереди.
Очередь
Iterable<T> => Collection<E> => Queue<E> => Deque<E>
Интерфейсы Queue<E> и Deque<E> реализуют следующие классы:
ArrayDeque<E> — двухсторонняя очередь
LinkedList<E> — связный список
PriorityQueue<E> — очередь с приоритетами
Объявляется следующем образом:
Разница между реализацией на листе и деку
ArrayDeque реализует дек на массиве, поэтому он эффективнее по памяти и работает быстрее, чем LinkedList
Пару слов о PriorityQueue.
Этот класс реализует следующие интерфейсы: Iterable<E>, Collection<E>, Queue<E>, Serializable. У этого класса есть свои особенности:
Из очереди первым возвращается элемент с наибольшим приоритетом
Значение null добавить нельзя
Связный список
Класс реализует следующие интерфейсы:
Iterable<E>, Collection<E>, List<E>, Queue<E>, Deque<E>, Serializable, Cloneable.
c++ deque vs queue vs stack
Queue and Stack are a structures widely mentioned. However, in C++, for queue you can do it in two ways:
but for stack you can only do it like this
My question is, what’s the difference between queue and deque, why two structures proposed? For stack, any other structure could be included?
9 Answers 9
Moron/Aryabhatta is correct, but a little more detail may be helpful.
Queue and stack are higher level containers than deque, vector, or list. By this, I mean that you can build a queue or stack out of the lower level containers.
Will build a stack of ints using a deque as the underlying container and a queue of doubles using a list as the underlying container.
You can think of s as a restricted deque and q as a restricted list.
All that is necessary is that the lower level container implements the methods needed by the higher level container. These are back() , push_back() , and pop_back() for stack and front() , back() , push_back() , and pop_front() for queue.
See stack and queue for more detail.
With respect to the deque, it is much more than a queue where you can insert at both ends. In particular, it has the random access operator[] . This makes it more like a vector, but a vector where you can insert and delete at the beginning with push_front() and pop_front() .