Data Structures: Stack

Shawn Koski
Sep 9, 2018 · 3 min read

For my second post in this series about different common programming data structures I will be talking about stacks.

What is a Stack

A Stack is a list-like data structure where elements can only be added or removed from the top of the stack. This is known as LIFO, or First In Last Out. The lack of searching or sorting makes most operations performed on a stack fast and efficient.

https://web.stanford.edu/class/archive/cs/cs106b/cs106b.1152/preview-stack-queue.shtml

Structure of a Stack

There are many real-world examples of stacks, my personal favorite way to picture them is as a giant stack of pancakes. I know that sounds weird, but her me out. When you’re placing pancakes on your plate you are going to put them one after another on top of each other. If you want to eat one of the pancakes in the middle of your stack you will first have to eat all the pancakes on top of the one you are trying to get to. This is like a stack data structure where if you want to get to an element in the middle of the stack you first have to remove all of the elements that are on top of it.

http://frugalfinders.com/ihop-national-pancake-day/

Operating on a Stack

There are three main functions you will be calling on a stack: push(), pop(), and peek(). Push() adds an element on to the top of the stack. Pop() removes the top element from the stack. Peek() lets you look at the top element on the stack without removing it. You can also have operations like length() to return the number of elements in your stack, or clear() to remove all elements from your stack.

Implementing a Stack in Javascript

class Stack {  
constructor() {
this.stack = [];
this.top = 0;
}
}

Our stack will be made out of an empty array and be initialized with a top variable of 0.

push(value) {    
this.stack[this.top++] = value;
}

For our push() function we set the top index of the array to our new value and then increment the top by one.

pop(value) {
return this.stack[--this.top];
}

Our pop() function will decrement top by one and return the value held in that array index. It leaves top as the decremented number so the next value that is pushed on to the stack will replace the current value.

peek() {
return this.stack[this.top - 1];
}

Peek() simply returns the top value of the stack without altering where the next value will be pushed.

length() {
return this.top;
}

Length() returns the current value of top which will be the length of the array.

clear() {
this.top = 0;
}

We can clear the stack by setting the top variable to 0.

I never know how to end my blog posts, but hopefully you learned something about stacks and have a little more understanding of how they work.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade