Stacks

.
Stack is a linear data structure that follows a particular order in which operations are performed: LIFO (Last in First Out) or FILO (First in Last Out). What this means is that the element that is added first to the list will be deleted the last. The main operations performed on a stack are:

• Push: Adds an item to the stack.
• Pop: Deletes an item from the stack.
  Fig: Push and Pop

Real-life example of stack includes a stack of plates where the bottommost plate (which was added to stack first) is used at the end.

Implementation

Stack can be implemented in two different ways:

• Arrays
• Linked List

Array

---

In this format, an array is used to maintain the order of stack. The main components of such a stack are:

• topmost position, top
• Length of the array, MAX
• array itself, stack
  Push: Following is the algorithm to implement stack (initialize top as -1):

begin procedure push: stack, data

    if stack is full //if top equals to MAX - 1
       return null
    endif

    top ← top + 1
    stack[top] ← data

end procedure

Pop:

begin procedure pop: stack

   if stack is empty //if top equals to -1
      return null
   endif

   data ← stack[top]
   top ← top - 1
   return data

end procedure

Example:
The major problem of using an array is that the size of the array is fixed. Therefore, we can easily have stack overflow (i.e the stack is full, and no more elements can be pushed).

Linked Lists

---

The logic remains the same, the only change is that the top technically is our head pointer now instead of it having a fixed indexed. Try implementing this yourself using what we learned about linked lists in the last task.

Let's look at an example:
The main advantage of using a linked list is that the stack can grow and shrink according to the needs at runtime i.e the stack built will be dynamic.

Time Complexity Analysis:

---

If either of the above methods are used to implement the stack both insertion and deletion will take O(1) time. However linked list works faster when the stack size is relatively high (>1000).

Important Resourcses:

https://www.geeksforgeeks.org/stack-data-structure/ (For Stacks)
https://www.geeksforgeeks.org/data-structures/linked-list/ (For Linked Lists)
https://www.tutorialspoint.com/data_structures_algorithms/linked_list_algorithms.htm (For Linked Lists)

Queues

---

Queue is a linear data structure that follows a particular order in which operations are performed: FIFO (First in First Out) or LILO (Last In Last Out). What this means is that the element that is added first to the list will be deleted the first. The main operations performed on a queue are:

• Enqueue: Adds an item to the queue.
• Dequeue: Deletes an item from the queue.
  Fig: Enqueue and Dequeue

Real-life examples of queue can be a traffic jam at a traffic signal where the car that arrived first leaves first or standing in a queue for your meal where the person who arrives first gets their meal first.

Implementation

Queue can be implemented in two different ways:

• Arrays
• Linked List

Arrays

---

In this format, an array is used to maintain the order of the queue. The main components of such a queue are:

• index at which dequeue takes place, front
• index at which enqueue takes place, rear
• length of the array, MAX
• array itself, queue Following is the algorithm to implement a queue (We initialize front and rear as 0):

Enqueue:

begin procedure enqueue: queue, data

   if queue is full //if rear equals to MAX
      return null
   endif

   queue[rear] ← data 
   rear ← rear + 1

end procedure

Dequeue:

begin procedure dequeue: queue

    if queue is empty //if rear equals to 0 or front equals to rear
      return null
   endif

   data ← queue[front]
   front ← front + 1
   return data

end procedure

Example:

The head in the above figure is front and the tail is rear.

The main problem with the above implementation is that the maximum number of elements a queue can have is equal to the size of the array and even if after deleting elements doesn’t change that. To counter this problem, we have a few solutions:

• Reset front and rear when the queue gets empty.
• Maintain only rear index and always deletes from index 0. This requires shifting of the element after every deletion which also increases the complexity.
• Use a circular queue.

However, the array size i.e, the value of MAX itself remains fixed. Therefore, there is a limitation in the maximum amount of element the queue can contain.

Linked Lists

---

Like stacks, queues can also be implemented using linked lists. Over here, the head pointer becomes our front and the tail becomes our rear. Now, try implementing this by yourself with what we have learned in the previous task.

Example:

The main advantage of using linked list is that the queeue can grow and shrink according to the needs at runtime i.e the queue built will be dynamic.

Time Complexity Analysis:

If either of the above methods are used to implement the stack both insertion and deletion will take O(1) time. However linked list works faster when the queue size is relatively high (>1000).

Important Resources:

https://www.geeksforgeeks.org/queue-data-structure/#intro.
https://www.hackerearth.com/practice/data-structures/queues/basics-of-queues/tutorial/.