3.1
Data Structure
A data structure A particular way of organising logically related data items into a single unit.
3.1.1
Classification of Data Structures
Data structures split first into simple (array, structure) and compound types built from them. Compound structures are further linear — elements form a sequence in memory (stack, queue, linked list) — or non-linear — elements sit in random locations with no fixed order (tree, graph). A second, independent split is by memory behaviour: static structures (like arrays) get a fixed block of primary memory before the program runs, while dynamic structures (like linked lists) request memory during execution and grow or shrink as needed.
3.1.2
Operations on Data Structures
- Traversing — visiting every element, first to last.
- Searching — finding the location of one or more elements matching a condition.
- Inserting — adding a new item, sometimes at a specific position.
- Deleting — removing an item, by value or by position.
- Sorting — arranging elements in ascending or descending order, to make searching faster.
- Merging — combining two data structures (often sorted ones) into a third.
Which data structure fits a problem best usually comes down to which of these operations happen most often, and how cheaply each structure supports them.
3.2
Stack
A stack is an ordered list where every insertion and deletion happens at one end, called Top — like a stack of plates. Because the last item placed on top is always the first one removed, this is the Last-In-First-Out (LIFO) principle. A stack is a logical concept, usually implemented physically using an array — which makes it a static structure with a fixed maximum size.
3.2.1
Implementation of Stack
A variable TOS (Top Of Stack) tracks the last filled position — starting at -1 for an empty stack, and rising toward N-1 as the array fills. The stack's current top element is always STACK[TOS].
3.2.2
Operations on Stack
Insertion and deletion on a stack are renamed push and pop, since — unlike an ordinary array — they're restricted to the top position only. Pushing into a full stack (TOS = N-1 already) causes stack overflow; popping an empty stack (TOS = -1) causes stack underflow.
PUSH operation algoritham
void push(int stack[], int val)
{
if (tos < n)
{
tos++;
stack[tos] = val;
}
else
cout << "Overflow";
}
POP operation algoritham
int pop(int stack[])
{
if (tos > -1)
{
val = stack[tos];
tos--;
}
else
cout << "Underflow";
return val;
}
Because stacks follow LIFO, they're the natural tool for reversing a string and for converting/evaluating polish (prefix/postfix) arithmetic expressions.
3.3
Queue
A queue models a real waiting line: new items join at the Rear, and items leave from the Front — First-In-First-Out (FIFO). Like a stack, it's a logical concept usually implemented with a static array.
3.3.1
Implementation of Queue
Two pointers, Front and Rear, both start at -1 for an empty queue. The first insertion sets both to 0; after that, only Rear moves forward on insertion and only Front moves forward on deletion.
3.3.2
Operations on Queue
Insertion increments Rear, then stores the value there — queue overflow if Rear has hit the last index. Deletion reads the value at Front, then increments Front — queue underflow if the queue is already empty. Unlike a stack, a queue's deletion never shifts the remaining elements; it just moves Front forward, and both pointers reset to -1 once the last element is removed.
void ins_q(int queue[], int val)
{
if (rear == -1)
{
front = 0;
rear = 0;
queue[rear] = val;
}
else if (rear < n)
{
rear++;
queue[rear] = val;
}
else
cout << "Overflow";
}
Queues model job scheduling — a printer's job buffer, for instance, holds print requests in FIFO order.
3.3.3
Circular Queue
A plain (linear) queue has a real flaw: once Rear reaches the array's last index, no further insertion is allowed — even if many front positions were freed by earlier deletions. A circular queue fixes this by treating the array as a ring, where Rear wraps back around to index 0 once it passes the end, reclaiming those freed positions instead of wasting them.
3.4
Linked List
Unlike stacks and queues, a linked list is a genuinely dynamic data structure — no memory is reserved in advance. Each element, called a node, holds a data part and a link (a pointer to the next node), so nodes can live scattered anywhere in memory yet still form an ordered chain. A special pointer, Start (or Header), holds the address of the first node; the last node's link is NULL.
3.4.1
Implementation of Linked List
A node is naturally defined as a self-referential structure — a structure containing a pointer to another instance of its own type, first introduced in Chapter 1.
struct Node
{
int data;
Node *link; // points to the next node — self-referential
};
Node *Start; // holds the address of the first node
3.4.2
Operations on Linked List
Creation repeatedly allocates a node, fills its data, and links it to the previous node (or to Start, if it's the first). Traversal starts from Start, follows each node's link to the next, and stops when a link is NULL. Insertion and deletion at a given position both begin with a traversal to locate the node's neighbours — PreNode and PostNode — and then simply relink pointers around the change; deletion additionally frees the removed node's memory.
Because memory is claimed only as items are actually added, a linked list never hits the "overflow" wall that array-based stacks and queues do.
01What is a data structure?
A particular way of organising logically related data items into a single unit.
02How are data structures classified based on memory allocation?
Static data structures (like arrays) get memory fixed before execution and can't resize. Dynamic data structures (like linked lists) allocate memory during execution and can grow or shrink at runtime.
03What's the difference between a linear and a non-linear data structure?
A linear structure's elements form a sequence in memory (e.g. stack, queue). A non-linear structure's elements sit in random locations with no fixed sequence (e.g. tree, graph).
04What principle does a stack follow, and where do insertions and deletions happen?
Last-In-First-Out (LIFO) — both insertion and deletion happen at the same end, called Top.
05What are stack overflow and stack underflow?
Overflow: trying to push into a full stack (TOS has reached the last index). Underflow: trying to pop from an empty stack (TOS is -1).
06What principle does a queue follow, and where do insertions and deletions happen?
First-In-First-Out (FIFO) — insertion happens at the rear end, deletion happens at the front end.
07What limitation of a linear queue does a circular queue solve?
In a linear queue, once Rear reaches the last index, no more insertions are possible even if earlier deletions freed positions at the front. A circular queue wraps Rear back to the start, reclaiming those freed positions.
08What is a linked list, and what does each node contain?
A dynamic data structure made of nodes scattered in memory and connected by pointers; each node holds a data part and a link (a pointer to the next node).
09What is a self-referential structure, and how does it relate to linked lists?
A structure containing a pointer to another instance of its own type. A linked list's node is defined this way, since its link member points to another node of the same structure type.
10How does traversal of a linked list work?
A temporary pointer starts at the address in Start, reads each node's data, then follows its link to move to the next node — continuing until it reaches a node whose link is NULL.
11Why doesn't a linked list face an overflow situation the way arrays do?
Memory for each node is allocated dynamically at runtime as items are added, rather than fixed in advance — the list simply keeps growing as long as memory is available.
12What steps are involved in inserting or deleting a node in a linked list?
First locate the target node's neighbours (PreNode and PostNode) through traversal, then relink pointers to include or bypass the node. For deletion, the removed node's memory is also freed.
