What are Stacks and Queues?

IB Standards Covered

5.1.6 Describe the characteristics and applications of a stack.

Stacks and Queues are two related data structures. Just like any other data structures, they were created with specific purposes in mind. Queues model physical queues so they can be used in networking when requests need to be waited on and each is served in the order that they came in. Stacks, on the other hand, would be useful when creating a back button or “undo” button, as they help you access the latest information. The following video goes over the conceptual explanation of both and reviews the essential methods that can be found in each.

Queues Notes

Use Last In First Out (LIFO) order. Items are retrieved in the order in which they were inserted.
Enqueue, dequeue, peek, and isEmpty are its essential methods.
It can be created with linked nodes, 2 stacks, arrays, ArrayList, and many other data structures.
It can be circular or linear.

Applications:
Model physical queues, such as people waiting in line.
Call centers use queues to let callers talk to customer service.
Printing documents can be queued in order in which they were sent.
In networking, requests are served in the order in which they queue.
Also in networking, data packets are served in the order in which they queue.
CPU scheduling. Processes are allowed a slice of processing time depending on their queue.

Stacks – Notes

Use First In First Out (FIFO) order. The latest item to be inserted is the one accessed.
Push, pop, peek, and isEmpty are its essential methods.
It can be created with linked nodes, arrays, ArrayList, and many other data structures.

Applications:
The back button of a browser.
The undo button in any application.
Processors use stacks when allocating space to new processes. Recursion is possible because of stacks.
Backtracking in searching algorithms.