Introduction to Data Structures: Stacks & Queues

Updated on April 11, 2018

Abstract data structures

Stacks and queues are both abstract data structures. The definition of their structure is solely based on their behaviour and not the underlying implementation. This is in contrast to more fundamental data structures, such as arrays and linked lists, which have strict requirements for how the storage of their data is implemented.

Below we will look at implementations of stacks and queues based upon arrays and linked lists. There are clear similarities between the stack and the queue. Indeed, in all of the below cases the efficiency of insertion and deletion operations scale as O(1). The main difference is that an array based implementation requires a maximum size but a linked list based implementation can dynamically grow. If a suitable maximum size can't be chosen in advance, an oversized array is usually used, leading to large amounts of wasted memory. However, a linked list uses more memory than an an array, to store the same number of elements, due to the additional storage of pointers.

Stacks

General idea

A stack is defined by having a LIFO (Last In First Out) ordering principle. The first element added to a stack is the last to be removed. Equivalently, the last element added to a stack is the first to be removed. Operations that act on a stack have a unique terminology:

  • Push - add a new element to the stack.
  • Pop - remove an element from the stack.

An example stack, storing a group of integers. Note that both insertions and removals occur at the same end of the stack.
An example stack, storing a group of integers. Note that both insertions and removals occur at the same end of the stack.

Array based implementation

template <class T>
class Stack {
public:
	Stack(const int size) : count{0}, max_size{size} {
		stack = new T[max_size];
	}
	~Stack() {
		delete[] stack;
	}
	bool Empty() const{ 
		return count == 0;
	}
	bool Full() const{
		return count == max_size;
	}
	void Push(const T new_data) {
		if (!Full()) {
			stack[count] = new_data;
			count++;
		} else {
			//Stack overflow error
		}
	}
	T Pop() {
		if (!Empty()) {
			count--;
			return stack[count];
		} else {
			//Empty stack error
		}
	}
private:
	int count;
	const int max_size;
	T* stack;
	Stack();
};

The above code declares a template stack class in C++, based upon an array. It has a max size and stores the stack elements within an array of this max size. The current count of elements on the stack is also stored. The default constructor is set as private and left undefined. This prevents it being called, as creating a stack without specifying a max size doesn't make sense. Instead, the constructor takes a user input max size and then dynamically allocates an array using this size.

Two boolean returning utility functions are included, to check if the stack is empty or full. The push function only runs if the stack isn't full, trying to push an element on to a full stack leads to an overflow error (which the programmer then needs to choose how to deal with). If there is space, the array element at the count index is set equal to the user input data and the count is then incremented. The pop function only runs if the stack isn't empty, trying to pop an element from a empty stack is obviously an error. If there are elements available, the count is decremented and array element at the count index is then returned.

An example of an array based stack. The stack has a maximum size of five but is only currently storing three values.
An example of an array based stack. The stack has a maximum size of five but is only currently storing three values.

Linked list based implementation

template <class T>
class Stack {
public:
	Stack() : top{nullptr} {}
	~Stack() {
		while (top != nullptr) {
			Node* previous{top};
			top = top->next;
			delete previous;
		}
	}
	bool Empty() const{
		return top == nullptr;
	}
	void Push(const T new_data) {
		Node* new_node{new Node};
		new_node->data = new_data;
		new_node->next = top;
		top = new_node;
	}
	T Pop() {
		if (!Empty()) {
			Node* current_top{top};
			T top_data{top->data};
			top = top->next;
			delete current_top;
			return top_data;
		} else {
			//Empty stack error
		}
	}
private:
	struct Node {
		T data;
		Node* next;
	};
	Node* top;
};

The above code declares a template stack class in C++, based upon a linear linked list of nodes. The only directly stored data is a pointer to the top node of the stack. The constructor sets the top to a null pointer, signifying an empty stack.

The push function creates a new node and then inserts it at the head of the linked list, which represents the top of our stack. Notice that there is now no stack overflow error (unless we run out of heap memory and the new allocation fails). The pop function deletes the top node, moves the top pointer to the next element down the stack and returns the data from the deleted element. There is still a need to deal with empty stack errors.

An example of a linked list based stack, currently storing three elements.
An example of a linked list based stack, currently storing three elements.

Queues

General idea

A queue is defined by having a FIFO (First In First Out) ordering principle. The first element added to a queue is the first to be removed and the last element to be added to a queue will be the last to be removed. The terminology for operations that act on queues is as follows:

  • Enqueue - add a new element to the queue.
  • Dequeue - remove an element from the queue.

An example queue, storing a group of integers. Note that the insertions and removals occur at opposite ends of the queue.
An example queue, storing a group of integers. Note that the insertions and removals occur at opposite ends of the queue.

Array based implementation

template <class T>
class Queue {
public:
	Queue(const int size) : front{0}, count{0}, max_size{size} {
		queue = new T[max_size];
	}
	~Queue() {
		delete[] queue;
	}
	bool Empty() const{
		return count == 0;
	}
	bool Full() const{
		return count == max_size;
	}
	void Enqueue(const T new_data) {
		if (!Full()) {
			queue[(front + count) % max_size] = new_data;
			count++;
		} else {
			//Queue overflow error
		}
	}
	T Dequeue() {
		if (!Empty()) {
			count--;
			T front_data{queue[front]};
			front = (front + 1) % max_size;
			return front_data;
		} else {
			//Empty queue error
		}
	}
private:
	int front;
	int count;
	const int max_size;
	T* queue;
	Queue();
};

The above code declares a template queue class in C++, based upon an array of max size. It also directly stores the array index corresponding to the element at the front of the queue and the count of elements in the queue. Like the previous stack implementation, the default constructor is blocked to force the user into specifying a max size.

The enqueue function (if the queue isn't full) sets the array element at the back of the queue to the user input data and then increments the element count. The array index for the back of the queue is calculated by adding the element count to the front index and then taking the modulo with max size. The modulo is used to keep the number within the array index bounds (between 0 and max_size - 1). This means the queue is allowed to cycle around the array. The dequeue function (if the queue isn't empty) reduces the element count, retrieves the data at the current front of the queue and then moves the front of the queue forward by an element.

An example of operations performed on an array based queue. Notice how the queue cycles around the array, a result of the use of modulo arithmetic in our implementation.
An example of operations performed on an array based queue. Notice how the queue cycles around the array, a result of the use of modulo arithmetic in our implementation.

Linked list based implementation

template <class T>
class Queue {
public:
	Queue() : front{nullptr}, back{nullptr} {}
	~Queue() {
		while (front != nullptr) {
			Node* previous{front};
			front = front->next;
			delete previous;
		}
	}
	bool Empty() const{
		return front == nullptr;
	}
	void Enqueue(const T new_data) {
		Node* new_node{new Node};
		new_node->data = new_data;
		new_node->next = nullptr;
		if (Empty()) {
			new_node->prev = nullptr;
			front = new_node;
		} else {
			new_node->prev = back;
			back->next = new_node;
		}
		back = new_node;
	}
	T Dequeue() {
		if (!Empty()) {
			Node* current_front{front};
			T front_data{front->data};
			front = front->next;
			if (front != nullptr) {
				front->prev = nullptr;
			}
			delete current_front;
			return front_data;
		} else {
			//Empty queue error
		}
	}
private:
	struct Node {
		T data;
		Node* next;
		Node* prev;
	};
	Node* front;
	Node* back;
};

The above code declares a template queue class in C++, based upon a doubly linked list of nodes. Pointers to nodes at the front and back of the queue are stored. The constructor sets both the front and back to null pointers, signifying an empty queue.

The enqueue function creates a new node and then inserts it to the tail of the linked list, which represents the back of our queue. Special care needs to be taken when the list is empty, as the new node then becomes the front and back of the queue. The dequeue function deletes the front node, moves the front pointer to the next element in the queue and returns the data from the deleted element.

An example linked list based queue, storing three elements. The arrangement of pointers is clearly illustrated.
An example linked list based queue, storing three elements. The arrangement of pointers is clearly illustrated.

Double ended queue

A double ended queue, abbreviated as a deque, is a more generalised type of queue. It allows elements to be inserted and removed from both the front and the back of the queue.

Uses

Like all other data structures, stacks and queues should be used when their attributes are suitable for the problem. Some examples being:

  • Handling the undo function of states in a program. When the user makes a change, push the new program state onto the stack. Pressing the undo button will then pop a past state off the stack and load it into the program.
  • The current functions that are running within a program, alongside their parameters and local variables, are stored within a stack. This known as the call stack.
  • A real life example of a stack would be a pile of dirty plates that need washing up.
  • The computer's operating system will use a queue to handle the scheduling of processes that need executing by the CPU.
  • Queues can also be used for applications analogous to real life queues, such as booking tickets or buying goods online.

Alternative data structures

Questions & Answers

    © 2018 Sam Brind

    Comments

      0 of 8192 characters used
      Post Comment

      No comments yet.

      working