stack.asc

Stack

The stack is a data structure that restricts the way you add and remove data. It only allows you to insert and retrieve in a Last-In-First-Out (LIFO) fashion.

An analogy is to think the stack is a rod and the data are discs. You can only take out the last one you put in.

Figure 1. Stack data structure is like a stack of disks: the last element in is the first element out

As you can see in the image above, If you insert the disks in the order 5, 4, 3, 2, 1. Then you can remove them on 1, 2, 3, 4, 5.

The stack inserts items to the end of the collection and also removes from the end. Both, an array and linked list would do it in constant time. However, since we don’t need the Array’s random access, a linked list makes more sense.

Stack’s constructor

link:../../../src/data-structures/stacks/stack.js[role=include]
  // ... methods goes here ...
}

As you can see in the stack constructor, we are using a linked list as the underlying data structure.

Let’s now develop the insert and remove operations in a stack.

Insertion

We can insert into a stack using the linked list’s addLast method.

Stack’s add

link:../../../src/data-structures/stacks/stack.js[role=include]

We are returning this, in case we want to chain multiple add commands.

Deletion

Deleting is straightforward as well.

Stack’s remove

link:../../../src/data-structures/stacks/stack.js[role=include]

This time we used the linked list’s removeLast method. That’s all we need for a stack implementation. Check out the full implementation here.

Implementation Usage

We can use our stack implementation as follows:

Stack usage example

link:../../../src/data-structures/stacks/stack.js[role=include]

As you can see if we add new items they will be the first to go out to honor LIFO.

Stack Complexity

Implementing the stack with an array and linked list would lead to the same time complexity:

Table 1. Time/Space complexity for the stack operations

Data Structure	Searching By		Inserting at the			Deleting from			Space
	Index/Key	Value	beginning	middle	end	beginning	middle	end
Stack	-	-	-	-	O(1)	-	-	O(1)	O(n)

It’s not very common to search for values on a stack (other Data Structures are better suited for this). Stacks especially useful for implementing Depth-First Search.