Ask LSBot
Back to Open Book Shelf

Stacks

A stack is an abstract data type that follows the "Last In, First Out" (LIFO) principle. Using LIFO means that the last item added to the stack is the first item to be removed.

Imagine a stack of plates. When you place a new plate on top of this stack, it covers all the other plates that were there before. If you need to remove a plate, you'll take off the one you placed last first because it's on top. You won't reach down to grab one from the bottom until all those placed above it have been removed. This "top-down" approach is the essence of LIFO.

Key Operations

There are three primary operations you can perform on a stack data structure:

Push

  • In stack terminology, pushing is the act of adding an element to the top of the stack. Just as you would place a clean plate on top of the others, pushing in a data context adds a data element (like a number, character, or object) to the stack.
  • This operation is accomplished in constant time, O(1), because it doesn't require shifting or moving other elements around; you simply place the new item on top.

Pop

  • Similar to removing the top plate from a stack when you need to use it, popping in a stack data structure involves removing the top element.
  • This is also a constant time operation, O(1), as it directly accesses the top element without needing to rearrange or look through the rest of the stack.

Peek

  • In a plate stack, you might glance at the top plate to see if it's clean or the one you want. In a stack data structure, "peeking" lets you see the value of the top element without removing it from the stack. This can be useful for checking the value before deciding to remove it or perform other operations.

Practical Applications of Stacks

Function Call Management

In programming, whenever a function (a block of code designed to perform a specific task) is called, information about where the function was called from and its internal variables are stored in a stack. Each subsequent function call adds another layer to this stack. When a function completes its task, its information is removed from the stack, and the program returns to the point where this function was called. This system helps manage where the program should continue running after a function has been executed.

Undo Mechanisms in Applications

Think about using a word processor or a graphics design program. Each action you take (like typing a letter or drawing a shape) can potentially be reversed by using the "undo" feature. Stacks make this possible by keeping a record of each action in the reverse order in which they were performed. When you hit "undo," the most recent action is "popped" off the stack and reversed.

Web Browser Navigation

The back button in a web browser allows you to revisit the previous web page. This is implemented using a stack. Each time you visit a new page, the URL (web address) is pushed onto a stack. When you press the back button, the most recent URL is popped off, taking you back to the last page you visited.

Depth-First Search (DFS) in Graphs

We will cover Graphs in a later lesson. Without going into what graphs are right now, just know that they are a data structure and we can traverse this data structure using something called depth-first search algorithm. This algorithm uses a stack to perform the traversal.

In the next assignment, we'll see how we can implement a stack using a linked list.

Implement a Stack with a Singly Linked List

In the following exercises, your goal is to implement a stack using a singly linked list. We'll provide you with a template to help you get started. You might recognize the class ListNode from the Linked List assignment. We encourage you to implement the stack independently but feel free to reference our walkthrough if you need guidance.

Problem Description

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

class Stack {
  constructor() {
    this.top = null;
  }
  peek() {
    // Returns the value of the top most element without removing it.

    // If the stack is empty, it returns `null`.
  }

  push(value) {
    // Adds an item to the stack
  }

  pop() {
    // Removes the item from the stack and returns it

    // If the stack is empty, it returns `null`.
  }
}

const myStack = new Stack();
myStack.push(1);
console.log('Top element:', myStack.peek());  // logs 'Top element: 1'
myStack.push(2);
console.log('Top element:', myStack.peek());  // logs 'Top element: 2'
myStack.push(3);
console.log('Top element:', myStack.peek());  // logs 'Top element: 3'
myStack.pop();
console.log('Top element after pop:', myStack.peek());  // logs 'Top element after pop: 2'
myStack.pop();
console.log('Top element after pop:', myStack.peek());  // logs 'Top element after pop: 1'
myStack.pop();
console.log('Peek on empty stack:', myStack.peek());    // logs 'Peek on empty stack: null'

Exercises

  1. Implement peek and write some test code to ensure that it's working.

    View Our Solution

    The peek method returns the topmost node's value or null if the stack is empty.

    // some code above

peek() {
  return this.top ? this.top.val : null;
}

    In our solution, we use a ternary operator. If the top element exists, this.top.val will be returned; otherwise, null. We could rewrite it with an if statement as well:

    // some code above

peek() {
  if (this.top) {
    return this.top.val;
  }
  return null;
}

  2. Implement push and write some test code to ensure that it's working.

    View Our Solution

    The push method is a bit more involved.

    • First, given a value, we want to create a ListNode with that value, referenced by newNode.
    • Next, we must consider two scenarios: an empty stack and a non-empty stack.
      • If the stack has no elements, directly assign newNode as the top node.
      • If the stack is not empty:
        • Set the next property of newNode to point to the current top node.
        • Update the top pointer to reference newNode.

    Assuming we have created a stack, let's see how adding the first three elements would look visually:

    myStack.push(1)

    myStack.push(2)

    myStack.push(3)

    // some code above

push(value) {
  const newNode = new ListNode(value);
  if (!this.top) {
    this.top = newNode;
  } else {
      newNode.next = this.top;
      this.top = newNode;
  }
}

    We can simplify this implementation significantly. Remember that our ListNode class allows us to pass in a next value when we create a new node. As a result, we can assign the current top to our new node's next value, handling both scenarios with one action:

    // some code above

push(value) {
  this.top = new ListNode(value, this.top);
}

    If the stack is empty, this.top is null, which is the default value that ListNode uses when we don't pass in a next argument. If the stack is not empty, this.top references the node that should be referenced by newNode's next pointer.

  3. Implement pop and write some test code to ensure that it's working.

    View Our Solution

    The pop method returns null if the stack is empty, otherwise it returns the topmost node. This means that we need to keep a reference to this top node to return its value later.

    Let's first see how popping elements from the stack would look visually. We'll continue where we left off in the previous image, with the stack containing three elements.

    myStack.pop()

    myStack.pop()

    myStack.pop()

    myStack.pop()

    // some code above

pop() {
  if (!this.top) return null;

  const poppedNode = this.top;

  this.top = this.top.next;

  return poppedNode.val;
}

    Finally, here's all of our code together:

    class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

class Stack {
  constructor() {
    this.top = null;
  }

  peek() {
    return this.top ? this.top.val : null;
  }

  push(value) {
    this.top = new ListNode(value, this.top);
  }

  pop() {
    if (!this.top) return null;

    const poppedNode = this.top;

    this.top = this.top.next;

    return poppedNode.val;
  }
}

const myStack = new Stack();
myStack.push(1);
console.log('Top element:', myStack.peek());  // logs 'Top element: 1'
myStack.push(2);
console.log('Top element:', myStack.peek());  // logs 'Top element: 2'
myStack.push(3);
console.log('Top element:', myStack.peek());  // logs 'Top element: 3'
myStack.pop();
console.log('Top element after pop:', myStack.peek());  // logs 'Top element after pop: 2'
myStack.pop();
console.log('Top element after pop:', myStack.peek());  // logs 'Top element after pop: 1'
myStack.pop();
console.log('Peek on empty stack:', myStack.peek());    // logs 'Peek on empty stack: null'
Previous:  Intro to Stacks and Queues

Ask LSBot about: Stacks

Your questions are private and won't be used to evaluate your performance.

×
This conversation with LSBot is temporary. Sign up for free to save your conversations with LSBot.

Hi! I'm LSBot. I'm here to help you understand this chapter content with fast, focused answers.

Ask me about concepts, examples, or anything you'd like clarified from this chapter. I can explain complex topics, provide examples, or help connect ideas.

Want to know more? Refer to the LSBot User Guide.

Stacks - Exercise

Your questions are private and won't be used to evaluate your performance.

×
This conversation with LSBot is temporary. Sign up for free to save your conversations with LSBot.

Hi! I'm LSBot. I'm here to help you think through this exercise by providing hints and guidance, without giving away the solution.

You can ask me about your approach, request clarification on the problem, or seek help when you feel stuck.

Want to know more? Refer to the LSBot User Guide.