Linear Data Structures

By the Syncfusion DevTutorials team · Last updated October 20, 2026

Use stacks (LIFO) and queues (FIFO): push, pop and peek, Queue with LinkedList and PriorityQueue, offer vs add, poll vs remove, and real applications.

Think about two everyday lines.

The first is a stack of plates in a canteen. Clean plates go on top. When you need one, you take the top plate. The last plate put down is the first one picked up.

The second is a queue at a ticket counter. New people join at the back. The person at the front is served first. The first person to arrive is the first to leave.

A stack and a queue are two of the most useful ways to store items in a line. They differ only in which end items leave from.

In simple words: a stack gives back the newest item first, and a queue gives back the oldest item first.

What You Will Learn

In this lesson, you will learn:

1. What a stack is, and the LIFO principle.
2. How to create a stack and use push, pop, peek, search, isEmpty and size.
3. Where stacks are used: undo, browser back, expressions, method calls and bracket matching.
4. What a queue is, and the FIFO principle.
5. How the Queue interface works with LinkedList and PriorityQueue.
6. The difference between add and offer, remove and poll, and element and peek.
7. Where queues are used, and how queues and stacks compare.

Start With a Working Example

Press Run.

The same three items, two different exit orders

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<String> plates = new Stack<>();
        plates.push("Plate 1");
        plates.push("Plate 2");
        plates.push("Plate 3");

        Queue<String> line = new LinkedList<>();
        line.offer("Asha");
        line.offer("Ravi");
        line.offer("Meena");

        System.out.println("Stack gives back:");
        while (!plates.isEmpty()) {
            System.out.println("  " + plates.pop());
        }

        System.out.println("Queue gives back:");
        while (!line.isEmpty()) {
            System.out.println("  " + line.poll());
        }
    }
}

Expected output:

Stack gives back:
  Plate 3
  Plate 2
  Plate 1
Queue gives back:
  Asha
  Ravi
  Meena

Both were filled in the same order. The stack returned them backwards: last in, first out. The queue returned them in order: first in, first out.

Try This

Push a fourth plate and add a fourth person. The plate comes out first. The person comes out last.

Stack

Introduction to Stack

A stack is a collection where you can only add and remove items at one end, called the top.

You cannot reach into the middle. To get to an item lower down, you must first remove everything above it.

Java has a Stack class in java.util. It is easy to read, so this lesson uses it to teach the idea. For new code, Java recommends ArrayDeque, which you will see at the end of the stack section.

LIFO Principle

A stack follows LIFO: Last In, First Out.

The most recently added item is always the first one removed.

push A      push B      push C       pop → C      pop → B
                         ┌───┐
             ┌───┐       │ C │ ← top
 ┌───┐       │ B │       │ B │       ┌───┐
 │ A │       │ A │       │ A │       │ B │        ┌───┐
 └───┘       └───┘       └───┘       │ A │        │ A │
                                     └───┘        └───┘

Creating a Stack

import java.util.Stack;

Stack<String> history = new Stack<>();
Stack<Integer> numbers = new Stack<>();

The type in angle brackets says what the stack holds. A new stack is empty.

Stack Methods

push()

push(item) adds an item to the top.

pop()

pop() removes the top item and returns it. On an empty stack, it throws an EmptyStackException.

peek()

peek() returns the top item without removing it. On an empty stack, it also throws an EmptyStackException.

search()

search(item) returns the item's distance from the top, counting the top as 1. If the item is not there, it returns -1.

isEmpty()

isEmpty() returns true when the stack holds nothing. Check it before calling pop or peek.

size()

size() returns how many items are in the stack.

Every Stack method on one pile of books

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<String> books = new Stack<>();
        System.out.println("Empty at start? " + books.isEmpty());

        books.push("Maths");
        books.push("Science");
        books.push("History");
        System.out.println("Pile: " + books);
        System.out.println("Size: " + books.size());

        System.out.println("Top book (peek): " + books.peek());
        System.out.println("Position of Maths: " + books.search("Maths"));
        System.out.println("Position of Art: " + books.search("Art"));

        String taken = books.pop();
        System.out.println("Took: " + taken);
        System.out.println("Pile now: " + books + ", top is " + books.peek());
    }
}

Expected output:

Empty at start? true
Pile: [Maths, Science, History]
Size: 3
Top book (peek): History
Position of Maths: 3
Position of Art: -1
Took: History
Pile now: [Maths, Science], top is Science

When printed, a Stack lists its items from bottom to top. So the top item, History, is shown last.

peek looked at the top without changing anything. pop actually removed it.

search("Maths") returned 3, because Maths is three books down from the top.

Stack Applications

Undo Operations

Every action you take in an editor is pushed onto a stack. Pressing Undo pops the most recent action and reverses it. Press Undo again, and the next most recent action is undone.

Browser Back Navigation

Each page you visit is pushed onto a stack. Pressing Back pops the current page and shows the one beneath it.

Undo and browser Back are both stacks

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<String> edits = new Stack<>();
        edits.push("Typed 'Hello'");
        edits.push("Made it bold");
        edits.push("Changed colour to red");

        System.out.println("Undo: " + edits.pop());
        System.out.println("Undo: " + edits.pop());
        System.out.println("Still kept: " + edits.peek());

        Stack<String> pages = new Stack<>();
        pages.push("home");
        pages.push("products");
        pages.push("product/42");

        pages.pop();
        System.out.println("Back button shows: " + pages.peek());
        pages.pop();
        System.out.println("Back button shows: " + pages.peek());
    }
}

Expected output:

Undo: Changed colour to red
Undo: Made it bold
Still kept: Typed 'Hello'
Back button shows: products
Back button shows: home

Undo reversed the newest edit first. Back went to the page just before the current one.

Expression Evaluation

Calculators use stacks to work out expressions. One simple form is postfix notation, where the operator comes after its two numbers. 3 + 4 is written 3 4 +.

The rule is short:

• When you see a number, push it.
• When you see an operator, pop two numbers, apply the operator, and push the answer.
• At the end, the answer is the only thing left on the stack.

A stack works out a postfix expression

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        String expression = "5 3 + 2 *";
        Stack<Integer> stack = new Stack<>();

        for (String token : expression.split(" ")) {
            if (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {
                int right = stack.pop();
                int left = stack.pop();
                int result = switch (token) {
                    case "+" -> left + right;
                    case "-" -> left - right;
                    case "*" -> left * right;
                    default -> left / right;
                };
                System.out.println(left + " " + token + " " + right + " = " + result);
                stack.push(result);
            } else {
                stack.push(Integer.parseInt(token));
            }
        }

        System.out.println("Answer: " + stack.pop());
    }
}

Expected output:

5 + 3 = 8
8 * 2 = 16
Answer: 16

5 3 + 2 * means (5 + 3) * 2. The stack holds 5 and 3, the + turns them into 8, then 2 is pushed, and the * turns 8 and 2 into 16.

Note the order when popping: the first pop is the right number. That matters for - and /.

Function Call Stack

The JVM uses a stack to keep track of method calls. This is called the call stack.

• When a method is called, a frame for it is pushed. The frame holds its local variables.
• When the method returns, its frame is popped, and Java goes back to the method below.

That is why the most recent call always finishes first. It is also why endless recursion causes a StackOverflowError: the call stack runs out of room.

Method calls finish in reverse order, like a stack

public class Main {
    public static void main(String[] args) {
        System.out.println("main starts");
        greet();
        System.out.println("main ends");
    }

    static void greet() {
        System.out.println("  greet starts");
        sayName();
        System.out.println("  greet ends");
    }

    static void sayName() {
        System.out.println("    sayName runs (top of the call stack)");
    }
}

Expected output:

main starts
  greet starts
    sayName runs (top of the call stack)
  greet ends
main ends

main called greet, which called sayName. The last method called, sayName, was the first to finish.

Parentheses Matching

Code editors check that every opening bracket has a matching closing bracket, in the right order. A stack makes this easy:

• Push every opening bracket: (, [ or {.
• For every closing bracket, pop the top. It must be the matching opener.
• At the end, the stack must be empty.

Check that every bracket is closed in the right order

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        String[] tests = {"(a + b) * [c - d]", "{[()]}", "(a + b]", "((x)"};

        for (String t : tests) {
            System.out.println(t + "  ->  " + (isBalanced(t) ? "balanced" : "NOT balanced"));
        }
    }

    static boolean isBalanced(String text) {
        Stack<Character> stack = new Stack<>();
        for (char c : text.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else if (c == ')' || c == ']' || c == '}') {
                if (stack.isEmpty()) {
                    return false;
                }
                char open = stack.pop();
                if ((c == ')' && open != '(') || (c == ']' && open != '[') || (c == '}' && open != '{')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

Expected output:

(a + b) * [c - d]  ->  balanced
{[()]}  ->  balanced
(a + b]  ->  NOT balanced
((x)  ->  NOT balanced

In (a + b], the ] pops a (, which does not match. In ((x), one ( is still on the stack at the end.

Stack vs ArrayDeque

The Stack class is old. It extends Vector, so it also allows reading by index, which a true stack should not. Its methods are also locked for threads, which makes it slower.

For new code, use ArrayDeque as a stack. It has the same push, pop and peek methods.

Deque<String> stack = new ArrayDeque<>();
stack.push("A");
stack.pop();

One difference: an empty ArrayDeque throws NoSuchElementException from pop(), and returns null from peek().

Queue

Introduction to Queue

A queue is a collection where items are added at the back and removed from the front.

Think of people waiting for a bus. Newcomers join the back. The person at the front boards first.

The front is called the head. The back is called the tail.

FIFO Principle

A queue follows FIFO: First In, First Out.

The item that has waited longest is always the next one out.

           offer(Ravi)                    poll() → Asha
 head                     tail      head                tail
 ┌──────┬──────┬───────┐            ┌──────┬───────┐
 │ Asha │ Ravi │ Meena │   ──►      │ Ravi │ Meena │
 └──────┴──────┴───────┘            └──────┴───────┘
  leaves here    joins here

Queue Interface

Queue is an interface in java.util. It describes what a queue can do. You create an object from a class that implements it.

It has two versions of each action. One throws an exception when it fails. The other returns a special value instead.

Common classes that implement Queue:

LinkedList Queue

LinkedList implements both List and Queue. When you store it in a Queue variable, you only see the queue methods.

A LinkedList used as a queue

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> tickets = new LinkedList<>();

        tickets.offer("T-101");
        tickets.offer("T-102");
        tickets.offer("T-103");
        System.out.println("Queue: " + tickets);
        System.out.println("Next up: " + tickets.peek());

        System.out.println("Serving " + tickets.poll());
        System.out.println("Serving " + tickets.poll());

        tickets.offer("T-104");
        System.out.println("Queue now: " + tickets + ", size " + tickets.size());
    }
}

Expected output:

Queue: [T-101, T-102, T-103]
Next up: T-101
Serving T-101
Serving T-102
Queue now: [T-103, T-104], size 2

A queue prints from head to tail. T-104 joined at the back, behind T-103.

PriorityQueue

A PriorityQueue does not follow FIFO. It always hands out the smallest element first, whatever order they were added in. "Smallest" means the highest priority.

For numbers, the smallest number comes first. For strings, the first in dictionary order comes first. You can pass a Comparator to change the rule, for example Comparator.reverseOrder() to get the largest first.

Think of a hospital emergency room. Patients are not seen in arrival order. The most serious case is treated first.

A PriorityQueue always hands out the most urgent item

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<Integer> urgency = new PriorityQueue<>();
        urgency.offer(3);
        urgency.offer(1);
        urgency.offer(5);
        urgency.offer(2);

        System.out.print("Smallest first: ");
        while (!urgency.isEmpty()) {
            System.out.print(urgency.poll() + " ");
        }
        System.out.println();

        Queue<Integer> scores = new PriorityQueue<>(Comparator.reverseOrder());
        scores.offer(72);
        scores.offer(95);
        scores.offer(88);

        System.out.print("Largest first: ");
        while (!scores.isEmpty()) {
            System.out.print(scores.poll() + " ");
        }
        System.out.println();
    }
}

Expected output:

Smallest first: 1 2 3 5
Largest first: 95 88 72

The numbers came out sorted, not in the order they were added.

Adding Elements

add()

add(e) adds e to the back. If the queue is full, it throws an IllegalStateException.

offer()

offer(e) adds e to the back. If the queue is full, it returns false instead of throwing.

Differences Between add() and offer()

The difference only shows up with a queue that has a fixed capacity, such as ArrayBlockingQueue from java.util.concurrent. Normal queues like LinkedList, ArrayDeque and PriorityQueue have no limit, so both methods always succeed.

Queue<String> small = new ArrayBlockingQueue<>(2);   // room for 2 only
small.offer("A");   // true
small.offer("B");   // true
small.offer("C");   // false, the queue is full
small.add("C");     // throws IllegalStateException: Queue full

Removing Elements

remove()

remove() removes and returns the item at the front. On an empty queue, it throws a NoSuchElementException.

poll()

poll() removes and returns the item at the front. On an empty queue, it returns null.

Differences Between remove() and poll()

On a queue with items, remove() and poll() do exactly the same thing. The difference only shows on an empty queue: remove() throws, while poll() returns null. Use poll() when an empty queue is a normal situation, like the end of a loop.

Accessing Elements

peek()

peek() returns the front item without removing it. On an empty queue, it returns null.

element()

element() also returns the front item without removing it. On an empty queue, it throws a NoSuchElementException.

Differences Between peek() and element()

Again, the difference only shows on an empty queue: element() throws, while peek() returns null. The example below shows all four methods on the same queue.

Exception methods vs null-returning methods on an empty queue

import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> jobs = new LinkedList<>();
        jobs.add("Print report");

        System.out.println("element(): " + jobs.element());
        System.out.println("remove(): " + jobs.remove());

        System.out.println("Now empty? " + jobs.isEmpty());
        System.out.println("peek() on empty: " + jobs.peek());
        System.out.println("poll() on empty: " + jobs.poll());

        try {
            jobs.remove();
        } catch (NoSuchElementException e) {
            System.out.println("remove() on empty: NoSuchElementException");
        }

        try {
            jobs.element();
        } catch (NoSuchElementException e) {
            System.out.println("element() on empty: NoSuchElementException");
        }
    }
}

Expected output:

element(): Print report
remove(): Print report
Now empty? true
peek() on empty: null
poll() on empty: null
remove() on empty: NoSuchElementException
element() on empty: NoSuchElementException

On a queue with items, each pair does the same thing. On an empty queue, peek and poll quietly return null, while element and remove throw.

Queue Applications

Ticket Booking Systems

Booking requests are served in the order they arrive, so nobody can jump ahead.

Print Queue

Documents sent to a shared printer wait in a queue and print one by one, oldest first.

Task Scheduling

An operating system keeps waiting programs in queues. A PriorityQueue lets urgent tasks run before others.

Message Processing

Chat apps and online shops put incoming messages or orders into a queue, so a worker can handle them one at a time, in order, even when many arrive at once.

A print queue serves documents in arrival order

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

public class Main {
    public static void main(String[] args) {
        Queue<String> printer = new ArrayDeque<>();

        printer.offer("Asha: report.pdf");
        printer.offer("Ravi: invoice.pdf");
        printer.offer("Meena: photo.png");
        System.out.println(printer.size() + " documents waiting");

        int page = 1;
        while (!printer.isEmpty()) {
            String job = printer.poll();
            System.out.println("Job " + page + " printing -> " + job);
            page++;
        }
        System.out.println("Printer is idle");
    }
}

Expected output:

3 documents waiting
Job 1 printing -> Asha: report.pdf
Job 2 printing -> Ravi: invoice.pdf
Job 3 printing -> Meena: photo.png
Printer is idle

The loop keeps calling poll() until the queue is empty. Asha sent her file first, so it printed first.

Queue vs Stack

Common mistakes

The following mistakes are common when working with stacks, queues and deques. Each row shows what you see, why it happens and how to fix it.

What to Remember

• A stack is LIFO: the last item added is the first removed.
• push adds to the top, pop removes the top, peek looks at it, search finds its distance from the top.
• Stacks power undo, the browser Back button, expression evaluation, the method call stack and bracket matching.
• A queue is FIFO: the first item added is the first removed.
• Queue is an interface. Use LinkedList or ArrayDeque for FIFO, and PriorityQueue for most-urgent-first.
• offer, poll and peek return a special value on failure. add, remove and element throw an exception.
• Queues serve tickets, print jobs, tasks and messages fairly, in order.

Next: Lambda Expressions