Chapter 3. Constructing Stacks and Queues

In the previous chapter, we discussed several linear data types, which were list, linked list, and Doubly Linked List. In this chapter, we are going to discuss other linear data types, and those are stack, queue, and dequeue. The following are the topics we are going to discuss regarding these three data types:

• Building a Stack ADT and then fetching, pushing, and popping elements in this ADT
• Building a Queue ADT and then fetching, enqueuing, and dequeuing elements in this ADT 
• Building a Dequeue ADT and then fetching, enqueuing, and dequeuing elements in this ADT 

Technical requirements

To follow along with this chapter, as well as the source code, we require the following:

• A desktop PC or Notebook with Windows, Linux, or macOS
• GNU GCC v5.4.0 or above
• Code::Block IDE v17.12 (for Windows and Linux OS) or Code::Block IDE v13.12 (for macOS)
• You will find the code files on GitHub at https://github.com/PacktPublishing/CPP-Data-Structures-and-Algorithms

Building a Stack ADT

A stack data type is a list with some restriction in the list's operations. It can only perform the operations from one side, called the top. There are three basic operations in the Stack data type, and they are Top(), Push(), and Pop(). The Top() operation is used to fetch the value of the top position item only, the Push() operation will insert the new item in the top position, and the Pop() operation will remove the item in the top position. The stack is also known as a Last In First Out (LIFO) data type. To support these three operations, we will add one operation to the stack, which is IsEmpty(), to indicate whether the stack has elements or not. Please take a look at the following stack diagram:

As we can see in the preceding Stack diagram, we have storage containing a bunch of numbers. However, the only opened side is the top side so that we can only put and take the number from that side. We can also take a peek at the topmost number from the top side.

In real...

Building a Queue ADT

A queue data type is a list with some restrictions to the effect that the inserting operation (enqueue) can only be performed from one side (called the back) and the removing operation (dequeue) can only be performed from the other side (called the front). Similar to the Stack data type, we can develop the Queue data type by using the LinkedList data type. For the Enqueue() operation, we can adopt the InsertTail() operation in the LinkedList data type since we are going to insert an element from the back, which is similar to the Tail node in the LinkedList data type. Also, for the Dequeue() operation, we will use the implementation of the RemoveHead() operation in the LinkedList data type. The Queue data type is also known as the First In First Out (FIFO) data type since the element that is inserted from the back of Queue will travel to the front side before it can be removed. Let's take a look at the following diagram showing the queue:

As we can see in the preceding...

Building a Deque ADT

A dequeue, which stands for double-ended queue, is a queue that can insert and remove items from two sides: thefrontandback. To build this data structure, we are going to adopt theDoublyLinkedListdata type we already built in the previous chapter. Similar to the Queue data type, the Dequeue data type also has the Front() operation to fetch the front-most element's value. The Enqueue() operation in the Queue data type will become EnqueueBack() in the Dequeue data type, and the Dequeue() operation in the Queue data type will become DequeueFront() in the Dequeue data type. However, since we adopt the DoublyLinkedList data type instead of LinkedList, the implementation will be different. Besides those operations, we are also going to build the following operations:

• The Back() operation to fetch the back-most element's value.
• The EnqueueFront() operation to insert a new element into the front side. It will be similar to the implementation of the InsertHead() operation in the...

Summary

In this chapter, we have successfully built others linear data types: the Stack, Queue, and Deque data types. We can use the Stack data type if we need storage that only has one side to insert and remove an element, we can use the Queue data type if we need storage which has to insert and remove the element from a different side, and if we need storage that can be accessed from two sides, both the front and back sides, we can use the Deque data type. Fortunately, the time complexity for all of the operations in these three data types isO(1), and doesn't depend on the number of the elements in the data type. In the next chapter, we are going to discuss various sorting algorithms to arrange the elements inside the data types we have discussed so far.

QA section

• Specify three basic operations in the Stack data type!
• What does LIFO refer to and with which data type (covered in this chapter) is it associated?
• Give an example of stack implementation in real life
• What is stack implementation in a programming language?
• What is deque also known as?
• What is the difference between queue and deque?
• Why is the complexity of the data types O(1)? Can you guess why the number of elements in the data type doesn't affect the complexity?

Further reading

For reference, you can refer to the following links:

• http://www.geeksforgeeks.org/stack-data-structure/
• http://www.geeksforgeeks.org/queue-data-structure/
• http://www.geeksforgeeks.org/deque-set-1-introduction-applications/
• https://visualgo.net/en/list?slide=4
• https://visualgo.net/en/list?slide=5
• https://visualgo.net/en/list?slide=7