Lab on Data Structure: Practical Unit 3

Table of Contents

1. Task 6: Stack Operations via Linked List
2. Task 7: Stack Operations via Array (Templates)
3. Task 8: Queues via Circular Array (Templates)
4. Task 9: Double-ended Queues (De-queue)
5. Practical Viva Questions

1. Task 6: Stack Operations via Linked List

Lab Assignment: Perform Stack operations using Linked List implementation.

In this implementation, the Top of the stack is always represented by the Head of the linked list. This allows for O(1) Push and Pop operations without worrying about array size limits.

Push: Insert a new node at the beginning of the list.
Pop: Remove the node from the beginning of the list.
Display: Traverse from the Head to the end of the list.

2. Task 7: Stack Operations via Array (Templates)

Lab Assignment: Perform Stack operations using Array implementation. Use Templates.

Templates allow the stack to hold any data type (integers, floats, or objects) while using a single logic definition.

template <class T>
class Stack {
  T arr[MAX];
  int top;
public:
  Stack() { top = -1; }
  void push(T val);
  T pop();
};

Check for Overflow/Underflow: In array-based stacks, always check if top == MAX-1 before pushing and top == -1 before popping.

3. Task 8: Queues via Circular Array (Templates)

Lab Assignment: Perform Queues operations using Circular Array implementation. Use Templates.

A Circular Queue solves the limitation of a simple array queue where space at the front cannot be reused.

Rear Update: rear = (rear + 1) % SIZE;
Front Update: front = (front + 1) % SIZE;

4. Task 9: Double-ended Queues (De-queue)

Lab Assignment: Create and perform different operations on Double-ended Queues (De-queues) using Linked List implementation.

A De-queue allows insertion and deletion from both the Front and the Rear. Using a Doubly Linked List is often preferred here as it provides O(1) access to the previous node at the Rear for deletion.

Operation	Description
insertFront()	Adds element to the start of the list.
insertRear()	Adds element to the end of the list.
deleteFront()	Removes the first element.
deleteRear()	Removes the last element.

5. Practical Viva Questions

Q1: Why is a Linked List implementation of a Stack considered "dynamic"?
Unlike the array implementation, it does not require a predefined size; memory is allocated only when a new element is pushed.

Q2: When is a Circular Queue "Full"?
In a typical implementation, it is full when (rear + 1) % SIZE == front.

Q3: What are the two types of restricted De-queues?
1. Input-Restricted (insertion at one end, deletion at both) and 2. Output-Restricted (insertion at both ends, deletion at one).

Template Tip: When defining template methods outside the class, remember to use the syntax: template <typename T> void Stack<T>::push(T val).