Data Structures in JavaScript: Visualizations & Exercises/

...

/

Stacks

Stacks

Stack is a Last In, First Out data structure useful is solving many problems in computer science.

We'll cover the following...

Introduction

A stack is a list like data structure which allows three basic operations:

  1. Insert into the stack. This is known as Push.
  2. Extract the most recently added. This is called Pop.
  3. Look at the most recently added element without removing (popping) it. This is called Peek.

Using the above terminology, we can say that we push elements into the stack and we pop elements from the stack. Stack is known as a Last-In First-Out (LIFO) data structure.

To support operations in the stack, we always keep track of the topmost element in the stack. Here's how tracking the top element in the stack helps us implement the above operations.

  1. When we push an element, we update the top to start pointing to the newly added element. 
  2. When we pop an element, we update the top to point to the next most-recently-added element in the stack. 
  3. When we peek, we just return the data pointed by the top.

Here's a quick animation where we push and pop elements in the stack.

Defining the stack

The  block of code below shows how a stack would be defined in JavaScript:

Press + to interact
function Stack() {
  this._top = -1;
  this._values = [];
}

The Stack function would contain 2 parts:

  • The index of the most recent element tracked by _top. It is initialized by -1 to indicate that stack contains no elements.
  • Array of values inserted into the stack tracked by _values. It is initialized by an empty array.

Pushing

...