Data Structures: Stacks Overview

A stack is a linear data structure where insertion and deletion occur at one end, termed the TOP.
It operates on the Last In First Out (LIFO) principle; the last item added is the first to be removed.
Key operations on a stack include:
- Push: Inserts an element onto the stack.
- Pop: Removes the top element from the stack.
A stack can be implemented using an array or a linked list.
Essential components in an array-based stack:
- TOP: Pointer to the top element's index.
- MAXSTK: Maximum number of elements the stack can hold.
Stack conditions:
- Overflow occurs if TOP = MAXSTK (stack is full).
- Underflow occurs if TOP = 0 (stack is empty).
Additional stack operations may include:
- Dup: Duplicates the top item.
- Peek: Inspects the top item without removing it.
- Swap: Exchanges the top two items.
- Rotate: Rotates the top n items of the stack.
Algorithms for stack operations (Push and Pop) must check for overflow and underflow conditions.

A queue is a linear data structure where additions (enqueue) occur at the rear and removals (dequeue) occur from the front.
Operates on the First In First Out (FIFO) principle; the first element added is the first to be removed.
Key operations on a queue:
- Enqueue: Adds an element to the rear.
- Dequeue: Removes an element from the front.
- Empty: Checks if the queue is empty.
- Front: Returns the front element without removing it.
- Size: Returns the total number of elements in the queue.
The queue model consists of input via enqueue and output via front, with deletion performed by dequeue.
Example of queue in real-life: Lines at a food court, where service is provided on a first-come-first-served basis.

Polish notation (prefix notation) places operators before their operands, eliminating the need for parentheses.
Three types of notations for expressions include:
- Infix: Operators placed between operands (e.g., A + B).
- Prefix: Operators placed before operands (e.g., +AB).
- Postfix: Operators placed after operands (e.g., AB+).
Operator precedence is crucial in infix notation, where operators must be evaluated in a specific order:
- Highest: Exponential ($)
- Multiplication/Division: (*, /)
- Lowest: Addition/Subtraction (+, -)

Infix to Postfix Conversion algorithm utilizes a stack for operator precedence management.
Postfix Evaluation algorithm processes operands and operators using a stack to return the result.
Infix to Prefix Conversion follows a similar approach, scanning from right to left and managing operators within a stack context.

A circular queue connects the last node back to the first, allowing continuous traversal without reallocation.
Operations in a circular queue still adhere to the FIFO principle, with efficiency improvements in insertions and deletions (O(1) time).
Implementations can be made using:
- Single linked list.
- Double linked list.
- Arrays.### Circular Linked List
A circular linked list consists of nodes with pointers to the next node, forming a circular structure.
Algorithm for creation involves defining a node structure with an integer info and a pointer to the next node.
A clist class contains member variables for pointers to nodes and functions for creating and displaying the linked list.
Creation and display of the list are executed through calls to member functions.

Insert Operation:
- Check for overflow conditions; if both front and rear point to n, report "Overflow."
- If the queue is empty (front = 0), initialize front and rear to 1 and insert the value.
- Wrap the rear pointer to the start of the queue if it reaches n.
- Increment the rear pointer otherwise and insert the value.
Delete Operation:
- Check for underflow; if front = 0, report "Underflow."
- Remove the front element and check if the queue becomes empty (front equals rear).
- Update the front pointer, wrapping it if it reaches n.

A deque allows insertion and removal of elements from both ends (front and rear).
It combines functionalities of both stacks and queues without enforcing strict ordering.
Useful for applications requiring flexible data access on both ends.

A priority queue is an ordered collection that allows insertion of items at the rear and removal from the front.
Items are ordered based on their key value, ensuring the item with the lowest key is always at the front.
Analogous to organizing letters by urgency; important items are handled first.

Utilized in scenarios where FIFO processing is needed, such as:
- Serving requests for shared resources (printers, CPUs).
- Managing calls in a call center.
- Buffering in media players and playlists.
- Handling real-time system interrupts promptly.

Recursion occurs when a function calls itself for solving problems more efficiently.
It simplifies code length and improves readability for problems like calculating factorials.
For factorials, the function keeps calling itself with decremented values until it reaches the base case.

An efficient sorting algorithm that operates on the divide-and-conquer principle.
Steps:
- Select a pivot; partition the array into smaller and larger elements.
- Recursively apply quicksort to the subarrays created from partitioning.
Averages O(n log n) comparisons, making it fast for sorting elements.

Sorted structures like priority queues can be implemented using heaps for efficient insertion.
Arrays may also implement priority queues, albeit with slower insertion speeds.
Priority queues are beneficial in multitasking operating systems for managing process scheduling.