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.
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.
Array based implementation
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.
Linked list based implementation
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.
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.
Array based implementation
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.
Linked list based implementation
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.
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.
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.
For each question, choose the best answer. The answer key is below.
- Which of these data structures isn't abstract?
- What is the state of an empty stack after the following operations are performed: PUSH(2), PUSH(9), POP(), PUSH(5)?
- TOP -> 9 -> 5
- TOP -> 5 -> 9
- TOP -> 5 -> 2
- In which order are queue elements accessed?
- TOP -> 5 -> 2
Alternative data structures
Questions & Answers
Question: How are queues and stacks used in a computer operating system?
Answer: Stacks are used to store the local variables for programs that are currently running. Queues are used to schedule CPU processes, examples being the job queue, ready queue and the device queues.
© 2018 Sam Brind