Objectives

By the end of this chapter you should be able to:

• Describe what a stack is and implement essential stack operations
• Understand common use cases for stacks

Stack

You can think of a stack just like a stack of things in real life. For example, if you had a stack of papers on your desk, the first piece of paper you would pull off of the stack would be the one on top of the stack. If you were to put more papers on the stack, the last one you put on the stack (the one of top) would also be the first one that you take off of a stack.

The stack data structure works in the same way. It is a Last In First Out (LIFO) data structure. So the last thing you placed on the stack is the first thing that you can take off of the stack.

Commonly, a stack only has a few operations that can be preformed:

• pop - Take something off of the top of the stack. In the example below, 1 will be removed from the stack because it is on top (the last element added).

• push - Add something to the top of the stack. In the example below, 55 is being pushed onto the stack. A stack is always last in, first out, so the 55 goes on top of the stack.

• size or length - How many elements are in the stack

Real World Examples of Stacks

Although the stack is a pretty simple data structure, it is used quite frequently in programming. Let's examine some real world use cases for stacks and think about what kinds of problems we can solve with them.

Call Stack - in JavaScript (and in computer science in general), the call stack is used to keep track of functions that are being executed or have been executed.

Backtracking - for certain kinds of algorithms (especially ones we will examine in a later section on Binary Search Trees), remembering information in a certain order can easily be achieved using a stack. You can read more about backtracking here

The back button in the browser - think about how this might work! Every time that you view a page, the previous URL get's added to a stack. If you click the back button that URL will be visited and popped off the stack. Try to visualize or diagram this example, it will help solidify your understanding quite a bit. Stacks are also very helpful for implementing an undo feature.

Calculations - calculators and specific kinds of notations (like this one), can be implemented using stacks to keep track of numbers and operations. When the = button is pressed (or other buttons to calculate values), certain values are popped off the stack.

Naive Stack Implementation

Here is a very simple implementation of a stack in JavaScript:

function Stack() {
    this.stack = [];
}

Stack.prototype.push = function(val) {
    this.stack.push(val);
}

Stack.prototype.pop = function() {
    return this.stack.pop();
}

Stack.prototype.length = function() {
    return this.stack.length;
}

Although this implementation is very simple and it enforces the LIFO property of a stack, it is not the most efficient. As we learned earlier, the push operation on an array is O(n). A better implementation would be to use a doubly linked list to implement the stack. That way, pushing and popping operations would always be constant time, O(1). You could also use a singly linked list, since its unshift and shift operations would mimic the push and pop of a stack.