Topic - 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.

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 

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.

Examples of Stacks 

Creating a Stack Calculator

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/ 

Implementation of a 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.