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.
Two notes before the code
On the fixed-size version. The array implementation below uses a fixed capacity, which is why it can
overflow. In Python, Java and JavaScript the built-in list, ArrayList and array all grow on their own, so a
stack built on one of those never overflows for capacity reasons and append and
.....
.....
.....
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?
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.
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.
Reading Progress
0%