How Queue and Stack data structures work?

Introduction

Data structures are crucial in computer science, and two of the most fundamental ones are stacks and queues. In this blog post, we will take a closer look at these data structures and their implementation.

Queues

A queue is a collection of elements. It operates like a line of customers waiting to pay a cashier:

• When new buyers arrive, they go to the end of the line, which is how the insertion operation works in a queue.
• The cashier always serves the customer at the beginning of the line, which is similar to reading from the queue.
• When the customer completes the purchase, they leave the line. This represents the delete operation.

The customer who has been in the line for the longest time is the first to leave. We call this property first-in, first out (FIFO). When working with queues, the insert, delete, and read operations are usually called enqueue, dequeue, and front.

But how can we implement a queue?

We can use an array of size N to efficiently implement the queue data structure that can store up to N elements. Note that the queue size is different from the underlying array size. To distinguish between the two, we will refer to:

• the number of elements in the queue as size, and;
• the total number of slots in the array as capacity.

The queue data will be stored in the array, but not every slot will have an element. So, we need to know the queue’s beginning and end. We call them the head and the tail. The head points to the first element in the queue, while the tail points to the slot after the last element in the queue. We also store the size of the queue.

template<typename T>
class Queue {
public:
    Queue(int capacity) : capacity_{capacity} {
    array_ = new T[capacity];
  }

  ~Queue() {
    delete array_;
  }

private:
  int capacity_;
  int size_{0};
  int head_index_{0};
  int tail_index_{0};
  T* array_;
};

Enqueue an element

To enqueue a new element, we add it after the last element. This is an index that the tail points to. After adding an element, we move the tail to the next slot.

  void enqueue(const T& element) {
    if (size_ >= capacity_) {
      throw std::runtime_error("Failed to enqueue an element because the queue is full.");
    }
    array_[tail_index_] = element;
    tail_index_ = (tail_index_ + 1) % capacity_;
    size_++;
  }

If there is no more space in the underlying array, which we check by comparing the size and the capacity, we raise an error. An alternative is to create a bigger array and move the elements there, then add the new element, which is what most libraries do.

To change the capacity of the array, we create a new array with the desired capacity, then move the elements from the current array to the new one. To move the elements, we distinguish between two cases:

• When the head_index <= tail_index, move the elements from the range [head_index, ...tail_index) at the beginning of the new array.
• When the head_index > tail_index, move the elements in two stages. Firstly, move the elements from [head_index, capacity) to the beginning of the new array, i.e. [0, capacity - head_index]. Secondly, append the elements in [0, tail_index) to the new array.

We also have to ensure that we free the old array because it’s not used anymore, and update the head and the tail to match the new layout.

...
public:
  void dequeue(const T& element) {
    if (size_ >= capacity_) {
      expand();
    }
    array_[tail_index_] = element;
    tail_index_ = (tail_index_ + 1) % capacity_;
    size_++;
  }

private:
...
    void expand() {
    change_array_capacity(capacity_ * 2);
  }

  void change_array_capacity(int new_capacity) {
    T* new_array = new T[new_capacity];
    if (head_index_ < tail_index_) {
      move(array_, head_index_, tail_index_, new_array, 0);
    } else {
      move(array_, head_index_, capacity_, new_array, 0);
      move(array_, 0, tail_index_, new_array, capacity_ - head_index_);
    }
    delete array_;

    array_ = new_array;
    capacity_ = new_capacity;
    head_index_ = 0;
    tail_index_ = size_;
  }

  void move(T* src, int start, int end, T* dst, int offset) {
    memcpy(dst + offset, src + start, (end - start) * sizeof(T));
  }

Dequeue the element

To dequeue the first element, we change the head to point to the next element. We don’t have to explicitly delete the element from the array since the head and the tail already provide enough information.

  void dequeue() {
    if (empty()) {
      throw std::runtime_error("Failed to dequeue the element because the queue is empty.");
    }
    size_--;
    head_index_ = (head_index_ + 1) % capacity_;
  }

Alternatively, if there are too few elements compared to the capacity of the array, we can save some space by shrinking the underlying array size.

...
public:
    void pop() {
    if (empty()) {
      throw std::runtime_error("Failed to pop the element because the queue is empty.");
    }
    size_--;
    head_index_ = (head_index_ + 1) % capacity_;
    if (size_ < capacity_ / 3) {
      shrink();
    }
  }

private:
  void shrink() {
    change_array_capacity(capacity_ / 2);
  }
  ...

Note that we shrink the array by half only if less than a third is used. This is to avoid the edge case where a single element is pushed and then popped, which may lead to expanding and shrinking on each operation.

Read the element

When using queues, we usually want to read the first element. We can implement this by returning the element stored at the slot that the head points to.

  const T& front() const {
    if (empty()) {
      throw std::runtime_error("Failed to get the front element because the queue is empty.");
    }
    return array_[head_index_];
  }

Wrap-Around Case

You may notice that after enqueuing and dequeuing elements for some time, the head and the tail would eventually reach the end of the array. Even though there may only be a few elements in the queue, we could still run out of free slots unless we do something about it.

To address this problem, once the tail reaches the end, we move it to the beginning of the array. This is, of course, assuming that there is enough space.

We have already incorporated this idea in the above solution by taking a modulo after incrementing the indexes by 1.

We use the same idea when dequeuing elements and incrementing the head.

Do we need to track the size?

You may be wondering why we track the size. Can’t we derive it given the head and the tail? For example, can we subtract the head from the tail while also handling the wrap-around case to compute the size?

int size() {
    return (tail_index - head_index + capacity) % capacity // ??????
}

Well, almost. The problem is that we need to distinguish between the queue being empty and using the full capacity. In both cases, the head and the tail would be the same, so we need more information to distinguish between the two states.

Queue Use-Case Example

Let’s see an example of a problem that a queue can solve.

Imagine writing a server that receives requests to execute a task as soon as possible.

One way this could work is for the server to receive a task and immediately start processing it. But what happens if there is a burst of tasks and our server can only process one at the time? The new task would be dropped, unless the server stores them somewhere.

Instead of dropping new tasks while the server is busy, they are added to the queue. The server would then process the task from the queue in order they were received.

In general, queues are very useful for algorithms that need to delay execution of tasks while preserving the order.

We will see more examples when we talk about graph algorithms in later blog posts.

Stacks

A stack operates like a bunch of dirty plates placed on each other:

• When you finish eating, you may put a plate on top of the pile. This how the insertion operation works in a stack.
• If you want to wash the dishes, you will take the plate from the top of the pile. This is how the deletion operation works.
• When you look at the pile of dirty plates, you only see the top one, which is how the read operation works.

The plate that was last added on top of the pile is the first to be washed. We call this property last-in, first-out (LIFO). When working with stacks, insert, delete, and read operations are usually called push, pop, and top.

How to implement a stack?

Similar to queues, we can use an array of size N to efficiently implement a stack that can store up to N elements. We will refer to:

• the number of elements in the stack as size, and;
• the total number of slots as capacity.

The elements in the stack will be stored in the array slots. The beginning of the array will represent the bottom of the stack, and it will always be at index zero. Since we can only add and delete elements from the top of the stack, we need to know the index of the top element. This is a slot at index size - 1.

Push an element

To push a new element, we add it after the last element, which is the index equal to the size. After pushing an element, we can increment the size. If no more space exists in the array, we can raise an error or create a bigger array. This is the same idea that we used to resize the queue.

Pop the element

To pop the element, we can simply decrement the size by 1.

Read the element

Finally, to read the top of the stack, we return the element at index size - 1.

Stack Use-Case Example

Let’s see an example of a problem that a stack can help us solve.

Imagine that you are implementing a web browser and want to implement back and forward functionality. For example, say that you are at techwithnikola.com website and click on the “About Me” page. After reading the post you may want to go back and you press the back button in your browser. The browser remembers that the previous page was techwithnikola.com and takes you there. Similarly, the go forward functionality would take you to the “About Me” page again.

You may notice that the last visited page is also the first one that you will visit after going back or forward, which is basically the same as the last-in, first-out policy.

So how can we solve this?

We can use two stacks: one for storing the back pages, and one for storing the forward pages. We will also keep track of the active page.

When you open a new page, the current active page is pushed on the backward stack.

To go back, we push the active page to the forward stack, update the active page to the top of the backwards stack, and finally pop the page from the backwards stack.

The approach is similar when going forward, except that we invert the backwards and forward stacks.

Oh, and there is one more thing. For completeness, imagine that you went a couple of pages backwards, then opened a page without using the forward button. In this case, we’d like to forget about the forward history, so we pop all the elements from the forward stack.

Conclusions

All operations in both stacks and queues provide constant run-time complexity, and linear memory complexity.

Stacks operate on the last-in, first-out principle, while queues use the first-in, first-out principle. This means that they provide different ways of accessing and manipulating data, making them useful for various types of problems.