Stacks & Queues

All sorts of applications can hold large amount of data for it to function, and storing data in a proper structure helps the applications to run efficiently. Datastructure is how we manage our stored information and more conveniently, operate on it. A certain datastructure is useful for a certain application depending on which operation being called and how frequent it is being called. Therefore, a datastructure is based on the structure that holds the data + the algorithms of that structure.

In this article, I’ll be talking about two primitive datastructures that every CS student has definitely used before one way or another.

Stacks

Let’s start with stacks, a LIFO datastructure used for retrieval/insertion of the most recent data element in constant time. LIFO stands for “Last In First Out”, meaning that the last element added to the stack is also the first one to be removed from the stack. Basically,

• Adding an element to the stack is called push.
• Removing an element from the stack is called pop.

When it comes to time complexity…

Implementing stacks is easy, but still has to be implemented in order to understand it thoroughly. All insertions and deletions are done at one end called top. A stack can be implemented in two ways…

1. Using Dynamic Arrays
2. Using Linked Lists

How you implement it is your choice, but those are the common methods needed to define a new class called “SimpleStack”.

// A common Stack Interface.
template<typename T>
class SimpleStack {
public:
	SimpleStack(int size); // Class Constructor.
	void push(const T& e); // adds element to top of the stack.
	void pop(); // removes top element of the stack.
	T top(); // returns top element of the stack.
	bool IsEmpty(); // checks if stack is empty.
	bool IsFull(); // checks if stack is full.
	~SimpleStack(); // Class Destructor.
};

Stacks in C++

Stacks in Go

Stack-based Applications

• Balancing Enclosure Symbols
• Conversion from Decimal to Hexadecimal
• Evaluation of Postfix Expression
• The Hanoi Towers
• Backtracking
• Transforming Recursive functions into Iterative functions
• Web browser history
• And many more...

Queues

Next, we’ll talk about queues, a FIFO datastructure that works the same way as you’d expect after hearing the word queue. FIFO stands for “First In First Out”, in other words, the first element that is added to the queue is also the first one to be removed from the queue. Think of it as standing in a queue for the movies, at the clinic, et cetera. It is a simple linear datastructure that serves well for all queue-based applications like CPU task scheduling in Operating Systems or applying Breadth-First Search Algorithm.

However, some applications might require and advanced datastructure like a Priority Queue that handles the queue based on who has the highest priority (key). You can read about Priority Queue in this article, for now what you need to know is that Queues and Priority Queues are not the same.

Back to Queues, it is a linear list of elements where access is by order of insertion. Insertions are done at one end rear and deletions are done at the other end front. Basically,

• Adding an element to end of queue is called enqueue.
• Removing an element from front of queue is called dequeue.

When it comes to time complexity…

When it comes to implementation, a queue is viewed as a circular array with two pointers front and rear. Both pointers advance clockwise and to enqueue: rear = (rear + 1) % size while to dequeue: front = (front + 1) % size. A queue can be implemented in two ways…

1. Using Dynamic Arrays
2. Using Linked Lists

// A common Queue Interface.
template<typename T>
class SimpleQueue {
public:
	SimpleQueue(int size); // Class Constructor.
	void enqueue(const T& e); // adds element to end of the queue.
	T dequeue(); // removes the element from front of the queue.
	T queueFront(); // retrieves front element without removing it.
	bool IsEmpty(); // checks if queue is empty.
	bool IsFull(); // checks if queue is full.
	~SimpleQueue(); // Class Destructor.
};

Queues in C++

Queues in Go

Queue-based Applications

• Job Scheduling
• Simulation of Waiting Lines
• I/O Buffering
• And many more...