Stack

A Stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle. Stack has one end, whereas the Queue has two ends (front and rear).
A stack can be defined as a container in which insertion and deletion can be done from the one end known as the top of the stack.
A Stack is an abstract data type with a pre-defined capacity, which means that it can store the elements of a limited size.

Operations on the stack :-

1. push(): When we insert an element in a stack then the operation is known as a push. If the stack is full then the
overflow condition occurs.
2. pop(): When we delete an element from the stack, the operation is known as a pop. If the stack is empty means
that no element exists in the stack, this state is known as an underflow state.
3. peek(): It returns the element at the given position.
4. count(): It returns the total number of elements available in a stack.
5. change(): It changes the element at the given position.
6. display(): It prints all the elements available in the stack.

PUSH operation

The steps involved in the PUSH operation is given below:
1. Before inserting an element in a stack, we check whether the stack is full.
2. If we try to insert the element in a stack, and the stack is full, then the overflow condition occurs.
3. When we initialize a stack, we set the value of top as -1 to check that the stack is empty.
4. When the new element is pushed in a stack, first, the value of the top gets incremented,
i.e., top=top+1, and the element will be placed at the new position of the top.
5. The elements will be inserted until we reach the max size of the stack.

POP operation

The steps involved in the POP operation is given below:
1. Before deleting the element from the stack, we check whether the stack is empty.
2. If we try to delete the element from the empty stack, then the underflow condition occurs.
3. If the stack is not empty, we first access the element which is pointed by the top
4. Once the pop operation is performed, the top is decremented by 1, i.e., top=top-1.

Applications of Stack

1. Recursion: The recursion means that the function is calling itself again. To maintain the previous states,
the compiler creates a system stack in which all the previous records of the function are maintained.
2. DFS(Depth First Search): This search is implemented on a Graph, and Graph uses the stack data structure.
3. Backtracking: Suppose we have to create a path to solve a maze problem. If we are moving in a particular path,
and we realize that we come on the wrong way. In order to come at the beginning of the path to create a new path,
we have to use the stack data structure.
4. Memory management: The stack manages the memory. The memory is assigned in the contiguous memory blocks.

Algorithm of push operation:-

begin
if top=n then stack full
top = top + 1
stack(top) = item;
end

time Complexity : o(1)

Algorithm of pop operation:-

begin
if top = 0 then empty
item = stack(top);
top = top-1;
end

time Complexity : o(1)

Queue

A queue can be defined as an ordered list which enables insert operations to be performed at one end called REAR
and delete operations to be performed at another end called FRONT. Queue is referred to be as First In First Out list.

Complexity

Operations performed on queue

1. Enqueue The Enqueue operation is used to insert the element at the rear end of the queue. It returns void.
2. Dequeue: It performs the deletion from the front-end of the queue. It also returns the element which has been removed from the front-end. It returns an integer value.
3. Peek: This is the third operation that returns the element, which is pointed by the front pointer in the queue but does not delete it.
4. Queue overflow (isfull): It shows the overflow condition when the queue is completely full.
5. Queue underflow (isempty): It shows the underflow condition when the Queue is empty, i.e., no elements are in the Queue.

Types of Queue

1. Linear Queue
In Linear Queue, an insertion takes place from one end while the deletion occurs from another end. The end at which the insertion
takes place is known as the rear end, and the end at which the deletion takes place is known as front end. It strictly follows the FIFO rule.

The elements are inserted from rear end, and if we insert mcrc elements in queue, then far ralust gers incremented on every insertion. drawback is uthing linear
queue is insertion is done only from year and. The linear queue shows. the overflow condition as rear is painating to last. clement of the queue.

2. Circular Queue

In circular queue, all nodes are represented as circular. It's similar to linear queue. except that last element of the queue is connected to the first element. It is also known as ring buffer. as all fools are connected to another end.
Dhrowback of linear queue is overcomes in circular queue. It empty space is available, new element can be added is
empty space by simply increment value of rear.

Priority Queue

The queue to which each element has some pipity associated with it. Based on Priority of the element, elements are
arranged in a priority queue. If elements occur with same priority, then they are served according to FIFO principle.

Array representation of Queue

After deleting an element, the value of front will increase from -1 to 0. however, the queue will look something like following.

Algorithm to insert any element in a queue

Step 1: IF REAR = MAX - 1
Write OVERFLOW
Go to step
[END OF IF]
Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE
SET REAR = REAR + 1
[END OF IF]
Step 3: Set QUEUE[REAR] = NUM
>Step 4

Algorithm to delete an element from queue