# Linear Data Structures Course: [Java](https://www.devtutorials.ai/learn/java) · Section: Collections Framework Source: https://www.devtutorials.ai/learn/java/collections-framework/linear-data-structures > 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**. ```java runnable title="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 plates = new Stack<>(); plates.push("Plate 1"); plates.push("Plate 2"); plates.push("Plate 3"); Queue 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: ```text 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. ```text push A push B push C pop → C pop → B ┌───┐ ┌───┐ │ C │ ← top ┌───┐ │ B │ │ B │ ┌───┐ │ A │ │ A │ │ A │ │ B │ ┌───┐ └───┘ └───┘ └───┘ │ A │ │ A │ └───┘ └───┘ ``` ### Creating a Stack ```text import java.util.Stack; Stack history = new Stack<>(); Stack 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. ```java runnable title="Every Stack method on one pile of books" import java.util.Stack; public class Main { public static void main(String[] args) { Stack 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: ```text 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. | Method | What it does | On an empty stack | |---|---|---| | `push(x)` | Adds `x` to the top | Works | | `pop()` | Removes and returns the top | Throws `EmptyStackException` | | `peek()` | Returns the top, keeps it | Throws `EmptyStackException` | | `search(x)` | Distance from the top (top = 1), or `-1` | Returns `-1` | | `isEmpty()` | `true` if nothing is in it | Returns `true` | | `size()` | Number of items | Returns `0` | Calling `pop()` or `peek()` on an empty stack stops the program with an `EmptyStackException`. Always check `isEmpty()` first, as the `while (!plates.isEmpty())` loop at the top of this lesson does. ### 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. ```java runnable title="Undo and browser Back are both stacks" import java.util.Stack; public class Main { public static void main(String[] args) { Stack 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 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: ```text 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. ```java runnable title="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 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: ```text 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. ```java runnable title="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: ```text 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. ```java runnable title="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 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: ```text (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. ```text Deque 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. ```text 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. | Action | Throws an exception | Returns a special value | |---|---|---| | Add to the back | `add(e)` | `offer(e)` returns `false` | | Remove from the front | `remove()` | `poll()` returns `null` | | Look at the front | `element()` | `peek()` returns `null` | Common classes that implement `Queue`: | Class | Order | Notes | |---|---|---| | `LinkedList` | FIFO | Also a `List` | | `ArrayDeque` | FIFO | Usually the fastest choice | | `PriorityQueue` | Smallest (highest priority) first | Not FIFO | ### LinkedList Queue `LinkedList` implements both `List` and `Queue`. When you store it in a `Queue` variable, you only see the queue methods. ```java runnable title="A LinkedList used as a queue" import java.util.LinkedList; import java.util.Queue; public class Main { public static void main(String[] args) { Queue 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: ```text 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. ```java runnable title="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 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 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: ```text Smallest first: 1 2 3 5 Largest first: 95 88 72 ``` The numbers came out sorted, not in the order they were added. Printing a whole `PriorityQueue`, or looping over it with for-each, does **not** show elements in priority order. Only `poll()` and `peek()` respect the priority. That is why the example above removes items one by one with `poll()`. ### 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. ```text Queue 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 ``` | | `add(e)` | `offer(e)` | |---|---|---| | When it works | Adds `e`, returns `true` | Adds `e`, returns `true` | | When the queue is full | Throws `IllegalStateException` | Returns `false` | | Prefer it when | Being full is a bug | Being full is a normal situation | ### 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. ```java runnable title="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 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: ```text 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. | | `remove()` | `poll()` | `element()` | `peek()` | |---|---|---|---|---| | Removes the front? | Yes | Yes | No | No | | Returns the front? | Yes | Yes | Yes | Yes | | On an empty queue | Throws `NoSuchElementException` | Returns `null` | Throws `NoSuchElementException` | Returns `null` | **Easy Way to Remember:** the friendly trio **offer, poll, peek** never throws. The strict trio **add, remove, element** throws when something is wrong. Use the friendly trio in normal loops. ### 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. ```java runnable title="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 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: ```text 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 | | Stack | Queue | |---|---|---| | Principle | LIFO: last in, first out | FIFO: first in, first out | | Add at | The top | The back (tail) | | Remove from | The top | The front (head) | | Add method | `push` | `offer` / `add` | | Remove method | `pop` | `poll` / `remove` | | Look method | `peek` | `peek` / `element` | | Real-life picture | A pile of plates | A line at a counter | | Typical uses | Undo, back button, brackets, method calls | Tickets, printers, tasks, messages | | Recommended class | `ArrayDeque` (or `Stack` for learning) | `ArrayDeque` or `LinkedList` | ## 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. | Symptom | Cause | Fix | |---|---|---| | `EmptyStackException` | `pop` or `peek` on an empty `Stack` | Check `isEmpty()` first | | `NoSuchElementException` | `remove` or `element` on an empty queue | Use `poll` or `peek` | | Items come out backwards | A stack was used where order should be kept | Use a queue | | A `PriorityQueue` prints unsorted | Printing does not follow priority | Remove items with `poll()` | | Wrong answer for `8 2 -` | The operands were popped in the wrong order | The first pop is the right operand | | `search` result looks wrong | It counts from the top, starting at 1 | Read it as distance from the top | ## 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