What Are Data Structures? Stacks & Queues

Updated on May 15, 2018

What is a data structure?

A data structure is a method for organising a set of data. The structure is defined by how the data is stored and how operations, such as data access, insertion and deletion, are performed on the stored data. Data structures are essential tools for programmers, as each structure has a set of benefits that make it useful for solving certain types of problem.

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 (push) and removals (pop) occur at the same end of the stack.
An example stack, storing a group of integers. Note that both insertions (push) and removals (pop) 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 (enqueue) and removals (dequeue) occur at opposite ends of the queue.
An example queue, storing a group of integers. Note that the insertions (enqueue) and removals (dequeue) 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

      This website uses cookies

      As a user in the EEA, your approval is needed on a few things. To provide a better website experience, owlcation.com uses cookies (and other similar technologies) and may collect, process, and share personal data. Please choose which areas of our service you consent to our doing so.

      For more information on managing or withdrawing consents and how we handle data, visit our Privacy Policy at: https://owlcation.com/privacy-policy#gdpr

      Show Details
      Necessary
      HubPages Device IDThis is used to identify particular browsers or devices when the access the service, and is used for security reasons.
      LoginThis is necessary to sign in to the HubPages Service.
      Google RecaptchaThis is used to prevent bots and spam. (Privacy Policy)
      AkismetThis is used to detect comment spam. (Privacy Policy)
      HubPages Google AnalyticsThis is used to provide data on traffic to our website, all personally identifyable data is anonymized. (Privacy Policy)
      HubPages Traffic PixelThis is used to collect data on traffic to articles and other pages on our site. Unless you are signed in to a HubPages account, all personally identifiable information is anonymized.
      Amazon Web ServicesThis is a cloud services platform that we used to host our service. (Privacy Policy)
      CloudflareThis is a cloud CDN service that we use to efficiently deliver files required for our service to operate such as javascript, cascading style sheets, images, and videos. (Privacy Policy)
      Google Hosted LibrariesJavascript software libraries such as jQuery are loaded at endpoints on the googleapis.com or gstatic.com domains, for performance and efficiency reasons. (Privacy Policy)
      Features
      Google Custom SearchThis is feature allows you to search the site. (Privacy Policy)
      Google MapsSome articles have Google Maps embedded in them. (Privacy Policy)
      Google ChartsThis is used to display charts and graphs on articles and the author center. (Privacy Policy)
      Google AdSense Host APIThis service allows you to sign up for or associate a Google AdSense account with HubPages, so that you can earn money from ads on your articles. No data is shared unless you engage with this feature. (Privacy Policy)
      Google YouTubeSome articles have YouTube videos embedded in them. (Privacy Policy)
      VimeoSome articles have Vimeo videos embedded in them. (Privacy Policy)
      PaypalThis is used for a registered author who enrolls in the HubPages Earnings program and requests to be paid via PayPal. No data is shared with Paypal unless you engage with this feature. (Privacy Policy)
      Facebook LoginYou can use this to streamline signing up for, or signing in to your Hubpages account. No data is shared with Facebook unless you engage with this feature. (Privacy Policy)
      MavenThis supports the Maven widget and search functionality. (Privacy Policy)
      Marketing
      Google AdSenseThis is an ad network. (Privacy Policy)
      Google DoubleClickGoogle provides ad serving technology and runs an ad network. (Privacy Policy)
      Index ExchangeThis is an ad network. (Privacy Policy)
      SovrnThis is an ad network. (Privacy Policy)
      Facebook AdsThis is an ad network. (Privacy Policy)
      Amazon Unified Ad MarketplaceThis is an ad network. (Privacy Policy)
      AppNexusThis is an ad network. (Privacy Policy)
      OpenxThis is an ad network. (Privacy Policy)
      Rubicon ProjectThis is an ad network. (Privacy Policy)
      TripleLiftThis is an ad network. (Privacy Policy)
      Say MediaWe partner with Say Media to deliver ad campaigns on our sites. (Privacy Policy)
      Remarketing PixelsWe may use remarketing pixels from advertising networks such as Google AdWords, Bing Ads, and Facebook in order to advertise the HubPages Service to people that have visited our sites.
      Conversion Tracking PixelsWe may use conversion tracking pixels from advertising networks such as Google AdWords, Bing Ads, and Facebook in order to identify when an advertisement has successfully resulted in the desired action, such as signing up for the HubPages Service or publishing an article on the HubPages Service.
      Statistics
      Author Google AnalyticsThis is used to provide traffic data and reports to the authors of articles on the HubPages Service. (Privacy Policy)
      ComscoreComScore is a media measurement and analytics company providing marketing data and analytics to enterprises, media and advertising agencies, and publishers. Non-consent will result in ComScore only processing obfuscated personal data. (Privacy Policy)
      Amazon Tracking PixelSome articles display amazon products as part of the Amazon Affiliate program, this pixel provides traffic statistics for those products (Privacy Policy)