Class 10
Stacks And Queues
What is a Stack?
- A stack is a data structure that consists of nodes.
- Each node references the next node in satck but not reference to it’s previous.
Terms:
push
the method used to put nodes or items to the stack
pop
the method used to remove nodes or items from the stack
- you can’t pop an empty stack
top
it’s the top of the stack
peek
the method used to view the value of the top in the stack
- you can’t pop an empty stack
is Empty
returns true when stack is empty otherwise return false
For all four methods the Big O notation is O(1)
stack concepts
FILO * first in last out *
means that the first item added in the stack will be the last item to be popped out of the stack.
LIFO last in first out
means that the last item added in the stack will be the first item to be popped out the stack.
TERMS OF QUEUE:
enqueue
- are items that are added to the queue.
dequeue
- are items that are removed from the queue.
front
- is the front or first item in the queue.
rear
- is the rear or last item in the queue.
peek
the method used to view the value of the top in the queue.
- you can’t pop an empty queue.
isEmpty
returns true when queue is empty otherwise return false.
For all four methods the Big O notation is O(1)
FIFO first in first out
- means that the first item in the queue will be the first item out of the queue.
LILO last in last out
- means that the last item in the queue will be the last item out of the queue.