Stack¶
A stack is a data structure where items are added and removed in last-in-first-out order ( sometimes called LIFO lists or LIFOs )
Adding an object to a stack is called pushing the object onto the stack, and removing an object from the stack is called popping the object off of the stack.
Linked-List Stacks ¶
Implementing a stack is easy using a linked list, with a linked list, pushing and popping items both have $\(\text{O}(1)\)$ run times.
- the
Pushmethod simply adds a new cell to the top of the list - the
Popmethod removes the top cell from the list.
Array Stacks¶
Allocate space for an array enough to hold the data expected to put in the stack. Then use a variable to keep track of the next empty position in the stack.\ \ \
With an array-based stack, Push and Pop have $\(\text{O}(1)\)$ run times.
Info
Setting and getting a value from an array generally is faster than creating a new cell in a linked list, so this method may be slightly faster than using a linked list.
An array-based stack requires extra space to hold new items, resizing the array will take extra time. If the array holds N items when you need to resize it, it will take $\(\text{O}(n)\)$ steps to copy those items into the newly resized array.
Double Stacks ¶
In case an algorithm needs to use two stacks whose combined size is bounded by some amount. Then can store both stacks in a single array, with one at each end and both growing toward the middle,
