C++ Programming and Data Structures Notes

C++ Programming and Data Structures Course Objectives

Understand C++ Classes: Design and implement classes focusing on code reuse, object-oriented programming concepts, data abstraction, and encapsulation.
Basics of C++: Learn about arrays, functions, pointers, constructors, and structures.
Data Structures: Explore linear and non-linear data structures with focus on applications.
Importance of Data Structures: Understand the role of data structures in efficient data storage, organization, and management in programming.
Knowledge of Data Structures: Gain knowledge of basic data structures including:
- Arrays
- Lists
- Stacks
- Queues
- Trees
- Graphs
Stack ADT: Evaluating arithmetic expressions and applications.
Queue ADT: Implementation of circular queue and double-ended queues with applications.

CO-PO Mapping Matrix

CO	PO1	PO2	PO3	PO4	PO5
CO1	3	2	2	2	2
CO2	3	3	3	3	2
CO3	3	3	3	3	2
CO4	3	3	3	3	2
CO5	3	3	2	3	1

Course Outcomes

CO1: Implement Object-Oriented Programming concepts.
CO2: Utilize arrays and functions within C++ programming.
CO3: Code functions for linear data structure operations.
CO4: Select appropriate linear data structures for problem-solving.
CO5: Operate on tree data structures using C++ programs.

Linear Data Structures - Stacks and Queues

Stack ADT

Definition: A stack is a linear data structure where insertions (push) and removals (pop) happen at the same end, termed as "top". The other end is termed as the "bottom" of the stack.

Stack Operations

empty():
- Returns true if the stack is empty; otherwise, false.
size():
- Returns the count of elements in the stack.
top():
- Returns the top element without modifying the stack.
pop():
- Removes the top element from the stack.
push(x):
- Adds element x to the top of the stack.

Push Operation Example

Initial Stack:
- Top:
- Push 1 → {1}
- Push 2 → {1, 2}
- Push 3 → {1, 2, 3}
- Push 4 → {1, 2, 3, 4}
- Push 5 → {1, 2, 3, 4, 5}

Pop Operation Example

Pop sequence: Pop (removes 5), Pop (removes 4), Pop (removes 3)…

Advantages of Stacks

Efficient Memory Management: Utilizes stack to manage function calls efficiently.
Recursion: Effective for recursion and dynamic memory allocation.
Hardware Support: Hardware supports stack operations, beneficial for OS management.

Disadvantages of Stacks

Limited Random Access: Cannot access middle elements as stacks do not support random access operations.
Fixed Size: Stack size may be limited leading to overflow in some environments.
Compiler Optimization: Limits stack usage, necessitating alternative data structures in some situations.

Node and Stack Class Implementation

Node Class:

```cpp
class Node {
public:
int data;
Node* next;
};

### Stack Class:

cpp
class Stack {
private:
Node* top;
public:
Stack() {
top = NULL;
}
void push(int value);
void pop();
int getTop();
bool isEmpty();
};

### Stack Operations Implementation

cpp
// Function to push a new element onto the stack
void Stack::push(int value) {
Node* newNode = new Node;
newNode->data = value;
newNode->next = top;
top = newNode;
cout << "Pushed: " << value << endl;
}

// Function to pop the top element from the stack
void Stack::pop() {
if (isEmpty()) {
cout << "Stack is empty. Cannot pop." << endl; return; } Node* temp = top; top = top->next;
cout << "Popped: " << temp->data << endl;
delete temp;
}

// Function to check if stack is empty
bool Stack::isEmpty() {
return top == NULL;
}

### Application of Stacks  
- **Balancing Symbols**: Checking for balanced symbols like curly brackets.  
- **Infix to Postfix Conversion**: Useful in expression evaluation.  
- **Evaluating Arithmetic Expressions**: Utilizing reverse Polish notation.  
- **Function Calls**: Managing nested function calls.

## Example: Balancing Symbols Algorithm  
1. Initialize an empty stack.  
2. Iterate through each character in the expression:  
   - If opening symbol, push to stack.  
   - If closing symbol, check for match with top of stack and pop if matched.  
3. After the iteration, if the stack is empty, the input is balanced.  

## Evaluating Arithmetic Expressions in RPN  
- **Postfix Notation**: The operator comes after its operands. Example:  
  - Expression `AB+` evaluates to `A + B`.  
- **Evaluation Steps**:  
1. Push operands onto stack.  
2. On encountering an operator, pop the top two operands, perform the operation, and push the result back to the stack.  
3. Continue till all tokens are processed.

# Queue ADT  
## Definition  
- **Queue**: A linear data structure following First-In-First-Out (FIFO) principle where elements are added at the rear and removed from the front.  

### Queue Operations  
1. **enqueue(item)**: Add an item to the rear of the queue.  
2. **dequeue()**: Remove the item from the front of the queue.  
3. **getFront()**: Returns the item at the front without removing it.  
4. **isEmpty()**: Checks if the queue is empty.  
5. **size()**: Returns the number of elements currently in the queue.

## Queue Characteristics  
- **Multiple Data Handling**: Queues can manage multiple elements simultaneously.  
- **Fast Operations**: Accesses both ends swiftly without delay.  
- **Flexibility**: Adapts easily to dynamic data handling scenarios.

### Node Class for Linked List Queue

cpp
class Node {
public:
int data;
Node* next;
};

### Queue Class Implementation

cpp
class Queue {
private:
Node* front;
Node* rear;
public:
Queue() {
front = NULL;
rear = NULL;
}
void enqueue(int value);
void dequeue();
int getFront();
bool isEmpty();
void displayQueue();
};

### Queue Operations Implementation

cpp
// Function to enqueue a new element into the queue
void Queue::enqueue(int value) {
Node* newNode = new Node;
newNode->data = value;
newNode->next = NULL;
if (isEmpty()) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
cout << "Enqueued: " << value << endl;
}

// Function to dequeue the front element from the queue
void Queue::dequeue() {
if (isEmpty()) {
cout << "Queue is empty. Cannot dequeue." << endl; return; } Node* temp = front; front = front->next;
if (front == NULL) {
rear = NULL;
}
cout << "Dequeued: " << temp->data << endl;
delete temp;
}

// Function to get the front element of the queue
int Queue::getFront() {
if (isEmpty()) {
cout << "Queue is empty." << endl; return -1; } return front->data;
}

# Applications of Queues  
1. **Job Scheduling**: Manage tasks based on priority and execution order.  
2. **Print Spooling**: Organize print jobs following their order of arrival.  
3. **Breadth-First Search**: Graph traversal method leveraging queues.  
4. **Buffering**: Managing data flow during I/O operations.  
5. **Event Handling**: Queues handle actions based on sequence during event-driven programming.

## Circular Queues  
- A circular queue connects the last element back to the first element, allowing continuous enqueue and dequeue operations without needing to resize.
- **Advantages**: Efficient memory utilization and unsized continuous flow management of elements.  
- **Applications**: Task scheduling, CPU resource management, and I/O data buffering.

## Implementation of Circular Queue  
### Circular Queue Class Example

cpp
class CircularQueue {
private:
Node* front;
Node* rear;
public:
CircularQueue() {
front = NULL;
rear = NULL;
}
void enqueue(int value);
void dequeue();
int getFront();
bool isEmpty();
void displayQueue();
};

### Implementation of Enqueue and Dequeue in Circular Queue  
#### Enqueue Function

cpp
void CircularQueue::enqueue(int value) {
Node* newNode = new Node;
newNode->data = value;
if (isEmpty()) {
front = rear = newNode;
} else {
rear->next = newNode;
newNode->next = front;
rear = newNode;
}
cout << "Enqueued: " << value << endl;
}

#### Dequeue Function

cpp
void CircularQueue::dequeue() {
if (isEmpty()) {
cout << "Circular Queue is empty. Cannot dequeue." << endl; return; } Node* temp = front; if (front == rear) { front = rear = NULL; } else { front = front->next;
}
cout << "Dequeued: " << temp->data << endl;
delete temp;
}

# Dequeue (Double-Ended Queue)  
- **Definition**: A dequeue allows insertion and deletion of elements at both ends, combining properties of both stacks and queues.  

### Dequeue Operations  
1. **Insert Front**: Add an element at the front of the dequeue.  
2. **Delete Front**: Remove an element from the front.  
3. **Insert Rear**: Add an element at the rear.  
4. **Delete Rear**: Remove an element from the rear.  
5. **Get Front**: Return the front element without removing it.  
6. **Get Rear**: Return the rear element without removing it.  
7. **Size**: Return the count of elements in the dequeue.  
8. **Is Empty**: Check if the dequeue is empty.

### Dequeue Class Implementation Example

cpp
class Deque {
private:
Node* front;
Node* rear;
int count;
public:
Deque() {
front = NULL;
rear = NULL;
count = 0;
}
void insertFront(int value);
void insertRear(int value);
void deleteFront();
void deleteRear();
int getFront();
int getRear();
bool isEmpty();
int size();
void displayDeque();
};

### Operations Implementation Example  
#### Insert Front Function

cpp
void Deque::insertFront(int value) {
Node* newNode = new Node(value);
if (isEmpty()) {
front = rear = newNode;
} else {
newNode->next = front;
front = newNode;
}
count++;
cout << "Inserted: " << value << " at front." << endl;
}

#### Delete Front Function

cpp
void Deque::deleteFront() {
if (isEmpty()) {
cout << "Deque is empty. Cannot delete front." << endl; return; } Node* temp = front; front = front->next;
if (front == NULL) {
rear = NULL;
}
delete temp;
count--;
}
```

Summary

Stacks and Queues are fundamental data structures critical for efficient data handling in computer programming.
Understanding and implementing these structures provides a foundational skill set for aspiring computer scientists and programmers, particularly within C++.
This course emphasizes practical applications and theoretical understanding of problems that can be addressed using these data structures in software development.