Stacks and Queues

From storage to behavior

In Arrays and Linked Lists, you focused on how data is physically arranged and how that affects access, insertion, and deletion.

Now we move one layer up: abstract data types.

A stack and a queue are not mainly about where data lives. They are about the rule for who gets removed next.

• Stack: most recently added item leaves first
• Queue: earliest added item leaves first

These simple rules show up everywhere: undo buttons, browser history, task scheduling, print jobs, request handling, and many easy/medium interview problems.

Last In, First Out

A stack follows LIFO: Last In, First Out.

Think of a stack of plates:

Top
 ↓
[ C ]  ← removed first
[ B ]
[ A ]  ← added first

The only end we care about is the top.

Core operations:

• push(item) — add to the top
• pop() — remove from the top
• peek() — look at the top without removing
• isEmpty() — check whether the stack has items

The important constraint is not that the data is vertical. It is that the most recent item has priority.

Arrays make simple stacks

JavaScript arrays already give us efficient stack-like operations at the end of the array.

• push adds to the end
• pop removes from the end

Because the end of an array does not require shifting all other elements, these operations are typically O(1).

```javascript
const stack = [];

stack.push("open file");
stack.push("edit line");
stack.push("save file");

console.log("Current stack:", stack);
console.log("Peek:", stack[stack.length - 1]);

console.log("Undo:", stack.pop());
console.log("Undo:", stack.pop());

console.log("Remaining stack:", stack);
console.log("Is empty?", stack.length === 0);
```

You run these operations on an empty stack:

push(10)
push(20)
push(30)
pop()

Which value is returned by pop()?

First In, First Out

A queue follows FIFO: First In, First Out.

Think of people waiting in line:

Front                         Back
  ↓                            ↓
[ A ] → [ B ] → [ C ] → [ D ]
remove                      add here

Core operations:

• enqueue(item) — add to the back
• dequeue() — remove from the front
• front() or peek() — inspect the next item
• isEmpty() — check whether the queue has items

Stacks prioritize recency. Queues prioritize arrival order.

The obvious version

A queue can also be modeled with a JavaScript array.

A beginner-friendly version uses:

• push to enqueue at the back
• shift to dequeue from the front

This is easy to read and fine for small inputs. But there is a performance catch: shift() may require moving every remaining item one position left, making it O(n).

```javascript
const queue = [];

queue.push("Alice");
queue.push("Ben");
queue.push("Chloe");

console.log("Queue:", queue);
console.log("Serving:", queue.shift());
console.log("Serving:", queue.shift());
console.log("Remaining:", queue);
```

In a queue, the operation that adds a new item to the back is called _____.

Avoid shifting work

For larger inputs, repeatedly calling shift() can become expensive.

Instead, keep a head index that points to the current front of the queue. Dequeueing becomes moving the pointer forward rather than physically moving all elements.

This keeps enqueue and dequeue operations effectively O(1).

```javascript
class Queue {
  constructor() {
    this.items = [];
    this.head = 0;
  }

  enqueue(value) {
    this.items.push(value);
  }

  dequeue() {
    if (this.isEmpty()) return undefined;
    const value = this.items[this.head];
    this.head += 1;
    return value;
  }

  front() {
    return this.isEmpty() ? undefined : this.items[this.head];
  }

  isEmpty() {
    return this.head >= this.items.length;
  }

  size() {
    return this.items.length - this.head;
  }
}

const tasks = new Queue();
tasks.enqueue("download report");
tasks.enqueue("validate rows");
tasks.enqueue("send summary");

console.log("Next:", tasks.front());
console.log("Run:", tasks.dequeue());
console.log("Run:", tasks.dequeue());
console.log("Remaining size:", tasks.size());
console.log("Next:", tasks.front());
```

A stack is a good fit when you need to process items in the same order they arrived.

Ask: who goes next?

When deciding between a stack and a queue, focus on the removal rule.

Need Use Undo the most recent action Stack Track browser back history Stack Serve requests in arrival order Queue Manage print jobs Queue Explore most recent choice first Stack

Key takeaways

• A stack uses LIFO: last added, first removed.
• A queue uses FIFO: first added, first removed.
• JavaScript arrays naturally support stacks with push and pop.
• Queues need more care if many front removals are expected.

Next, we will build on these ideas when we look at Trees, where ordering and traversal become more structured.