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 that 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 in 1, 2, 3, 4, 5.

The stack inserts items to the end of the collection and also removes it from the rear. 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 use 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.

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 are especially useful for implementing Depth-First Search.

Practice Questions

Validate Parentheses / Braces / Brackets

ST-1) Given a string with three types of brackets: (), {}, and []. Validate they are correctly closed and opened.

Examples:

isParenthesesValid('(){}[]'); // true
isParenthesesValid('('); // false (closing parentheses is missing)
isParenthesesValid('([{}])'); // true
isParenthesesValid('[{]}'); // false (brakets are not closed in the right order)
isParenthesesValid('([{)}]'); // false (closing is out of order)

Common in interviews at: Amazon, Bloomberg, Facebook, Citadel

link:../../interview-questions/valid-parentheses.js[role=include]
  // write you code here
}

Solution: [stack-q-valid-parentheses]

Daily Temperaturs

ST-2) Given an array of integers from 30 to 100 (daily temperatures), return another array that, for each day in the input, tells you how many days you would have to wait until warmer weather. If no warmer climate is possible, then return 0 for that element.

Examples:

dailyTemperatures([30, 28, 50, 40, 30]); // [2 (to 50), 1 (to 28), 0, 0, 0]
dailyTemperatures([73, 69, 72, 76, 73, 100]); // [3, 1, 1, 0, 1, 100]

Common in interviews at: Amazon, Adobe, Cisco

link:../../interview-questions/daily-temperatures.js[role=include]
  // write you code here
}

Solution: [stack-q-daily-temperatures]