Data Structures – Stacks and Queues

/ Computer Science, Data Structures / By

Data Structures - Stacks and Queues

Next data structure we’ll look at are stacks and queues. They are both linear data structures and they follow specific rules for insertion and deletion of elements.

Definition

Stacks are FILO (First in Last Out) or LIFO ( Last In First Out). This means that the first element you put into the stack will be the last one to be removed from the stack. One analogy that always comes up is a stack of plates, plate on the top ( last one to be put on the stack ) will be removed first, and to get to one at the bottom you first need to remove every other one. Methods preformed in the stack are the following:

  1. Push – Putting element on top of the stack
  2. Pop – removing element from the top of the stack
  3. Top ( or Peek ) – previewing the top of the stack
  4. isEmpty

Queues work the opposite way, they are a FIFO ( First In First Out ) data structure. Imagine a list of queued songs on Spotify, the first one you put in will be the one that’s played next. Methods of a queue are:

  1. Enqueue – add the element at the end of the queue
  2. Dequeue- remove the first element from the queue
  3. Front – first element ( next one to be dequeued )
  4. Rear – last element ( latest one that was enqueued )

Stack applications and implementation

Stack have a variety of uses and some are:

  1. Converting from infix to postfix notation
  2. Backtracking algorithms – see this post for more in depth explanation of backtracking
  3. Memory management in modern programming languages – handling operations, taking arguments and parameters from the stack and returning results back on the stack, stacks are a necessity for all recursive operations, when you try to push some data on a stack that exceeds the stack limit stack overflow occurs
  4. Algorithms like Tower of Hanoi, topological sorting, Graham scan, agglomerative hierarchical clustering…

They can be implemented by arrays or by linked lists. We’ll implement them as always in C++ but other languages can be found on my GitHub.

There are advantages and disadvantages of both approaches:

Array implementation:

  • Advantages – memory efficient, easy to implement
  • Disadvantages – not dynamic

Implementing with arrays is pretty straight forward, we keep the index of the last added element, when we add an element we increment the top index, when we remove we decrement it.

//Implementation using arrays
class StackArray
{
private:
    int top;
public:
    StackArray() { top = -1; }
    int stackArray[1000];
    bool Push(int value)
    {
        if(top >= 999) { return false; }
        stackArray[++top] = value; //Increment top and add a value
        return true;
    }

    int Pop()
    { 
        if(!IsEmpty()) 
        {
            return stackArray[top--]; //Return the value then decrement the top 
        }
        else
        {
            return 0; //Stack is empty
        }
    }

    int Peek()
    {
        return stackArray[top]; //Return the top value
    }

    bool IsEmpty() 
    { 
        return top < -1;
    }
};

Linked lists

  • Advantages – dynamic, you can expand the stack as long as you need
  • Disadvantages – pointers require more memory to store

When implementing with linked lists this is the logic:

  • Our top element is the head of the list
  • When we push an element into the stack we just replace the current head node with the new one
class StackNode
{
public:
    StackNode* next;
    int data;
		StackNode(int value)
		{
				data = value;
				next = NULL;
		};
};

class StackLL
{
    StackNode* head = nullptr;
public:
    bool Push (int value)
    {
        StackNode* newElement = new StackNode(value);
        newElement->next = head; 
        head = newElement; //Make new element the new head
    }

    int Pop ()
    {
        if(!IsEmpty())
        {
            int toPop = head->data;
            StackNode* temp = head; //This is so we can free up the memory later
            head = head->next; //Make second element the new top 
            delete(temp); //Free up memory
            return (toPop);   
        }
        else
        {
            return 0; //Stack is empty
        }
    }

    int Peek ()
    {
        return head->data;
    }

    bool IsEmpty ()
    {
        return ( !head );
    }
};

Queues Application and Implementation

Queues are used when we have some task or data that needs to be processed later, like a scheduler or a buffer. Another application is the implementation of breath first search algorithm. Same as stacks, queues can be implemented using arrays or linked lists.

In the array implementation we need to keep track of two indices, front and rear, indices to which we add/remove values. To solve the problem of out of bunds index when incrementing front and rear we use circular queue. This means that we always preform a modulo operation when incrementing the index of front and rear so that we stay in bounds.

  • Advantages – ease of implementing
  • Disadvantages – static data type, can’t be expanded
class QueueArray
{
    int front, rear, size, capacity;
    int *queueArray;
public:
    QueueArray(int capacity)
    {
        front = size = 0;
        rear = -1;
        queueArray = new int[capacity];
    }
    
    void Enqueue(int value)
    {
        if(size == capacity) { return; }
        rear = (rear+1)%capacity;
        queueArray[rear] = value;
        size++;
    }
    
    int Dequeue()
    {
        if(IsEmpty()) { return 0; }
        int toDequeue = queueArray[front];
        front = (front+1)%capacity;
				size--;
        return(toDequeue);
    }

    int IsEmpty()
    {
        return (size == 0);
    }
};

When implementing with linked lists we instead of indices store pointers to front and rear element. Methods are the same.

//Implementation using Linked Lists
class QueueNode
{
public:
    int data;
    QueueNode* next;
    QueueNode(int value)
    {
        data = value;
        next = nullptr;
    }
};

class QueueLL
{
    QueueLL()
    {
        front = rear = nullptr;
    }
public:
    QueueNode* front, * rear;

    void Enqueue(int value)
    {
        QueueNode* newElement = new QueueNode(value);
        if(IsEmpty()) //If it's the first element to be added we set both front and rear
        {
            front = rear = newElement;
            return;
        }

        rear->next = newElement;
        rear = newElement;
    }

    int Dequeue()
    {
        if(IsEmpty()) { return 0; }

        int toDequeue = front->data;
        QueueNode* temp = front; //Temp node to free up memory later
        front->next = front;
        if(front == nullptr) //If front is null then set rear to null as well
        { 
            rear = nullptr; 
        }
        delete(temp);//Clear memory
        return toDequeue;
    }

    bool IsEmpty()
    {
        return rear == nullptr;
    }
};

Other types of Queues

Priority Queue – This version of queue sorts the elements based on some filter or function, for example bigger values have higher priority, those with higher priority are served first, on the topic of implementing a priority queue I’ll have a different article since it uses heaps and we first need to go over that.

Deque – double-ended queue, supports adding an removing elements from both ends.

Archives
Recent Posts