C Data Structures: Stack, Binary Tree, Queue Implementations
C Stack Implementation: LIFO Data Structure
A stack is a fundamental linear data structure that follows the Last-In, First-Out (LIFO) principle. This means the last element added to the stack is the first one to be removed. Stacks are commonly used in various computing scenarios, such as function call management, expression evaluation, and undo/redo functionalities.
Key Stack Operations
- Push: Adds an element to the top of the stack. If the stack is full, it results in a “Stack Overflow” error.
- Pop: Removes the top element from the stack. If the stack is empty, it results in a “Stack Empty” error.
- Display: Shows all elements currently in the stack, typically from top to bottom.
C Code for Stack Implementation
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 3
typedef struct StackType {
int A[MAXSIZE];
int Top;
} STACK;
STACK S;
void InitStack() {
S.Top = -1;
}
void Push(int Num) {
if (S.Top == MAXSIZE - 1) {
printf("Stack Overflow\n");
} else {
S.Top++;
S.A[S.Top] = Num;
}
}
int Pop() {
int Num;
if (S.Top == -1) {
printf("Stack Empty\n");
return -1;
} else {
Num = S.A[S.Top];
S.Top--;
return Num;
}
}
void DisplayStack() {
int i;
if (S.Top < 0) {
printf("Stack is Empty\n");
} else {
printf("The elements in Stack are:\n");
for (i = S.Top; i >= 0; i--)
printf(" %d\n", S.A[i]);
printf("\n");
}
}
int Menu() {
int ch;
printf("\nStack Implementation\n");
printf("1. Push a number\n");
printf("2. Pop a number\n");
printf("3. Display the contents of the Stack\n");
printf("4. Exit\n");
printf("Enter Your Choice: ");
scanf("%d", &ch);
return ch;
}
int main() {
int choice, Num;
InitStack();
while (1) {
choice = Menu();
switch (choice) {
case 1:
printf("Enter the number to push: ");
scanf("%d", &Num);
Push(Num);
break;
case 2:
Num = Pop();
if (Num != -1)
printf("Popped number: %d\n", Num);
break;
case 3:
DisplayStack();
break;
case 4:
printf("Exiting the program.\n");
exit(0);
default:
printf("Invalid choice. Please try again.\n");
}
}
return 0;
}
Binary Tree Operations in C
A binary tree is a hierarchical data structure where each node has at most two children, referred to as the left child and the right child. Binary trees are widely used for efficient searching, sorting, and storing hierarchical data.
Core Binary Tree Functions
- Insertion: Adds a new node while maintaining the tree’s properties (e.g., for a Binary Search Tree, smaller values go to the left, larger to the right).
- Searching: Locates a specific value within the tree.
- Traversal: Methods to visit all nodes in a specific order:
- Preorder: Root, Left, Right
- Inorder: Left, Root, Right (results in sorted order for BST)
- Postorder: Left, Right, Root
- Min/Max Value: Finds the smallest or largest element in the tree.
- Leaf Node Check: Determines if a node has no children.
C Code for Binary Tree Implementation
#include <stdio.h>
#include <stdlib.h>
#include <memory.h> // Not strictly needed for this code, but was in original
typedef struct TreeType {
int Data;
struct TreeType *Left, *Right;
} TREENODE;
TREENODE *Root = NULL;
void menu();
void InsertTreeNode(int num);
int SearchNum(TREENODE *Root, int num);
void DisplayLeafNode(TREENODE *Root);
int IsLeafNode(TREENODE *Root, int num);
int MinNum(TREENODE *Root);
int MaxNum(TREENODE *Root);
void Preorder(TREENODE *Root);
void Postorder(TREENODE *Root);
void Inorder(TREENODE *Root);
int main() { // Changed from void main()
int n, num, num1, num2, ch;
menu();
while (1) {
printf("\nYour Choice : ");
scanf("%d", &ch);
printf("\n");
int i;
switch (ch) {
case 1:
printf("How many numbers ? ");
scanf("%d", &n);
for (i = 1; i <= n; i++) {
printf("%d : ", i);
scanf("%d", &num);
InsertTreeNode(num);
}
break;
case 2:
printf("Enter the number to be searched : ");
scanf("%d", &num1);
if (SearchNum(Root, num1))
printf("The number is present \n");
else
printf("The number is not present \n");
break;
case 3:
printf("Leaf Nodes: \n"); // Added descriptive text
DisplayLeafNode(Root);
break;
case 4:
printf("Enter the number : ");
scanf("%d", &num2);
if (IsLeafNode(Root, num2))
printf("%d is a leaf node \n", num2);
else
printf("%d is not a leaf node \n", num2);
break;
case 5:
if (Root == NULL) { // Handle empty tree case
printf("Tree is empty. Cannot find minimum.\n");
} else {
printf("The smallest number in the tree is %d\n", MinNum(Root));
}
break;
case 6:
if (Root == NULL) { // Handle empty tree case
printf("Tree is empty. Cannot find maximum.\n");
} else {
printf("The largest number in the tree is %d\n", MaxNum(Root));
}
break;
case 7:
printf("Preorder traversal \n");
Preorder(Root);
printf("\n");
break;
case 8:
printf("Postorder traversal \n");
Postorder(Root);
printf("\n");
break;
case 9:
printf("Inorder traversal \n");
Inorder(Root);
printf("\n");
break;
case 10:
printf("EXITING.......\n"); // Added newline
exit(0);
default:
printf("INVALID CHOICE \n");
}
}
return 0;
}
void menu() {
printf("----------- Binary Tree -----------\n");
printf("1. Insert numbers \n");
printf("2. Search a number \n"); // Corrected "num" to "number"
printf("3. Display leaf nodes \n"); // Corrected "node" to "nodes"
printf("4. Check if a number is a leaf node \n"); // Improved phrasing
printf("5. Return the smallest number \n");
printf("6. Return the largest number \n");
printf("7. Preorder traversal\n");
printf("8. Postorder traversal\n");
printf("9. Inorder traversal\n");
printf("10. Exit\n\n");
}
void InsertTreeNode(int num) {
TREENODE *Prev = NULL, *Curr, *Node;
Node = (TREENODE *)malloc(sizeof(TREENODE));
if (Node == NULL) { // Added malloc check
printf("Memory allocation failed for new node.\n");
return;
}
Node->Data = num;
Node->Left = Node->Right = NULL;
if (Root == NULL) {
Root = Node;
return;
}
Curr = Root;
while (Curr) {
Prev = Curr;
Curr = (num <= Curr->Data) ? Curr->Left : Curr->Right;
}
if (num < Prev->Data)
Prev->Left = Node;
else
Prev->Right = Node;
}
int SearchNum(TREENODE *Root, int num) {
TREENODE *Curr = Root;
if (Root == NULL) return 0; // Return 0 for not found if tree is empty
while (Curr) {
if (num == Curr->Data)
return 1;
else
Curr = (num < Curr->Data) ? Curr->Left : Curr->Right;
}
return 0; // Number not found
}
void DisplayLeafNode(TREENODE *Root) {
if (Root) {
if (Root->Left == NULL && Root->Right == NULL)
printf("Leaf Node : %d \n", Root->Data);
DisplayLeafNode(Root->Left);
DisplayLeafNode(Root->Right);
}
}
int IsLeafNode(TREENODE *Root, int num) {
TREENODE *Curr = Root;
if (Root == NULL) return 0; // Return 0 if tree is empty
while (Curr) {
if (num == Curr->Data)
return (Curr->Left == NULL && Curr->Right == NULL) ? 1 : 0;
else
Curr = (num < Curr->Data) ? Curr->Left : Curr->Right;
}
return 0; // Number not found
}
int MaxNum(TREENODE *Root) {
TREENODE *Curr = Root;
if (Root == NULL) return -1; // Or handle error appropriately, e.g., INT_MIN
while (Curr->Right)
Curr = Curr->Right;
return Curr->Data;
}
int MinNum(TREENODE *Root) {
TREENODE *Curr = Root;
if (Root == NULL) return -1; // Or handle error appropriately, e.g., INT_MAX
while (Curr->Left)
Curr = Curr->Left;
return Curr->Data;
}
void Preorder(TREENODE *Root) {
if (Root) {
printf("%d ", Root->Data);
Preorder(Root->Left);
Preorder(Root->Right);
}
}
void Postorder(TREENODE *Root) {
if (Root) {
Postorder(Root->Left);
Postorder(Root->Right);
printf("%d ", Root->Data);
}
}
void Inorder(TREENODE *Root) {
if (Root) {
Inorder(Root->Left);
printf("%d ", Root->Data);
Inorder(Root->Right);
}
}
Patient Queue Management System in C
A queue is a linear data structure that follows the First-In, First-Out (FIFO) principle. This means the first element added to the queue is the first one to be removed. Queues are essential for managing tasks in order, such as print job scheduling, CPU scheduling, and handling customer service calls.
Key Queue Operations
- Enqueue: Adds an element to the rear (end) of the queue.
- Dequeue: Removes an element from the front (beginning) of the queue.
- Display: Shows all elements currently in the queue, from front to rear.
C Code for Patient Queue Implementation
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
char PID[10];
char PName[50];
char Sickness[50];
} PATIENT;
typedef struct QueueNode {
PATIENT data;
struct QueueNode* next;
} QueueNode;
QueueNode* FRONT = NULL;
QueueNode* REAR = NULL;
int patientCount = 0;
// Function Prototypes
QueueNode* createNode(char PID[], char PName[], char Sickness[]);
void enqueue(char PID[], char PName[], char Sickness[]);
void dequeue();
void displayQueue(); // Added display function
int queueMenu(); // Added menu function
QueueNode* createNode(char PID[], char PName[], char Sickness[]) {
QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
if (!newNode) {
printf("\nMemory allocation failed!\n");
return NULL;
}
strcpy(newNode->data.PID, PID);
strcpy(newNode->data.PName, PName);
strcpy(newNode->data.Sickness, Sickness);
newNode->next = NULL;
return newNode;
}
void enqueue(char PID[], char PName[], char Sickness[]) {
QueueNode* newNode = createNode(PID, PName, Sickness);
if (!newNode) return;
if (REAR == NULL) { // Queue is empty
FRONT = REAR = newNode;
} else {
REAR->next = newNode;
REAR = newNode;
}
patientCount++;
printf("\nPatient %s (ID: %s) has been added to the queue.\n", PName, PID);
}
void dequeue() {
if (FRONT == NULL) {
printf("\nQueue is empty! No patient to remove.\n");
return;
}
QueueNode* temp = FRONT;
printf("\nPatient %s (ID: %s, Sickness: %s) has been removed from the queue.\n", temp->data.PName, temp->data.PID, temp->data.Sickness);
FRONT = FRONT->next;
if (FRONT == NULL) { // If queue becomes empty after dequeue
REAR = NULL;
}
free(temp);
patientCount--;
}
void displayQueue() {
if (FRONT == NULL) {
printf("\nQueue is empty. No patients to display.\n");
return;
}
QueueNode* current = FRONT;
printf("\n--- Current Patients in Queue (%d patients) ---\n", patientCount);
int i = 1;
while (current != NULL) {
printf("%d. ID: %s, Name: %s, Sickness: %s\n", i++, current->data.PID, current->data.PName, current->data.Sickness);
current = current->next;
}
printf("------------------------------------------------\n");
}
int queueMenu() {
int choice;
printf("\n--- Patient Queue System ---\n");
printf("1. Add New Patient (Enqueue)\n");
printf("2. Remove Patient (Dequeue)\n");
printf("3. Display All Patients\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
return choice;
}
int main() {
int choice;
char pid[10], pname[50], sickness[50];
while (1) {
choice = queueMenu();
switch (choice) {
case 1:
printf("Enter Patient ID: ");
scanf("%s", pid);
printf("Enter Patient Name: ");
scanf(" %[^
]%*c", pname); // Reads string with spaces
printf("Enter Sickness: ");
scanf(" %[^
]%*c", sickness);
enqueue(pid, pname, sickness);
break;
case 2:
dequeue();
break;
case 3:
displayQueue();
break;
case 4:
printf("Exiting Patient Queue System.\n");
exit(0);
default:
printf("Invalid choice. Please try again.\n");
}
}
return 0;
}