DEV Community

miku86
miku86

Posted on

JavaScript Data Structures: Stack: Intro

Intro

After completing the series about the Doubly Linked List, we start with the Stack.


What is a Stack?

  • uses the "Last In, First Out"-Principle
  • Examples: a stack of cards, a pile of dishes, a browser history
  • there are multiple ways to implement a Stack: Array, Singly Linked List, Doubly Linked List

Stack


Big O of Stack

  • Access: O(N)
  • Search: O(N)
  • Insert: O(1)
  • Delete: O(1)

Example

We will use a Singly Linked List to build our Stack.

A <== B <== C (last)

  • C is the last node we pushed (= added) on top of the Stack
  • C has a pointer (next) to the next node (B)
  • if we pop (= remove) C, the next node on top of the Stack should be B

Setup

We need the following parts to build our Stack:

  • a Node with a value and a pointer to the next item in the Stack
  • a Stack with a length and a pointer to the last item
// a Node has a value (`value`) and a pointer to the next node (`next`)
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

// a Stack has a length and a last item (`last`)
class Stack {
  constructor() {
    this.length = 0;
    this.last = null;
  }
}
Enter fullscreen mode Exit fullscreen mode

Thoughts

We set up our Stack. Now we need at least two methods within the Stack:

  • a method that pushes a new node on top of the Stack: push
  • a method that pops off the last node from the top of the Stack: pop

Next Part

We will implement our first method for the Stack.

If you want to get notified, subscribe!


Questions

  • Can you think of some pros or cons of using the Singly Linked List instead of an Array or a Doubly Linked List?

Top comments (0)