Skip to content

Stack and Queue

Stack1

It is an abstract, linear data type with a predefined capacity (or boundary). It's follow Last In First Out (LIFO) or First In Last Out (FILO) ordering.

Let us conceptualize stacks using a stack of plates placed in a box. The first plate placed in the stack (the plate at the bottom of the stack) will be the last one to be removed, and the plate added last would be the first to be removed.

-----
| 3 | // Last plate placed (Top of the stack)
| 2 |
| 1 | // First plate placed
-----

Queue1

It similar to stack, which is also a linear structure but follows a First In First Out (FIFO) order. Queues are open from both ends: one end for inserting data (enqueue), and the other end for removing data (dequeue). A stack is only open from one end.

When it comes to queues, think of a check out counter at your favorite grocery store. The first person in the checkout line will be attended to first before others, and the last person in line will be attend to last. This is how a queue works. It has two ends, front and rear. Elements enter from the rear and leave from the front.

[ Counter ]
    | 1 | <- Front (First person in line)
    | 2 |
    | 3 | <- Rear (Last person in line)

Type of Queue2

  1. Circular Queue (Ring Buffer)

    It is a simple queue with a fixed size. Its time complexity is O(1) for both enqueue and dequeue operations.

    • Memory Management: The unused memory locations in the case of ordinary queues can be utilized in circular queues.
    • Traffic system: In a computer-controlled traffic system, circular queues are used to switch on the traffic lights one by one repeatedly as per the time set.
    • CPU Scheduling: Operating systems often maintain a queue of processes that are ready to execute or that are waiting for a particular event to occur.

  2. Priority Queue

    It is a type of queue where each element has a priority assigned to it. Elements with higher priority are dequeued before elements with lower priority.

    • Operating systems: Priority queues are used in operating systems for task scheduling.
    • Networking: Priority queues are used in networking for quality of service (QoS) management.

  3. Double-Ended Queue (Deque)

    It is a queue that allows insertion and deletion of elements from both the front and the rear end.

    • Undo functionality: Deques are used in applications that require undo functionality.
    • Implementing stacks and queues: Deques can be used to implement both stacks and queues.

  4. Input-Restricted Queue

    It is a queue where deletion can be performed from both ends, but insertion can only be done from one end.

    • Operating systems: Input-restricted queues are used in operating systems for job scheduling.

  5. Output-Restricted Queue

    It is a queue where insertion can be performed from both ends, but deletion can only be done from one end.

    • Operating systems: Output-restricted queues are used in operating systems for job scheduling.

Summary

For a stack we remove the most recently added element, but for a queue, we remove the “oldest” element. They differ in how elements are removed.

  1. Data structures 101: How to use stacks and queues in Java ↩↩

  2. Different Types of Queues and its Applications ↩