Stacks vs. Queues

Stacks and queues are both very commonly used data structures. They dynamically store and retrieve data items in two different ways. Let’s take a look at these two principles, so we can understand what differences they have and where their uses may be applicable.

Definition:

Stacks and queues are both abstract data structures and the definition of their structure is based on their behaviour, not their implementation.

Stacks and queues are collection of objects stored in a particular order. They are linear because their elements form a sequence. The main difference between them is their mechanism to add and remove elements.

Stacks

Stacks are last-in-first-out (LIFO) structures – The first element added to a stack is the last one to be removed and the last element added to a stack is the first to be removed.

Operations on stack:

 – Push – Pushes (stores) an element on the stack.

How it works: Checks if the stack is full. If it is full, produces an overflow error and exit. If the stack is not full, then increments top to point the next empty space. Adds data element to the stack location, where the top is pointing and returns success.

 – Pop – Removes (accesses) an element from the stack.

How it works: Checks if the stack is empty. If it is empty, produces an underflow error and exits. If the stack is not empty, then accesses the data element at which the top is pointing. Decreases the value of top by 1 and returns success.

Only one pointer is used. It points to the top of the stack.

Queues

Queues are first-in-first-out (FIFO) structures – 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.

Operations on queue:

– Enqueue − Adds (stores) an item to the queue.

How it works: Checks if the queue is full. If the queue is full, produces overflow error and exit. If the queue is not full, increments the rear pointer to point the next empty space. Adds data element to the queue location, where the rear is pointing and returns success.

– Dequeue − Removes (accesses) an item from the queue.

How it works: Checks if the queue is empty. If the queue is empty, produces underflow error and exit. If the queue is not empty, accesses the data where the front is pointing. Increments front pointer to point to the next available data element and returns success.

Two pointers are used to refer the front and rear end of the queue.

Random access is not allowed in both stacks and queues. You cannot add or remove an element from the middle.

Implementation and Application

Both stacks and queues can be implemented using an array or linked list. The main difference between them is that an array based implementation requires a maximum size but a linked list based implementation can dynamically grow. An oversized array is usually used if a suitable maximum size can’t be chosen in advance thus leading to large amounts of wasted memory. However, a linked list uses more memory than an array, to store the same number of elements, due to the additional storage of pointers. The operations and functionality are the same no matter the implementation. You choose to use the array or the linked list type for performance improvements.

Examples of application:

• Stacks:
  • Backtracking
  • Expression conversion and parsing
  • Undo command
• Queues:
  • CPU scheduling
  • Synchronization
  • Handling of interrupts in real-time systems

Key Differences

• Working principle to add and remove elements – Stacks are last-in-first-out (LIFO) / Queues are first-in-first-out (FIFO)
• Stack performs two operations known as push and pop while in queue they’re known as enqueue and dequeue.
• Stacks have only one open end and that is the reason for using only one pointer to refer to the top of the stack. Queues use two pointers to refer front and the rear end of the queue.