Difference between Stack and Queue

Q: What is the main difference between a stack and a queue?

A stack is LIFO (Last In, First Out): the newest element is removed first. A queue is FIFO (First In, First Out): the oldest element is removed first.

Q: Where are elements added and removed in each?

Stack: added and removed at the same end, the top. Queue: added at the rear and removed from the front.

Q: What are the operation names for a stack and a queue?

Stack: push, pop, peek. Queue: enqueue ( offer in Java), dequeue ( poll in Java), peek. All of them are O(1).

Q: Show a stack and a queue in Java with the same input.

Java example: import java.util.ArrayDeque; import java.util.Deque; import java.util.Queue; public class StackVsQueue { public static void main(String[] args) { Deque stack = new ArrayDeque<>(); Queue queue = new ArrayDeque<>(); for (int i = 1; i <= 3; i++) { stack.push(i); queue.offer(i); } System.out.println("Stack pop: " + stack.pop()); // 3 (last in) System.out.println("Queue poll: " + queue.poll()); // 1 (first in) } }

Q: Which is used for DFS and which for BFS?

Depth-first search uses a stack (or recursion), because it goes as deep as possible before backtracking. Breadth-first search uses a queue, because it visits nodes level by level in the order they were discovered.

Q: Give real-world examples of a stack and a queue.

Stack: undo history, the browser back button, a pile of books. Queue: a line at a ticket counter, printer jobs, messages waiting to be processed.

Q: Which Java class can act as both a stack and a queue?

ArrayDeque (and LinkedList ) implement Deque, a double-ended queue. Use push / pop for stack behaviour, and offer / poll for queue behaviour.

Difference between Stack and Queue

Hey, In this article you are going to learn difference between Stack and Queue in terms of their structure, memeory uses, performance, implementation and more.

What is a Stack Data Structure ?

A stack is a linear (ordered) data structure used to store and manipulate a collection of data elements. Stack follows the LIFO (Last In First Out) principle, which means the last element added to the stack will be removed first from the stack.

In a stack, insertion and deletion of an element can be done from one end known as the top of the stack.

The stack data structure is commonly used in programming for tasks such as managing function calls, undo/redo functionality in applications, parsing expressions, backtracking algorithms, maintaining browser history, and many more.

What is a Queue Data Structure?

A Queue is a linear data structure to store and manipulate the data elements. The queue data structure apply the concept of "First in, First out" (FIFO), which means the first added element into the queue to be the first removed from the queue. Queues do not allow random insertion and deletion operations.

A Queue is open at both ends, which enables insert operations to be performed at one end called REAR or TAIL and delete operations to be performed at another end called FRONT or HEAD.

Difference between Stack and Queue Data Structure

Characteristic	Stack	Queue
Princal Flow	Follows LIFO (Last In First Out) principle, which means the last element added to the stack will be removed first from the stack.	Follow FIFO (First in, First out) principle, which means the first added element into the queue to be the first removed from the queue.
Basic Operations	push(), pop(), peek()	enqueue(), dequeue(), peek(), rear()
Complexity (Amortized)	Push: O(1), Pop: O(1), Peek: O(1)	Enqueue: O(1), Dequeue: O(1), Front: O(1), Rear: O(1)
Addition of Elements	Elements are added to the top of the stack.	Elements are added to the rear (end) of the queue.
Removal of Elements	The last element added is the first one to be removed.	The first element added is the first one to be removed.
Memory Management	Managed with a single pointer (top)	Managed with two pointers (front and rear)
Overflow	Stack overflow occurs if the stack exceeds its capacity.	Queue overflow occurs if the queue exceeds its capacity.
Full Condition	When top== max-1, it means that the stack is full.	When rear==max-1, it means that the queue is full.
Implementation	Stack can be implemented using arrays or linked lists.	Queue can be implemented using arrays, linked lists, or circular buffers.

Frequently Asked Questions (FAQ)

Q1. What is the main difference between a stack and a queue?

A stack is LIFO (Last In, First Out): the newest element is removed first. A queue is FIFO (First In, First Out): the oldest element is removed first.

Q2. Where are elements added and removed in each?

Stack: added and removed at the same end, the top.
Queue: added at the rear and removed from the front.

Q3. What are the operation names for a stack and a queue?

Stack: push, pop, peek.
Queue: enqueue (offer in Java), dequeue (poll in Java), peek.

All of them are O(1).

Q4. Show a stack and a queue in Java with the same input.

StackVsQueue.java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Queue;

public class StackVsQueue {
    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 1; i <= 3; i++) {
            stack.push(i);
            queue.offer(i);
        }
        System.out.println("Stack pop: " + stack.pop());     // 3 (last in)
        System.out.println("Queue poll: " + queue.poll());   // 1 (first in)
    }
}

Q5. How do you implement a queue using two stacks?

QueueWithTwoStacks.java

import java.util.ArrayDeque;
import java.util.Deque;

public class QueueWithTwoStacks {
    private final Deque<Integer> in = new ArrayDeque<>();
    private final Deque<Integer> out = new ArrayDeque<>();

    public void enqueue(int value) {
        in.push(value);
    }

    public int dequeue() {
        if (out.isEmpty()) {
            while (!in.isEmpty()) {
                out.push(in.pop());     // reverse the order once
            }
        }
        return out.pop();
    }

    public static void main(String[] args) {
        QueueWithTwoStacks q = new QueueWithTwoStacks();
        q.enqueue(1);
        q.enqueue(2);
        q.enqueue(3);
        System.out.println(q.dequeue());   // 1
        System.out.println(q.dequeue());   // 2
    }
}

Each element moves between stacks at most once, so dequeue is O(1) amortized.

Q6. How do you implement a stack using a queue?

After each push, rotate the queue so the new element is at the front:

StackWithQueue.java

import java.util.ArrayDeque;
import java.util.Queue;

public class StackWithQueue {
    private final Queue<Integer> queue = new ArrayDeque<>();

    public void push(int value) {
        queue.offer(value);
        for (int i = 0; i < queue.size() - 1; i++) {
            queue.offer(queue.poll());   // move older elements behind the new one
        }
    }

    public int pop() {
        return queue.poll();
    }

    public static void main(String[] args) {
        StackWithQueue s = new StackWithQueue();
        s.push(1);
        s.push(2);
        s.push(3);
        System.out.println(s.pop());     // 3
    }
}

Push becomes O(n), and pop stays O(1).

Q7. Which is used for DFS and which for BFS?

Depth-first search uses a stack (or recursion), because it goes as deep as possible before backtracking. Breadth-first search uses a queue, because it visits nodes level by level in the order they were discovered.

Q8. Give real-world examples of a stack and a queue.

Stack: undo history, the browser back button, a pile of books.
Queue: a line at a ticket counter, printer jobs, messages waiting to be processed.

Q9. Which Java class can act as both a stack and a queue?

ArrayDeque (and LinkedList) implement Deque, a double-ended queue. Use push/pop for stack behaviour, and offer/poll for queue behaviour.

Q10. Do stacks and queues have different time complexities?

No. With a good implementation, insert, remove and peek are all O(1) for both, and searching is O(n) for both. They differ only in the order in which elements are removed.

Was this tutorial helpful?

Help Us Improve

Difference between Stack and Queue

What is a Stack Data Structure ?

What is a Queue Data Structure?

Difference between Stack and Queue Data Structure

Frequently Asked Questions (FAQ)