DSA PreFi

Stack

An abstract data type that follows the LIFO (Last In, First Out) principle where the last item added is the first to be removed.

Push

The operation that inserts or adds an element onto the top of the stack.

Pop

The operation that removes the top element from the stack.

Peek (Top)

The operation that returns the top element of the stack without removing it.

Underflow

An error that occurs when attempting to pop an element from an empty stack.

Overflow

An error that occurs when attempting to push an element into a full stack.

Applications of Stack

Used in expression evaluation, function calls, backtracking algorithms, and undo mechanisms.

Postfix Expression

An arithmetic expression where the operator follows the operands (e.g., AB+).

Prefix Expression

An arithmetic expression where the operator precedes the operands (e.g., +AB).

Infix Expression

An arithmetic expression where the operator is written between the operands (e.g., A + B).

Stack Implementation Using Array

Stack is implemented using an array with a variable “top” to track the top index.

Stack Implementation Using Linked List

Stack is implemented using nodes where each node contains data and a pointer to the next node.

Queue

An abstract data type that follows the FIFO (First In, First Out) principle where the first element inserted is the first to be removed.

Enqueue

The operation that inserts or adds an element at the rear of the queue.

Dequeue

The operation that removes an element from the front of the queue.

Front

The position of the first element in the queue.

Rear

The position of the last element in the queue.

Circular Queue

A variation of a queue where the last position is connected back to the first position to make a circle.

Priority Queue

A queue where each element is associated with a priority and served based on priority rather than arrival order.

Double-Ended Queue (Deque)

A queue that allows insertion and deletion of elements from both ends.

Queue Underflow

Error condition that occurs when attempting to remove an element from an empty queue.

Queue Overflow

Error condition that occurs when attempting to add an element to a full queue.

Queue Implementation Using Array

Queue implemented with an array and front/rear pointers to manage insertion and deletion.

Queue Implementation Using Linked List

Queue implemented using nodes with pointers to the next node for dynamic memory allocation.

Linked List

A linear data structure where each element (node) contains data and a reference (pointer) to the next node.

Node

The basic unit of a linked list that contains data and a pointer to the next node.

Head

The first node in a linked list.

Tail

The last node in a linked list whose next pointer is null.

Singly Linked List

A linked list where each node points only to the next node.

Doubly Linked List

A linked list where each node has two pointers: one pointing to the next node and one to the previous node.

Circular Linked List

A linked list where the last node points back to the first node, forming a circle.

Advantages of Linked List

Dynamic memory allocation, ease of insertion/deletion without shifting elements.

Disadvantages of Linked List

Requires extra memory for pointers and has sequential access only.

Insertion in Linked List

Adding a new node by adjusting the pointers between existing nodes.

Deletion in Linked List

Removing a node by adjusting the pointers of the surrounding nodes.

Traversal in Linked List

Visiting each node of the linked list sequentially to access or display data.

Search in Linked List

Finding a node by comparing its data with the target value.

Stack vs Queue

Stack is LIFO; Queue is FIFO.

Recursion

A function that calls itself directly or indirectly to solve a problem.

Base Case

The condition in recursion that stops further recursive calls.

Recursive Case

The part of the recursion where the function calls itself with modified parameters.

Direct Recursion

When a function calls itself directly.

Indirect Recursion

When a function calls another function that calls the first one again.

Tail Recursion

When the recursive call is the last operation in the function.

Non-Tail Recursion

When the recursive call is followed by another operation.

Advantages of Recursion

Reduces code size, simplifies problems like tree traversal and factorial.

Disadvantages of Recursion

Uses more memory and has risk of stack overflow for deep recursion.

Call Stack

A structure that stores information about active subroutines/functions including parameters, return addresses, and local variables.

Applications of Recursion

Used in sorting algorithms (quick sort, merge sort), tree traversal, and backtracking problems.