First You Tell me Linear and Non-linear data structure

Linear :
● A linear data structure is a type of data structure where elements are arranged
sequentially or linearly.
● Each element is connected to its previous and next element (except the first and
last).
● Data elements are stored in a single level.

Example: Array, Stack, Queue, Linked List,

Non-Linear Data Structure

● A non-linear data structure is a type of data structure where elements are not
arranged sequentially.
● Elements can be connected to multiple elements forming a hierarchy or graph.
● Data is stored at multiple levels.

Example: Tree, Graph

Stack :

A stack is a linear data structure that stores elements in a sequential manner and allows
insertion and deletion only at one end, called the "top" of the stack.

Stack Follows the principle of “Last In, First Out” (LIFO) principle. Which means the
last element added to the stack will be the first one to be removed.
Real Life Example:

1. Stack of Plates (Most Common Example)

● Imagine a cafeteria where plates are kept one on top of another.

● When new plates arrive, they are placed on the top → (Push operation).

● When someone needs a plate, they take from the top → (Pop operation).

● The first plate placed at the bottom will be the last one to be used.

Why it’s a Stack?

Because only the topmost plate can be accessed directly — just like in Stack where only
the top element can be inserted or removed.

2. Undo/Redo in Text Editors

● When you type something in MS Word or Notepad, each action (typing, deleting,
formatting) is pushed into a stack.

● When you press Undo (Ctrl+Z) → the last action you did is popped out first.

● If you undo multiple times, actions are undone in reverse order.

● Similarly, Redo (Ctrl+Y) maintains another stack for redoing operations.

Why it’s a Stack?

Because actions follow the Last In, First Out order — the last thing you typed is the
first to be undone.

3. Browser History (Back Button)

● Suppose you open pages in this order:
Google → YouTube → Instagram → ChatGPT
 ● Each page is pushed into the history stack.

● If you click the Back button, the browser pops the last visited page first
(ChatGPT → Instagram → YouTube → Google).

Components of Stack :

1. Top

● Definition: Top is a variable (or pointer) that stores the position of the last
inserted element in the stack.

● Purpose: It helps us know where the next element should be inserted

(Push) or from where the element should be removed (Pop).

● If the stack is empty → Top = -1 (commonly used).

● If the stack is full → Top = MaxStack – 1.

2. MaxStack

● Definition: MaxStack is a variable that defines the maximum number of

elements that can be stored in the stack.

● Example: If MaxStack = 5, then the stack can hold at most 5 elements.

● Once the stack reaches this limit, any further Push operation causes "Stack
Overflow".

Quick Example (MaxStack = 5)

● Start: Top = -1 (stack empty)

 ● Push(10) → Top = 0, Stack = [10]

● Push(20) → Top = 1, Stack = [10, 20]

● Push(30) → Top = 2, Stack = [10, 20, 30]

● Pop() → removes 30, Top = 1, Stack = [10, 20]

✅ In short for students:

● Top → points to the last element in the stack.

● Element → actual data stored in the stack.

● MaxStack → maximum size of the stack (capacity).

Stack Operations :
1. isEmpty Operation

● Definition:

The isEmpty Operation is used to check whether the stack is empty. isempty() returns a
boolean value (true or false) depending on whether the stack is empty or not.

How the isEmpty() operation work:

● Checks the top variable, If the top is pointing to -1. Return true, as the top is not
pointing to any element
If Top == -1 → Stack is Empty → return True.

● Else if the top is greater than -1, return false as the top is pointing to some element
○ Otherwise → return False.

● Example:
Stack = []
○ Empty stack means Top == -1→ isEmpty() = True
 ○ Stack = [10, 20] → isEmpty() = False

2. Push Operation

● Definition: Push is the process of inserting (adding) a new element into

the stack at the top position.
It adds a new element to the top of the stack.

It takes the element as its input and adds it to the top of the stack.

This operation increases the size of the stack by one. push is a type of function that is
basically used to insert an element in the stack, and this is the only method that can insert
the element in the stack.

how the push() method works:

● Checks If the stack has space to insert the element

● If the stack is full, no element can be inserted, so it will return an error

● Else if the stack has the capacity, the top will be increment by one and will
be pointing to the next empty space in the data structure

● Assign the given element to where the top is pointing in the data structure
 ● Inserting is done and shows a success message
Push Algorithm:

A new element is always inserted from the topmost position of the Stack; we always need
to check if the top is empty or not, i.e., TOP=Max-1 if this condition goes false, it means
the Stack is full, and no more elements can be inserted, and even if we try to insert the
element, a Stack overflow message will be displayed.

Algorithm:

Step-1: If TOP = Max-1 (Check if the stack is full (Top == MaxStack - 1). If yes → Overflow
error.)

Print “Overflow”

Goto Step 4

Step-2: Set TOP= TOP + 1 (Increase Top by 1.)

Step-3: Set Stack[TOP]= ELEMENT (Place the new element at Stack[Top].)

Step-4: END

● Example:

○ Stack = [10, 20], Top = 1

○ Push(30) → Stack = [10, 20, 30], Top = 2

3. Pop Operation

● Definition: Pop is the process of removing (deleting) the element from the
top of the stack.
It removes the top element from the stack.
This operation decreases the size of the stack by one.
Pop is also a type of method/function that is basically used to remove/delete an element
from the stack, and this is the only method that is used for the removal of an element
from the stack.

How the pop() method works:

● Checks the size of the stack, If the stack is empty. It will return false, as there are
no elements to remove

● If the stack is not empty, the element pointing by the top can be stored in a
variable

● Now 0 can be assigned to the element where the top is pointing.

● The popped value can be returned using the variable

Pop Algorithm:

POP means to delete an element from the Stack. Before deleting an element, make sure to
check if the Stack Top is NULL, i.e., TOP=NULL. If this condition goes true, it means
the Stack is empty, and no deletion operation can be performed, and even if we try to
delete, then the Stack underflow message will be generated.

Algorithm:

Step-1: If TOP = NULL (or -1)

Print “Underflow”

👉 Meaning: Check whether the stack is empty.

 ● In an array implementation of a stack, TOP = -1 means no elements are present.
● If the stack is empty and you still try to remove an element →
Underflow Error (because nothing is there to remove).

📌 Action:

● Print "Underflow" message.

● Jump to Step-4 (END) because the operation cannot continue.

Goto Step 4

Step-2: Set VAL = Stack[TOP] (Take out the element at Stack[Top].)

👉 Meaning: Take out the element from the current TOP position of the stack.

● VAL is just a temporary variable that stores the element we are removing.

● Example: If Stack = [10, 20, 30], and TOP = 2 → VAL = Stack[2] = 30.

📌 Now, we have the deleted element in VAL

Step-3: Set TOP = TOP - 1 ( Decrease Top by 1.)

👉 Meaning: Reduce the value of TOP by 1 to point to the new last element.

● After removing an element, the "top" moves down.

● Example:
○ Before POP → Stack = [10, 20, 30], TOP = 2

○ After POP → Stack = [10, 20], TOP = 1

○ Now the stack correctly represents the remaining elements.

Step-4: END

● Example:

○ Stack = [10, 20, 30], Top = 2

○ Pop() → removes 30 → Stack = [10, 20], Top = 1
4. Peek/ topElement() Operation

● Definition: Peek is the operation that returns the element at the top of the
stack without removing it.

It returns the top element without removing it.

This operation does not change the stack size and is useful when inspecting the top
element without modifying the stack.

How the peek() operation work:

● Checks the size of the element, If the stack is empty. An error will be returned as
there are no elements to return

● If the stack is not empty, the element pointing by the top will be stored to a
variable

● Return the variable having the top element

Peek Algorithm:
When we need to return the value of the topmost element of the Stack without deleting it from
the Stack, the Peek operation is used.

This operation first checks if the Stack is empty, i.e., TOP = NULL; if it is so, then an
appropriate message will display, else the value will return.

Algorithm:

Step-1: If TOP = NULL (Check if the stack is empty (Top == -1).)

PRINT “Stack is Empty”

Goto Step 3

Step-2: Return Stack[TOP] ( Return the element at Stack[Top].)

Step-3: END

● Example:

○ Stack = [10, 20, 30], Top = 2

○ Peek() → returns 30 (but stack remains unchanged)

5. isFull Operation

● Definition:

The isFull Operation is used to Checks whether the stack has reached its maximum
capacity. isfull() returns a Boolean value (true or false) depending on whether the stack is full
or not.

This operation determines if the stack is at maximum capacity and cannot hold additional
elements.

How the isFull() operation work:

● Checks the top variable, If the top is equal to the given size. Return true as the capacity of
the data structure is full.

If Top == MaxStack - 1 → Stack is Full → return True.

● Else if the top is lesser than the given size, return false
○ Otherwise → return False.

● Example:

○ MaxStack = 5

○ Stack = [10, 20, 30, 40, 50], Top = 4 → isFull() = True

6. size():
Size is a function in stack definition which is used to find out the number of elements that are
present inside the stack.

The size() is used to calculate the size of the stack, which returns the size of the stack. The size is
the capacity of the stack or the number of elements a stack can have at a single time. The size()
method is used only when the implementation of stacks is done using arrays because there is a
limited space while using arrays.
The variable ‘top' will be used to calculate the size of the stack. For example, If the top is
pointing to 3 means there are 4 elements in the stack, so we can return top + 1, resulting in the
size of 4 here.

Multiple Stacks :
1. Introduction
● A stack is a linear data structure that follows the LIFO (Last In, First Out)
principle.

● In some situations, a single stack is not enough to store or manage large or

different types of data.

● To overcome this limitation, we use multiple stacks within the same

memory space.
2. What is Multiple Stack?
● Multiple Stack means having two or more stacks inside a single array.

● Instead of allocating separate arrays for each stack, we divide one array
into multiple parts.

● This method helps in efficient memory utilization.

3. Example Setup (Two Stacks in One Array)

Suppose we have an array STACK[10].
We divide it into two stacks:

●
 ● Stack A grows from left to right (starting from index 0).

● Stack B grows from right to left (starting from index 9).

👉 The total combined size of Stack A and Stack B will never exceed n = 10.

Indexes: 0 1 2 3 4 5 6 7 8 9
↑ ↑
Stack A → ← Stack B

4. Operations on Multiple Stacks

(A) Initialization

● Let TOPA = -1 (no elements in Stack A yet).

● Let TOPB = n (here, n=10, so TOPB = 10).

(B) PUSH Operation

1. Push into Stack A

○ Check: If TOPA + 1 == TOPB, then overflow (no more space).

○ Else: TOPA = TOPA + 1, insert element at STACK[TOPA].

2. Push into Stack B

○ Check: If TOPB - 1 == TOPA, then overflow.

○ Else: TOPB = TOPB - 1, insert element at STACK[TOPB].

(C) POP Operation

1. Pop from Stack A

○ Check: If TOPA == -1, then underflow (empty).

○ Else: Take element from STACK[TOPA], then TOPA = TOPA -

1.

2. Pop from Stack B

○ Check: If TOPB == n, then underflow.

○ Else: Take element from STACK[TOPB], then TOPB = TOPB +

1.

{ The Diagram
Indexes: 0 1 2 3 4 5 6 7 8 9
↑ ↑
Stack A → ← Stack B

1. Array Representation
● We have one array of size 10 → STACK[0..9].

● Indexes go from 0 (leftmost) to 9 (rightmost).

● Instead of creating two separate arrays, we divide this single array into two
stacks.

2. Stack A (Left Side Stack)

● Stack A starts at index 0 (the left end of the array).
 ● It grows from left to right.

○ First element goes to STACK[0].

○ Next to STACK[1], then STACK[2], and so on.

● Its TOP pointer (TOPA) starts at -1 (empty).

● Each PUSH increases TOPA by +1.

● Each POP decreases TOPA by -1.

👉 So Stack A looks like this when filled:

STACK A → [11] [22] [33] [44] ...

Indexes → 0 1 2 3

3. Stack B (Right Side Stack)

● Stack B starts at index 9 (the right end of the array).

● It grows from right to left.

○ First element goes to STACK[9].

○ Next to STACK[8], then STACK[7], and so on.

● Its TOP pointer (TOPB) starts at n (here, 10) when empty.

● Each PUSH decreases TOPB by -1.

● Each POP increases TOPB by +1.

👉 So Stack B looks like this when filled:

STACK B → [99] [88] [77] ...

Indexes → 9 8 7
}

5. Advantages of Multiple Stacks

● Efficient memory utilization → unused space of one stack can be used by
the other.

● Useful in situations where two different processes need separate stacks but
can share memory.

● Reduces the need for creating multiple arrays.

6. Applications
● Memory management in compilers and operating systems.

● Implementing undo/redo functionality (two stacks: one for undo, one for
redo).

● Expression evaluation (multiple stacks used for operands and operators).

✅ Key Point for Students:

Instead of wasting memory with separate arrays, multiple stacks in one array
allow us to use memory more efficiently. The only restriction is that the combined
size must not exceed the array size.