Stacks

Projected Time

About 1 hour

Prerequisites

Motivation

Stack is one of the most commonly used data structure along with its opposite relative, queue. Understanding how to implement stack helps you better understand and describe insertion, removal, and organization of data in a sequential order.

Applications of stack includes:

An “undo” mechanism in text editors; this operation is accomplished by keeping all text changes in a stack.
Undo/Redo stacks in Excel or Word.
Language processing :
- space for parameters and local variables is created internally using a stack.
- compiler’s syntax check for matching braces is implemented by using stack.
Back/Forward stacks on browsers. (by Siddhart Mahapatra)

Objectives

Explain what a stack data structure is and show how it is implemented.

Specific Things to Learn

Definition of stack
Show an example of stack data structure
JavaScript methods used to implement stack

Lesson

Lesson slides
Lesson video

Make sure to mention these things:

Explain what LIFO and FILO means.
Differentiate stack and queue.

Common Mistakes / Misconceptions

Array and stack seem similar at first glance. While stack can be implemented using array, the data in array can be accessed randomly, whereas stack must be accessed according to order.

Guided Practice

Explain and discuss as a class the steps involved in writing a stack structure, including:

Constructor
Push/Enqueue
Pop/Dequeue
Size control

Independent Practice

Try to write a Stack class with the steps discussed as methods:

const Stack = function() {}
  // Constructor

  // Push

  // Pop

  // Size management of stack

  // Output of stack
}

Challenge / Check for Understanding

Find a partner and show each other your own Stack class. Explain how the class you wrote works.

Next, ask each other the following questions:

What is difference between a stack and a simple array?
Which method uses LIFO?
Which methods are used in the stack data structure?
What is the runtime complexity of a stack?
How to make simple class as a stack class?
What is the meaning of ‘_’ (underscore) in the beginning of the variable name? Refer Playing with data structures in JavaScript — Stack
Give some day-to-day examples where stack is used.
What is difference between stack and queue?