Topic 4 – Stacks and Queues
Introduction
Two extremely common data structures are stacks and queues. A stack is just like what it is called, and operates on the principle Last In – First Out (commonly called LIFO). A queue looks a lot like a stack, but it is also exactly as the name describes and operates on the principle First In First Out (also called FIFO). Because so much of the operation of computers relies on stacks and queues – a good understanding of them is fundamental to all things computer – software and hardware. The full discussion on Stacks and Queues is available on wikibooks at https://en.wikibooks.org/wiki/Data_Structures/Stacks_and_Queues – this page summarizes much of the pertinent information from the wikibook.
Stack Operations
The stack has 2 basic operations – Push which is simply placing an item on the top of stack, and Pop – which is taking an item off the top of the stack. The concept of the stack is quite basic, if you want to play with it simply take a few coins and pile them up one by one, and remove them one by one from the top only. In a computer a stack can be implement using different ways; most commonly as an array or linked list. Everything you even wanted t know about stacks is at http://en.wikipedia.org/wiki/Stack_%28abstract_data_type%29
A sample implementation of a stack is here – https://jsfiddle.net/reaglin/0LLt6q55/ – this implementation is not complete (it is the responsibility of the student to complete the implementation for their assignments). Note that the incomplete code sections are noted with comments.
The algorithm for Push and Pop is described on Tutorials Point at https://www.tutorialspoint.com/data_structures_algorithms/stack_algorithm.htm
Queue Operations
The queue also has 2 basic operations Enqueue and Dequeue. Items are added to the end of the queue and removed from the front of the queue. Queues are very heavily used in computer programming and multiple implementations of the queue exist; linked list, doubly linked list, and deque. The basic structure and implementation of the queue is discussed at http://en.wikipedia.org/wiki/Queue_%28abstract_data_type%29
The algorithm for Queue is described in detail on Tutorials Point at https://www.tutorialspoint.com/data_structures_algorithms/dsa_queue.htm
Queuing Theory
Queuing theory is an entire field of mathematics that is used to predict the performance of queues. Queues are important in many engineering fields such as traffic engineering (think stop light), manufacturing (think assembly line), and even in cooking (think running kitchens where one item must complete before another begins). The wikipedia article on queuing is good and you should have a basic understanding of what queuing theory is and what it is used for. http://en.wikipedia.org/wiki/Queueing_theory
Resources
Some good resources for solving stack/queue problems are included here;
http://www.cs.cmu.edu/~adamchik/15-121/lectures/Stacks%20and%20Queues/Stacks%20and%20Queues.html – Carnegie Mellon description – with good examples.
Implementing a Stack in Python – https://realpython.com/how-to-implement-python-stack/
Examples of Stacks
Video – Abstract Data Types Creating a Stack Calculator
Link – https://www.youtube.com/watch?v=iclXbiG3OwA
Video – Implementation of Stacks and Queues
Stacks and queues are specific cases of a Linked List – and can be implemented as such. The implementation should be an efficient implementation. An implementation of a stack using a doubly linked list is here – https://jsfiddle.net/reaglin/0LLt6q55/
Link – https://www.youtube.com/watch?v=adoNkMNrlmU
Video – The Queue
It is important to understand how both the stack and queue work. If you are still a little confused (even on how to code the queue) here is a video to help you understand the structure and implementation of queues and their nodes.