Stack
Info
The stack is an ordered container of data that enforces a LIFO (last in, first out) policy on adds and removes.
Think of it like a stack of DVDs. You put in a DVD, and another on top. Then the last DVD you put in will be the first one out, and the first DVD you put in will be the last one out.
Specification
Definition
For a stack holding data type T:
init:(no input) -> Stack- Pre:
true - Post: returned value is a new, empty stack
- Pre:
isEmpty:(no input) -> bool- Pre:
true - Post: return value is the same as
length == 0
- Pre:
push:(stack element) -> void- Pre:
true - Post: new stack contains
- Pre:
pop:(no input) -> void- Pre: is not empty
- Post: new stack contains
peek:(no input) -> T- Pre: is not empty
- Post:
true
nuke:(no input) -> void- Pre:
true - Post: all items of the stack have been deleted
- Pre:
Implementation
General Implementation with a Linked List
See Linked List.
init:- Initialize root node to
nullptr
- Initialize root node to
push:- Create a new node and set its value
- Set the next pointer of this node to the current node
- Set the "current" node to the new node
isEmpty:- Check if root node is
nullptr
- Check if root node is
pop:- Store the address of the node after the top node
- Delete the top node
- Set the new top node as the previously stored node in (1)
peek- Return the top node
nuke- Nuke the linked list by deleting each node one by one (could be done by calling pop over and over again)
Runtimes (see Big O):
init:push:isEmpty:pop:peek:nuke:
General Implementation with a Dynamic Array
See Computer Science/Programming/Arrays
init:- Initialize the array
push:- Push to the array like usual
isEmpty:- Check if the length of the array is 0
pop:- Remove the last item of the array
peek- Return the last element of the array
nuke- Delete each element of the array if necessary, delete the array if necessary
Runtimes:
init:push:(amortized) isEmpty:pop:peek:nuke: