(a) What is stack data structure? Write algorithms for linked implementation of stack. (b) What is a D-queue? List various classes of D-queue. Explain insertion and deletion operations with the help of examples.

(a) What is stack data structure? Write algorithms for linked implementation of stack.

Stack Data Structure

A stack is a linear data structure that follows the Last In First Out (LIFO) principle. This means that the last element added to the stack will be the first one to be removed. It is analogous to a stack of plates, where you can only take the top plate off the stack and add a new plate to the top.

A stack has two primary operations:

1. Push: Adds an element to the top of the stack.
2. Pop: Removes the top element from the stack.

Additionally, stacks often support a few more operations:

• Peek or Top: Returns the top element of the stack without removing it.
• IsEmpty: Checks if the stack is empty.
• Size: Returns the number of elements in the stack.

Linked Implementation of Stack

In a linked implementation of a stack, each element in the stack is a node in a linked list. Each node contains the data and a reference to the next node.

Here's a step-by-step algorithm for the linked implementation of a stack:

1. Node Structure: Define a Node class that will represent each element in the stack.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

1. Stack Class: Define a Stack class that will handle the stack operations.

class Stack:
    def __init__(self):
        self.top = None

1. Push Operation: To push an element onto the stack, create a new node and make it the new top of the stack.

def push(self, data):
    new_node = Node(data)
    new_node.next = self.top
    self.top = new_node

1. Pop Operation: To pop an element from the stack, remove the top node and return its data.

def pop(self):
    if self.top is None:
        return None  # Stack is empty
    popped_node = self.top
    self.top = self.top.next
    return popped_node.data

1. Peek Operation: To peek at the top element, return the data of the top node without removing it.

def peek(self):
    if self.top is None:
        return None  # Stack is empty
    return self.top.data

1. IsEmpty Operation: To check if the stack is empty, check if the top node is None.

def is_empty(self):
    return self.top is None

1. Size Operation: To get the size of the stack, traverse the linked list and count the nodes.

def size(self):
    count = 0
    current = self.top
    while current:
        count += 1
        current = current.next
    return count

(b) What is a D-queue? List various classes of D-queue. Explain insertion and deletion operations with the help of examples.

D-Queue (Double-Ended Queue)

A double-ended queue, or deque, is an abstract data type similar to a queue, but with the ability to add and remove elements from both ends. This flexibility allows it to act as both a queue (FIFO) and a stack (LIFO).

Classes of D-Queue

There are two main classes of deques:

1. Input-Restricted Deque: In this deque, insertion is restricted at one end but deletion is allowed at both ends.
2. Output-Restricted Deque: In this deque, deletion is restricted at one end but insertion is allowed at both ends.

Insertion and Deletion Operations

The basic operations for a deque are:

• Insert Front: Add an element at the front.
• Insert Last: Add an element at the rear.
• Delete Front: Remove an element from the front.
• Delete Last: Remove an element from the rear.

Here are examples of these operations:

1. Insert Front:

def insert_front(self, data):
    new_node = Node(data)
    new_node.next = self.front
    if self.is_empty():  # If deque is empty
        self.rear = new_node
    else:
        self.front.prev = new_node
    self.front = new_node

1. Insert Last:

def insert_last(self, data):
    new_node = Node(data)
    if self.is_empty():  # If deque is empty
        self.front = new_node
    else:
        self.rear.next = new_node
        new_node.prev = self.rear
    self.rear = new_node

1. Delete Front:

def delete_front(self):
    if self.is_empty():
        return None  # Deque is empty
    data = self.front.data
    self.front = self.front.next
    if self.front is None:  # Deque is now empty
        self.rear = None
    else:
        self.front.prev = None
    return data

1. Delete Last:

def delete_last(self):
    if self.is_empty():
        return None  # Deque is empty
    data = self.rear.data
    self.rear = self.rear.prev
    if self.rear is None:  # Deque is now empty
        self.front = None
    else:
        self.rear.next = None
    return data

Example

Let's say we have an empty deque, and we perform the following operations:

1. insert_last(10) - Deque becomes: [10]
2. insert_front(20) - Deque becomes: [20, 10]
3. insert_last(30) - Deque becomes: [20, 10, 30]
4. delete_front() - Deque becomes: [10, 30]
5. insert_front(40) - Deque becomes: [40, 10, 30]
6. delete_last() - Deque becomes: [40, 10]

After these operations, the deque has elements 40 and 10, with 40 at the front and 10 at the rear.