Skip to content

Class 10 Stacks and Queues

Jump to bottom
Erin Trainor edited this page Mar 27, 2019 · 1 revision

Resource

Stacks and Queues

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 it’s previous. LIKE A LINKED LIST

Common Terminology

  • Push - Nodes or items that are put into the stack are pushed

    • Big O = O(1) - Pushing a node onto a stack will be an O(1) operation. This is because it takes the same amount of time, no matter how many nodes you have in the stack.

  • Pop - Nodes or items that are removed from the stack are popped

    • Big O = O(1) - Popping a node off a stack 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.

  • Top - This is the top of the stack.

  • Peek - When you Peek you will view the Top node in the stack. If the stack is empty, and you don’t Peek, you will receive a NullReferenceException if you attempt to Pop.

    • Big O = O(1) - When conducting a Peek, you will only be viewing the Top node of the stack. Traditionally, you always want to Peek before conducting a Pop. This will ensure that you do not receive a NullExceptionError on your Pop action.

FILO

First In Last Out

LIFO

Last in First Out

Queues

  • Enqueue - Nodes or items that are added to the queue.

    • Big O = O(1) - When you add an item to a queue, you use the Enqueue action. This is done with an O(1) operation in time because it does not matter how many other items live in the queue, it takes the same amount of time to perform the operation.

  • Dequeue - Nodes or items that are removed from the queue.

    • Big O = O(1) - When you remove an item from a queue, you use the Dequeue action. This is done with an O(1) operation in time because it doesn’t matter how many other items are in the queue, you are still always removing the Front node of the queue.

  • 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 Top node in the stack. If the stack is empty, and you don’t Peek, you will receive a NullReferenceException.

    • Big O = O(1) - When conducting a Peek, you will only be viewing the Front node of the stack. Traditionally, you always want to Peek before conducting a Dequeue. This will ensure that you do not receive a NullExceptionError on your Dequeue action.
Clone this wiki locally