Skip to content

Latest commit

 

History

History
148 lines (103 loc) · 4.72 KB

File metadata and controls

148 lines (103 loc) · 4.72 KB

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.

image
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
}
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
}