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

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.

Operations on Stack:

1. Push: Add an element to the top of the stack.
2. Pop: Remove the top element from the stack.
3. Peek or Top: Retrieve the top element of the stack without removing it.
4. IsEmpty: Check if the stack is empty.
5. IsFull: Check if the stack is full (mainly for array implementation).

Linked Implementation of Stack

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

Node Structure

Node {
    Data data;
    Node *next;
}

Push Algorithm

Algorithm Push(data):
1. Create a new node with the given data.
2. Make the new node's next point to the current top of the stack.
3. Update the top pointer to point to the new node.

Pop Algorithm

Algorithm Pop():
1. If the stack is empty, return an error or null.
2. Store the top node's data to return later.
3. Update the top pointer to the next node in the stack.
4. Delete the old top node.
5. Return the stored data.

Peek Algorithm

Algorithm Peek():
1. If the stack is empty, return an error or null.
2. Return the data of the top node.

IsEmpty Algorithm

Algorithm IsEmpty():
1. Return true if the top pointer is null.
2. Otherwise, return false.

D-Queue (Double-Ended Queue)

A D-queue, or double-ended queue, is a data structure similar to a queue where insertion and deletion operations can be performed from both ends. This means you can add or remove elements from the front as well as the back.

Classes of D-queue:

1. Input Restricted D-queue: Allows insertion at one end but deletion at both ends.
2. Output Restricted D-queue: Allows deletion at one end but insertion at both ends.

Operations on D-queue:

1. InsertFront: Insert an element at the front of the D-queue.
2. InsertLast: Insert an element at the rear of the D-queue.
3. DeleteFront: Remove the front element from the D-queue.
4. DeleteLast: Remove the rear element from the D-queue.
5. GetFront: Get the front element of the D-queue.
6. GetRear: Get the rear element of the D-queue.

Insertion and Deletion Examples

InsertFront Example

D-queue: 10 <- 20 <- 30
InsertFront(5)
D-queue after insertion: 5 <- 10 <- 20 <- 30

InsertLast Example

D-queue: 10 <- 20 <- 30
InsertLast(40)
D-queue after insertion: 10 <- 20 <- 30 <- 40

DeleteFront Example

D-queue: 10 <- 20 <- 30
DeleteFront()
D-queue after deletion: 20 <- 30

DeleteLast Example

D-queue: 10 <- 20 <- 30
DeleteLast()
D-queue after deletion: 10 <- 20

In summary, stacks and D-queues are both linear data structures that allow for the storage and retrieval of data, but they differ in how elements can be inserted and removed. Stacks follow the LIFO principle, while D-queues allow for more flexible operations at both ends.