Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Implementing Stack Data Structure

Stacks are a Last-In, First-Out (LIFO) data structure that supports four main operations: Push, Pop, Peek (Top), and IsEmpty. In this lesson, we will first explain these operations in detail and then implement a stack using arrays and linked lists.

1. Stack Operations

1.1 Push Operation (Adding an Element to the Stack)

The Push operation adds an element to the top of the stack. If the stack is full (for a fixed-size array implementation), it results in a stack overflow error.

Steps for Push Operation:

1

.....

.....

.....

Like the course? Get enrolled and start learning!
S

sourcesmith

· 2 years ago

java.util.Stack is one of the old synchronized collection classes (it in fact extends Vector). These are rarely used.

In more modern Java you would use Collections.asLifoQeue on a Deque instance.to create a LIFO view of the queue.

M

matthew.carnahan1

· 2 years ago

If the only advantage to using linked lists for stacks, is it avoids stack overflows, then I don't see why we would use them over a simple list in python. I can't speak for the other programming languages, but it appears to me that the only reason we would have a stack overflow issue in the first set of code, is because we deliberately set a finite size for the stack. If we instead code it up, like it is in the lesson "Operations on Stack", it would allow you to use a simple list, that is dynamically sized, which would in turn avoid the stack overflow problem. A lot simpler code.

Does anyone disagree?

Show 2 replies
Andre Abtahi

Andre Abtahi

· 2 years ago

for the push method, we need to decide wether top points to this new item or if it needs to be swapped out to point to the new item by re routing pointers. Either way a validation check should occur otherwise top is confused type wise given that it's set to None.