Quick Summary: A Stack is a linear data structure operating on the LIFO (Last-In, First-Out) principle, where insertions and deletions happen exclusively at one end called the TOP. A Queue is a linear data structure operating on the FIFO (First-In, First-Out) principle, where insertions occur at the REAR end and deletions occur at the opposite FRONT end.
Stacks and queues are two of the most fundamental abstract data types (ADTs) in computer science, used extensively by operating system schedulers, memory managers, parsers, and graph traversal algorithms.
STACK |
QUEUE |
|---|---|
Operational Principle: In a stack, the insertion and deletion operations take place at only one end called the TOP end (LIFO - Last-In, First-Out). |
Operational Principle: In a queue, insertion takes place at one end (REAR) and deletion takes place at the other end (FRONT) (FIFO - First-In, First-Out). |
Deletion Order: In a stack, the element which is inserted last is the first to be deleted or popped. |
Deletion Order: In a queue, the element which is inserted first is the first to be deleted or dequeued. |
Pointer Requirements: A stack requires only one pointer index, called TOP, to track the active end of the stack. |
Pointer Requirements: A queue requires two pointers: FRONT (for reading/deletion) and REAR (for writing/insertion). |
Real-World Analogy: A pile of trays in a cafeteria or a stack of dinner plates (you add to the top and take from the top). |
Real-World Analogy: Students waiting in a line at a college registration counter (the first student in line is served first). |
Memory Space Utilization: In a stack, there is no internal fragmentation or wasted slots between elements because all operations expand and contract at the TOP. |
Memory Space Utilization: In a simple linear queue, even if front space is freed by deletions, rear may hit the array boundary preventing new insertions (resolved by Circular Queues). |
Primary Operations: |
Primary Operations: |
Variants & Types: Single Stack, Min/Max Stack, Call Stack. |
Circular Queue, Priority Queue, Double-Ended Queue (Deque), Blocking Queue. |
Key Computing Applications: Function call stack recursion, Undo/Redo operations, Expression syntax parsing (Infix to Postfix), Depth-First Search (DFS). |
CPU process scheduling (Round Robin), Printer spooling buffers, Breadth-First Search (BFS), Asynchronous messaging (RabbitMQ, Kafka). |
#define MAX 100
int stack[MAX];
int top = -1; // Single pointer tracking top
void push(int value) {
if (top == MAX - 1) {
printf("Stack Overflow\n");
return;
}
stack[++top] = value; // Increment top and insert
}
int pop() {
if (top == -1) {
printf("Stack Underflow\n");
return -1;
}
return stack[top--]; // Return element and decrement top
}
#define MAX 100
int queue[MAX];
int front = -1, rear = -1; // Two pointers
void enqueue(int value) {
if ((rear + 1) % MAX == front) {
printf("Queue is Full\n");
return;
}
if (front == -1) front = 0;
rear = (rear + 1) % MAX; // Circular increment
queue[rear] = value;
}
int dequeue() {
if (front == -1) {
printf("Queue is Empty\n");
return -1;
}
int item = queue[front];
if (front == rear) { // Last element removed, reset queue
front = rear = -1;
} else {
front = (front + 1) % MAX;
}
return item;
}
Q1: If elements A, B, C, and D are pushed onto a stack in order, which element is retrieved first on pop?
Correct Answer: D
Because a stack is a LIFO structure (Last-In, First-Out), element D was pushed last, so it resides at the TOP and is popped first.
Q2: Which graph traversal algorithm relies fundamentally on a Queue data structure?
Correct Answer: B
Breadth-First Search (BFS) explores all neighboring nodes level-by-level, which requires a FIFO Queue to process vertices in the exact order they were discovered.
Q3: What error condition occurs when attempting to pop an element from an empty stack?
Correct Answer: B
Attempting to remove an item from an empty stack is termed Stack Underflow (when top == -1). Attempting to push into a full stack is termed Stack Overflow.
A Deque is a generalized queue where insertion and deletion operations can occur at both ends (front and rear). A Deque can function as both a Stack and a Queue depending on which methods are invoked.
Every time a function is called, an activation record (stack frame) containing its local variables, parameters, and return instruction address is pushed onto the system Call Stack. When the function finishes execution, its frame is popped, returning control to the caller.
In a standard queue, elements leave in strict FIFO order. In a Priority Queue, each element is assigned an associated priority key. The element with the highest priority is always dequeued first, regardless of when it arrived (typically implemented using a Binary Heap).
Yes! By using an inbox stack for enqueue operations and an outbox stack for dequeue operations, elements are reversed twice, achieving FIFO order with amortized O(1) time complexity.
Stack Overflow occurs when recursive functions fail to recognize or hit their base termination case, continually pushing activation frames onto the call stack until allocated stack memory is completely exhausted.
Both Stacks and Queues are strictly linear data structures because elements form a one-dimensional logical sequence where each element has a unique predecessor and successor (except the ends).