Data Structures: Stacks and Queues
a guide into data structures and the most known related algorithms
In this article, I will explain two important data structures, and I will be writing about more popular data structures in upcoming articles.
For the first time, we are talking about data structures that need to be implemented using the simpler data structures we already covered. If you need more information about those you can always refer back to the previous articles.
Remember, these articles assume our readers are familiar with the concept of data structures and why they are used in software development, and it will dive into the definition, the different types, implementations, and complexity of each data structure we are studying.
Definition
Both Stacks and Queues are linear data structures modeling real-life scenarios. Stack models a Last In First Out scenario and the Queue models a First In First Out Scenario.
Both data structures are used to organize access to data, the difference is in the way every structure organizes that access…
Push is the adding method to the stack while Pop is the method to access and delete the top element of the stack.
Enqueue is the method to add an element to a Queue, and Dequeue is to remove previously enqueued elements.
Usage
Stack
1- The UNDO functionality in text editors.
2- Compiler syntax-checking for Brackets and Braces coupling.
3- Modeling piles.
4- Supporting recursion, and keeping track of previous function calls.
5- Used in a Depth First Search on a graph or tree.
Queue
1- Modeling a waiting line.
2- Any First Come First Serve scenario, in a web server request management for example.
3- Breath first search graph or tree traversal.
Complexity
Stack
Most operations are of a constant time complexity big O, besides searching which is linear in case the item we are looking for doesn’t exist.
Queue
Similarly, only Contains and Removal operations are linear in a queue. All the other operations are of constant complexity.
Different Languages approach
C#
In .NET, both Queue and Stack are implemented, packaged, and offered as classes to easily call and use.
// Using a stack in c# is as easy as the below example.
Stack st = new Stack();st.Push('A');
st.Push('B');
st.Push('C');char ch = st.Pop(); //will return C;
char ch2 = st.Pop(); // returns B;// Using a queue can also be done as the below example.
Queue q = new Queue();q.Enqueue(“Two”);
q.Enqueue(“One”);
// Remove elements and print them to the console.
while (q.Count > 0)
Console.WriteLine(q.Dequeue());
JAVA
Java offers the implementation of Stack and Queue a bit differently.
A stack is offered as a class inheriting a vector datatype with all its methods in addition to the methods for stack manipulation. It is used very similarly to C#.
A queue, on the other hand, is offered as an interface that requires the usage of a different datatype as Queue. below is an example.
// examples of declaring a queue in JAVA.
Queue queueA = new LinkedList();
Queue queueB = new PriorityQueue();queueA.add("element 1");
queueA.add("element 2");// both poll and remove do the same with one difference, if the // queue is empty poll return a null while remove throws an // exception.String element1 = queueA.poll();
String element2 = queueA.remove();
JavaScript
JavaScript doesn’t offer a pre-packaged implementation of Stack nor Queue, which means developers or engineer like you and me will need to implement it.
The easiest way is to build constructors with their prototype methods similar to what we saw in JAVA and C#. The only difference is using object {} for storage.
the link below is a great blog explaining the implementation of Stack and Queue in JavaScript.
Ruby and Python
Both Ruby and Python don’t really have data structures specifically for Queues and Stacks, instead they offer the respective methods with their basic data structures so we can imitate the functionalities of a stack and a queue.
Ruby, for instance, offers the methods push and pop to be used with arrays, offering a LIFO behavior (Stack) and push/shift or unshift/pop offering FIFO behavior (Queue).
Python offers append, pop, and pop(0) bundled with List, and it also offers dequeue pronounced dec with the methods: append, pop, and popleft.
Popular problems solved with Queue and Stack
BFS and DFS, mainly in trees and graphs, are the most common design patterns where queues and stacks play an essential role.
Breadth-First Search (BFS)
Visits all vertices or nodes in a tree level by level. In order to do so, every time we visit a node we push its children into a queue, so after we are done with that node, we will have access to the next level nodes in order.
Depth-First Search (DFS)
Visits all vertices or nodes in a tree starting by the root node and keeps visiting all child nodes until it reaches the deepest.
DFS uses a Stack in order to store the child nodes of every vertex it visits in order to revisit them after done with the deeper nodes.
Conclusion
As we explained the definition of Queues and Stacks and its implementation in different languages and its most common coding patterns, keep in mind there are more data structures to model and fix different problems.
We will be talking about those in future articles, along with their implementations and the most common coding patterns that help resolve their specific problems.
Stay tuned…
