What is a Stack
- A stack is a data structure that consists of Nodes. Each Node references the next Node in the stack, but does not reference its previous.
-
First In Last Out
-
Last In First Out
-
Pushing a Node onto a stack will always be an O(1) operation. This is because it takes the same amount of time no matter how many Nodes (n) you have in the stack.
-
Popping a Node off a stack is the action of removing a Node from the top. When conducting a pop, the top Node will be re-assigned to the Node that lives below and the top Node is returned to the user. When conducting a peek, you will only be inspecting the top Node of the stack.
What is a Queue
- Queues follow these concepts:
-
First In First Out
-
Last In Last Out
Common terminology for a queue is
-
Enqueue - Nodes or items that are added to the queue.
-
Dequeue - Nodes or items that are removed from the queue. If called when the queue is empty an exception will be raised.
-
Front - This is the front/first Node of the queue.
-
Rear - This is the rear/last Node of the queue.
-
Peek - When you peek you will view the value of the front Node in the queue. If called when the queue is empty an exception will be raised.
-
IsEmpty - returns true when queue is empty otherwise returns false.
