String Operations and Queue Data Structures Explained
String Storage and Memory Representation
A string is a collection of characters stored together in memory. Strings are used to store names, words, sentences, and other text data in computer systems. In programming languages like C, a string is stored as an array of characters and ends with a special null character '\0'.
Example of String: char name[] = "ROHIT";
In memory, the string is stored as:
| R | O | H | I | T | \0 |
Here, \0 represents the end of the string.
Methods of String Storage
1. Fixed Length Storage
In this method, a fixed amount of memory is reserved for the string.
- Advantages: Simple to implement, easy access to characters.
- Disadvantages: Memory wastage may occur, large strings cannot fit in small fixed spaces.
2. Variable Length Storage
In this method, memory is allocated according to the size of the string.
- Advantages: Better memory utilization, can store strings of different lengths.
- Disadvantages: Implementation is more complex, memory management becomes difficult.
Applications of Strings
- Storing names and messages
- Text processing
- Searching operations
- Database management systems
Advantages and Disadvantages of String Storage
- Advantages: Easy handling of text data, efficient data representation, useful in many applications.
- Disadvantages: Extra memory is needed for the null character, string operations may take more processing time.
String Length Operation
The length operation is used to calculate the total number of characters present in a string. In C language, the null character '\0' is not included while counting the length of the string. The length operation is very important because many string operations depend upon the size of the string.
Example: String = “COMPUTER”, Length of string = 8
Algorithm for Finding String Length
- Step 1: Start
- Step 2: Read the string
- Step 3: Initialize COUNT = 0
- Step 4: Check each character of the string
- Step 5: Repeat until null character
'\0'occurs: COUNT = COUNT + 1 - Step 6: Print COUNT
- Step 7: Stop
Pros and Cons of Length Operation
- Advantages: Helps in determining string size, useful in many string operations, easy to implement.
- Disadvantages: Takes extra time for very large strings, each character must be checked individually.
- Applications: String comparison, memory allocation, text processing.
Substring Operation on Strings
A substring is a part of the original string obtained by selecting some characters from it. Substring operation is used when only a specific portion of the string is required.
Example: Main String = “COMPUTER”, Substring = “PUT”. Here, “PUT” is a substring of “COMPUTER”.
Algorithm for Substring Extraction
- Step 1: Start
- Step 2: Read the main string
- Step 3: Enter starting position and required length
- Step 4: Copy characters from main string into another string
- Step 5: Store null character at the end
- Step 6: Print substring
- Step 7: Stop
Pros and Cons of Substring Operation
- Advantages: Helps in extracting useful information, useful in text editing and searching, easy to perform on strings.
- Disadvantages: Additional memory may be required, processing becomes slower for long strings.
- Applications: Text editors, search operations, database systems.
Insertion Operation on Strings
Insertion means adding a new character or substring into an existing string at a specific position. To perform insertion, characters are shifted towards the right side to create empty space.
Example: String = “ABEF”, Insert = “CD”, Result = “ABCDEF”
Algorithm for String Insertion
- Step 1: Start
- Step 2: Read the original string
- Step 3: Enter the position for insertion
- Step 4: Enter new substring or character
- Step 5: Shift existing characters towards the right
- Step 6: Insert new substring at required position
- Step 7: Print updated string
- Step 8: Stop
Pros and Cons of Insertion
- Advantages: New data can be added easily, useful in updating text, important for text processing applications.
- Disadvantages: Shifting characters takes extra time, performance decreases for large strings.
- Applications: Text editors, data modification, document processing.
Deletion Operation on Strings
Deletion means removing one or more characters from a string. After deletion, remaining characters are shifted towards the left side. Deletion operation is useful for removing unwanted data from strings.
Example: String = “COMPUTER”, Delete = “PUT”, Result = “COMER”
Algorithm for String Deletion
- Step 1: Start
- Step 2: Read the string
- Step 3: Enter position and number of characters to delete
- Step 4: Shift remaining characters towards the left
- Step 5: Adjust the end of string with null character
- Step 6: Print updated string
- Step 7: Stop
Pros and Cons of Deletion
- Advantages: Removes unwanted characters easily, helps in editing strings, useful in data updating.
- Disadvantages: Character shifting increases processing time, less efficient for large strings.
- Applications: Text editing, removing invalid data, database updating.
Replacement Operation on Strings
Replacement operation means replacing an old substring or character with a new substring or character. It is commonly used in text editing and data modification applications.
Example: String = “GOOD”, Replace “GOOD” with “BEST”, Result = “BEST”
Algorithm for String Replacement
- Step 1: Start
- Step 2: Read the original string
- Step 3: Enter old substring and new substring
- Step 4: Search old substring in the main string
- Step 5: Replace old substring with new substring
- Step 6: Print updated string
- Step 7: Stop
Pros and Cons of Replacement
- Advantages: Makes modification of strings easy, useful in editing and updating data, saves time in manual correction.
- Disadvantages: Searching and replacing take extra processing time, difficult for very large strings.
- Applications: Text editors, data correction, document processing.
Pattern Matching in Strings
Pattern matching is the process of searching for a particular pattern or substring inside the main string. It checks whether the required pattern exists in the string or not.
Example: Main String = “DATA STRUCTURE”, Pattern = “STRUCT”. The pattern is found inside the main string.
Algorithm for Pattern Matching
- Step 1: Start
- Step 2: Read main string and pattern
- Step 3: Compare pattern characters with string characters
- Step 4: If all characters match, display position
- Step 5: Otherwise continue searching
- Step 6: Repeat until end of string
- Step 7: Stop
Pros and Cons of Pattern Matching
- Advantages: Useful in searching operations, used in search engines and text editors, helps in fast information retrieval.
- Disadvantages: Searching large strings takes more time, complex algorithms may be difficult to implement.
- Applications: Search engines, text processing, compiler design.
Simple Queue Data Structure
A Queue is a linear data structure in which insertion of elements is done from one end called REAR and deletion of elements is done from another end called FRONT. A queue follows the principle of FIFO (First In First Out). It means the element inserted first will be removed first. A queue works similar to a line of people standing for tickets where the first person in line leaves first.
Representation of Simple Queue
A simple queue can be represented using:
- Arrays
- Linked Lists
Two pointers are used in a queue:
- FRONT: points to the first element
- REAR: points to the last element
Operations on Simple Queue
1. Insertion (ENQUEUE)
Insertion means adding a new element at the REAR end of the queue.
Algorithm for ENQUEUE:
- Step 1: Check if queue is full
- Step 2: If REAR = MAX – 1, print “Overflow”
- Step 3: Otherwise increment REAR by 1
- Step 4: Insert element at QUEUE[REAR]
- Step 5: If FRONT = -1, set FRONT = 0
- Step 6: Stop
2. Deletion (DEQUEUE)
Deletion means removing an element from the FRONT end of the queue.
Algorithm for DEQUEUE:
- Step 1: Check if queue is empty
- Step 2: If FRONT = -1 or FRONT > REAR, print “Underflow”
- Step 3: Otherwise delete element from FRONT
- Step 4: Increment FRONT by 1
- Step 5: Stop
Example of Queue: Suppose queue elements are: 10, 20, 30, 40. If one element is deleted, then 10 will be removed first because the queue follows the FIFO principle. Remaining queue: 20, 30, 40.
Pros, Cons, and Applications
- Advantages: Easy insertion and deletion operations, follows FIFO order properly, useful in scheduling and buffering.
- Disadvantages: Fixed size in arrays, memory wastage may occur in array implementation, difficult to utilize free spaces efficiently.
- Applications: CPU scheduling, data buffering, printer scheduling, ticket reservation systems.
Priority Queue Data Structure
A Priority Queue is a special type of queue in which each element is assigned a priority. Elements are deleted according to their priority instead of their insertion order. In a priority queue, the element with higher priority is removed first. If two elements have the same priority, then they are processed according to the FIFO principle.
Types of Priority Queue
- 1. Ascending Priority Queue: In this type, the element with the smaller value priority is deleted first.
- 2. Descending Priority Queue: In this type, the element with the higher value priority is deleted first.
Representation of Priority Queue
Priority queues can be represented using arrays or linked lists. Each element contains:
- Data element
- Priority value
Operations on Priority Queue
1. Insertion (ENQUEUE)
Insertion means adding an element according to its priority.
Algorithm for Insertion:
- Step 1: Start
- Step 2: Check whether queue is full
- Step 3: Enter element and its priority
- Step 4: Insert element at proper position according to priority
- Step 5: Stop
2. Deletion (DEQUEUE)
Deletion removes the element having the highest priority.
Algorithm for Deletion:
- Step 1: Start
- Step 2: Check whether queue is empty
- Step 3: Delete highest priority element from FRONT
- Step 4: Adjust queue positions
- Step 5: Stop
Example of Priority Queue: Suppose elements are inserted with priorities: A (3), B (1), C (2). Deletion order will be: B → C → A because the smaller priority number has higher priority.
Pros and Cons of Priority Queue
- Advantages: Important tasks are processed first, efficient for scheduling operations, useful in operating systems and networking.
- Disadvantages: Implementation is more complex than a simple queue, insertion operation may take more time, extra memory may be required.