Stack & Queue Data Structures

Expert Answer & Key Takeaways

In-depth study of Stack (LIFO) and Queue (FIFO) data structures, their operations, implementations, variants (Circular, Priority), and applications in computer science.

Data Structures: Stack and Queue

Data structures are fundamental to computer science, providing a way to store, organize, and retrieve data efficiently. Among the most essential linear data structures are the Stack and the Queue. These structures dictate how data is added and removed, forming the backbone of many complex algorithms and system processes. For the Basic Computer Instructor exam, a deep understanding of these concepts, their implementations, and their applications is crucial.

1. Introduction to Linear Data Structures

A data structure is said to be linear if its elements are arranged in a sequential order, one after the other. In linear data structures, each element is connected to its previous and next element. Stacks and Queues are classic examples where elements are accessed in a specific, predictable order.

2. The Stack Data Structure

A Stack is a linear data structure that follows a particular order in which the operations are performed. The order is LIFO (Last In, First Out) or FILO (First In, Last Out).

2.1 Real-World Analogy

Imagine a stack of plates at a buffet. You can only take the plate that is on the very top of the stack. When clean plates are added, they are placed on the top. The last plate placed on the stack is the first one to be removed. This perfectly illustrates the LIFO principle.

2.2 Core Operations of a Stack

The primary operations that define a stack are:

Push(data): Adds an element to the top of the stack. If the stack is full, this operation results in an overflow condition.
Pop(): Removes and returns the top element from the stack. If the stack is empty, this operation results in an underflow condition.
Peek() or Top(): Returns the top element of the stack without removing it.
isEmpty(): Returns true if the stack is empty, else false.
isFull(): Returns true if the stack is full (applicable in array-based implementations).

2.3 Implementation of Stacks

Stacks can be implemented using two primary underlying data structures: Arrays and Linked Lists.

A. Array Implementation

Using an array is the simplest way to implement a stack. We maintain an integer variable, typically called top, which keeps track of the index of the top element. Initially, top is set to -1.

#define MAX 100
int stack[MAX];
int top = -1;

void push(int data) {
    if (top == MAX - 1) {
        printf("Stack Overflow\n");
        return;
    }
    stack[++top] = data;
}

int pop() {
    if (top == -1) {
        printf("Stack Underflow\n");
        return -1;
    }
    return stack[top--];
}

Pros: Easy to implement, memory is saved as pointers are not involved. Cons: It is not dynamic. It doesn’t grow and shrink depending on needs at runtime.

B. Linked List Implementation

In a linked list implementation, every new element is inserted as a new node at the beginning (head) of the list, and every pop operation removes the node from the beginning.

struct Node {
    int data;
    struct Node* next;
};
struct Node* top = NULL;

void push(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = top;
    top = newNode;
}

int pop() {
    if (top == NULL) return -1;
    struct Node* temp = top;
    int popped = temp->data;
    top = top->next;
    free(temp);
    return popped;
}

Pros: Dynamic in size. No need to define size initially. Cons: Extra memory is required for pointers.

2.4 Complexity Analysis

Time Complexity: Push, Pop, Peek, isEmpty all take O(1) time since we only manipulate the top pointer/index.
Space Complexity: O(N) where N is the maximum number of elements the stack can hold.

2.5 Applications of Stacks

Stacks are ubiquitous in computing:

Function Calls & Recursion: The system uses a call stack to keep track of active subroutines. When a function is called, its execution context is pushed onto the stack. When it returns, the context is popped.
Expression Parsing and Evaluation: Compilers use stacks to evaluate arithmetic expressions and convert between Infix, Postfix, and Prefix notations.
Undo/Redo Operations: Text editors store previous states in a stack to enable the 'Undo' feature.
Balanced Parentheses Checking: Checking if expressions have balanced brackets (e.g., {[()]}).
Browser History: The 'Back' button works by popping the current URL from the history stack.
Depth-First Search (DFS): The DFS algorithm for traversing trees or graphs uses a stack (or recursion, which uses the call stack).

3. The Queue Data Structure

A Queue is a linear structure which follows a particular order in which the operations are performed. The order is FIFO (First In, First Out).

3.1 Real-World Analogy

Think of a queue of people waiting to buy tickets at a cinema. The person who joins the line first is served first. New people join at the end of the line.

3.2 Core Operations of a Queue

Enqueue(data): Adds an item to the rear (back) of the queue. Overflows if full.
Dequeue(): Removes an item from the front of the queue. Underflows if empty.
Front() / Peek(): Gets the item at the front without removing it.
Rear(): Gets the item at the back without removing it.

3.3 Implementation of Queues

Like stacks, queues can be implemented using Arrays or Linked Lists. A standard queue maintains two pointers: front and rear.

A. Array Implementation

#define MAX 100
int queue[MAX];
int front = -1, rear = -1;

void enqueue(int data) {
    if (rear == MAX - 1) return; // Overflow
    if (front == -1) front = 0;
    queue[++rear] = data;
}

int dequeue() {
    if (front == -1 || front > rear) return -1; // Underflow
    return queue[front++];
}

Problem with standard Array Queue: After several enqueue and dequeue operations, front shifts to the right, creating empty spaces at the beginning of the array that cannot be reused, even if the queue is technically not full. This is solved by the Circular Queue.

3.4 Types of Queues

1. Circular Queue

In a circular queue, the last position is connected back to the first position to make a circle. This efficiently utilizes the wasted array space.

Formula for Enqueue: rear = (rear + 1) % MAX
Formula for Dequeue: front = (front + 1) % MAX
Full Condition: (rear + 1) % MAX == front

2. Priority Queue

A Priority Queue is a special type of queue in which each element is associated with a priority value. Elements are served based on their priority. If elements have the same priority, they are served according to their order in the queue.

Ascending Priority Queue: Elements can be inserted in any order, but only the smallest element can be removed.
Descending Priority Queue: Only the largest element can be removed.
Implementation: Usually implemented using Heaps (Binary Heap) for O(log n) enqueue and dequeue operations.

3. Double Ended Queue (Deque)

A Deque (pronounced 'deck') is a generalized version of a queue that allows insertion and deletion at both ends (front and rear).

Input Restricted Deque: Deletions can be made at both ends, but insertion can only be made at one end.
Output Restricted Deque: Insertions can be made at both ends, but deletion can only be made at one end.

3.5 Complexity Analysis

Time Complexity: Enqueue, Dequeue, Front, Rear all take O(1) time in standard array/linked-list implementations. Priority queue operations take O(log N) using heaps.
Space Complexity: O(N).

3.6 Applications of Queues

CPU Scheduling: Operating systems use queues to manage processes waiting for CPU time (e.g., Round Robin scheduling).
Print Spooling: Print jobs are placed in a queue and processed in the order they were received.
Breadth-First Search (BFS): The BFS algorithm for traversing trees and graphs uses a queue to keep track of nodes at the current level before moving to the next level.
Handling of Interrupts: Hardware interrupts are handled in the order they arrive.
Message Queues: Used in inter-process communication (IPC) and distributed systems to pass messages asynchronously.

4. Stack vs Queue: A Comparative Summary

Feature	Stack	Queue
Working Principle	LIFO (Last In First Out)	FIFO (First In First Out)
Pointers used	Only one pointer: `top`	Two pointers: `front` and `rear`
Insertion Operation	Push	Enqueue
Deletion Operation	Pop	Dequeue
Real-life Example	Stack of books, plates	Line of people at a ticket counter
Primary Application	Expression evaluation, Recursion	CPU Scheduling, Buffer management

5. Important Infix, Prefix, and Postfix Conversions

A very common topic in the Computer Instructor exam is expression conversion using Stacks.

Infix: A + B (Operator between operands)
Prefix (Polish Notation): + A B (Operator before operands)
Postfix (Reverse Polish Notation): A B + (Operator after operands) Algorithm to Convert Infix to Postfix:

Scan the infix expression from left to right.
If the scanned character is an operand, output it.
If the character is an '(', push it to the stack.
If the character is an ')', pop and output from the stack until an '(' is encountered.
If an operator is scanned:
- While stack is not empty and precedence of the scanned operator is less than or equal to the precedence of the top of the stack, pop and output.
- Push the scanned operator to the stack.
Pop and output all remaining elements from the stack. Understanding this algorithm and the precedence of operators (like ^ > *, / > +, -) is vital for scoring well in the Data Structures section.

Course4All Editorial Board

Verified Expert

Subject Matter Experts

Comprising experienced educators and curriculum specialists dedicated to providing accurate, exam-aligned preparation material.

Pattern: 2026 Ready

Updated: Weekly

Next Topic →Linked List

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.

Stack & Queue Data Structures

Expert Answer & Key Takeaways

Data Structures: Stack and Queue

1. Introduction to Linear Data Structures

A data structure is said to be linear if its elements are arranged in a sequential order, one after the other. In linear data structures, each element is connected to its previous and next element. Stacks and Queues are classic examples where elements are accessed in a specific, predictable order.

2. The Stack Data Structure

2.1 Real-World Analogy

2.2 Core Operations of a Stack

2.3 Implementation of Stacks

A. Array Implementation

B. Linked List Implementation

2.4 Complexity Analysis

2.5 Applications of Stacks

3. The Queue Data Structure

3.1 Real-World Analogy

3.2 Core Operations of a Queue

3.3 Implementation of Queues

A. Array Implementation

3.4 Types of Queues

1. Circular Queue

2. Priority Queue

3. Double Ended Queue (Deque)

3.5 Complexity Analysis

3.6 Applications of Queues

4. Stack vs Queue: A Comparative Summary

5. Important Infix, Prefix, and Postfix Conversions

Course4All Editorial Board

Explore More Data Structures

Linked List

Tree & Graph

Searching Techniques

Sorting Techniques

Found an issue or have a suggestion?