Problem Question
To implement Linear Queue using array
Explanation of Problem
In this problem, the basic need is to have an array as the basic data structure. We would be making logics and attaching them to this basic array of ours that would make it a linear queue. So basically, this is the enhancement of the basic data structure array, to evolve it into a linear queue. A linear queue is identified by two main pointers, one is the head or the front of queue, and the other is the tail or the rear of the queue. The most important thing to understand about a linear queue is that, all the new data gets inserted at the rear, and any deletions are done at the front, just like a real life queue. Any new person joins a queue at the rear and the person to leave the queue is the person at the front. Just keeping these two restrictions on the addition and deletion to an array, we get the linear queue in place. But the major drawback of using a queue is that, removing elements from queue means orphaning the front of queue at each deletion. This means the space is not reusable.
NOTE: To keep the program simple, we have kept the size of the queue as 100. You can alter that as per your needs.
Code
/**@Title: Array_Queue.cpp*
*@Programming Paradigm: Procedural*
*@Language: C++*
*@Compiler: GNU GCC*
*@IDE: Code::Blocks 13.12*
*@Author: Rogue Coder*
*@URL: http://letsplaycoding.blogspot.com/*
*@Date: 04-07-2014*
*@Updated: 28-07-2014*
*/
#include <iostream>
int main()
{
int queueArray [ 100 ], choice = 0, frontOfQueue = 0, rearOfQueue = 0, elementOfQueue, i;
std::cout << "\aWelcome to Queue v1.1\n\aMade by Rogue Coder\n\nThis Queue can handle 100 elements.";
do
{
std::cout << "\nMenu:\n1. Enter\n2. Remove\n3. Display\n4. Exit\nYou Choice: ";
std::cin >> choice;
switch ( choice )
{
case 1:
if ( rearOfQueue >= 100 )
std::cout << "\n\a!!QUEUE OVERFLOW!!\n";
else
{
std::cout << "\nEnter the element to be fed into Queue: ";
std::cin >> elementOfQueue;
queueArray [ rearOfQueue++ ] = elementOfQueue;
}
break;
case 2:
if ( rearOfQueue <= frontOfQueue )
std::cout << "\n\a!!QUEUE UNDERFLOW!!\n";
else
{
std::cout << std::endl << queueArray [ frontOfQueue ] << " removed!";
frontOfQueue++;
}
break;
case 3:
std::cout << "\nQueue:\n";
if ( rearOfQueue == frontOfQueue )
std::cout << "\n\a!!QUEUE EMPTY!!\n";
else
for ( i = frontOfQueue; i < rearOfQueue; i++ )
std::cout << queueArray [ i ] << " ";
break;
case 4:
std::cout << "\n\n\aThank You for using Queue v1.1\n\aMade by Rogue Coder\n\aPress any key to exit";
std::cin.get();
break;
default:
std::cout << "\n\n\a\a!!!WRONG CHOICE!!!\n\n\a\a";
break;
}
}
while( choice != 4 );
return 0;
}
Explanation of Code
#include <iostream> -> The compiler calls the Preprocessor to include the IOSTREAM(Standard Input / Output Streams Library) header file into the program, thus letting the use of the Standard Input / Output Streams functions like std::cin and std::cout. As per C++11 specification, including <iostream> automatically includes also <ios>, <streambuf>, <istream>, <ostream> and <iosfwd>.
int main() -> The entry point of the program where the execution starts. This function has to be named main. As per the ANSI specification, the return type has to be int. Since the return type is specified as int in my program, I have to use a return statement at the end of my code. So I use return 0 since zero returned from a function, by convention, implies a correct execution of the program. The return values are used to debug the program.
std::cin (extern istream cin) -> Standard Input Stream, and object of class istream. It is generally used with the extraction operator (>>), though we can use member functions like get (cin.get()), read (cin.read()), etc. for the input. The use of extraction operator is much more popular due to the fact that it aids in getting formatted input.
std::cout (extern ostream cout) -> Standard Output Stream, and object of class ostream. It is generally used with the insertion operator (<<), though we can use member functions like write (cout.write()) for the output. The use of insertions operator is much more popular due to the fact that it aids in giving formatted output.
using namespace std; -> In modern IDEs, we have to explicitly write std::cout instead of cout to use the ostream cout object. Namespace std helps in easing off the pain of writing std:: again and again. Though make sure you are not trapped! The classes defined in std should not be redefined by you. So in case you want to define a class 'distance', you can't do so if you have used std namespace. Though you can define 'Distance' (capital D).
std::endl (ostream& endl (ostream& os)) -> This is a function which is used to insert a newline character and flush the stream. Because this function is a manipulator, it is designed to be used alone with no arguments in conjunction with the insertion (<<) operations on output streams.
int queueArray [ 100 ], choice = 0, frontOfQueue = 0, rearOfQueue = 0, elementOfQueue, i -> These are the variables that will be used to hold various values in the program. queueArray is the basic array which we will be using to implement Linear Queue. frontOfQueue and rearOfQueue represent the head and tail of the linear queue respectively. choice is used to store the user’s choice in the menu, and elementOfQueue represents the element we are working with, in case of insertion. i acts as the loop counter in the various for loops used through the program.
do {…}while( choice != 4 ); -> This is our main program loop in which the control is trapped until the user decides to exit the program with the choice 4.
if ( rearOfQueue >= 100 )
std::cout << "\n\a!!QUEUE OVERFLOW!!\n";
else
{
std::cout << "\nEnter the element to be fed into Queue: ";
std::cin >> elementOfQueue;
queueArray [ rearOfQueue++ ] = elementOfQueue;
} -> This is the insertion case. When the user enters the choice as ‘1’, the program first checks the value of variable rearOfQueue, which in case exceeds the highest possible for the array depending on its size, (99 in our case, since the size of the array is 100, and C++ uses 0 as starting index), the program prints a message “QUEUE OVERFLOW” denoting that the queue is full, else it prompts for user input, the element that the user wants to insert into the linear queue. This element is then stored in a variable, elementOfQueue and is appended at the end of the queue, using the statement, queueArray [ rearOfQueue++ ] = elementOfQueue;. The element gets inserted at the rear of the queue, and the pointer starts pointing to one position next (incremented).
if ( rearOfQueue <= frontOfQueue )
std::cout << "\n\a!!QUEUE UNDERFLOW!!\n";
else
{
std::cout << std::endl << queueArray [ frontOfQueue ] << " removed!";
frontOfQueue++;
} -> This is case 2 of our program, when the user wants to remove from the queue. In such a case the rearOfQueue is inspected. If it is pointing to frontOfQueue, i.e., the start of the queue, that means, the queue is empty, and hence a message is displayed, “QUEUE UNDERFLOW”, else the element at the front of the queue is displayed to the user as being removed(just for information), and frontOfQueue is incremented by one to point to the new front end of the queue. Actually removing from queue means orphaning the front element. This is the major drawback of queue data structure, that space not reusable.
std::cout << "\nQueue:\n";
if ( rearOfQueue == frontOfQueue )
std::cout << "\n\a!!QUEUE EMPTY!!\n";
else
for ( i = frontOfQueue; i < rearOfQueue; i++ )
std::cout << queueArray [ i ] << " "; -> This is the case 3 of our program. This is nothing but a simple array traversal logic. At first we inspect the rearOfQueue. If it is pointing to frontOfQueue, then it means the queue is empty, and the user is notified of that. Else, the control enters into a loop, where the loop traverses the queue fron front to the rear, printing each element on the user’s display.
exit(0); -> This function is used to exit the program with an error code as it's argument. '0' implies normal exit. Other values are used for debugging purposes.
std::cin.get() -> This statement is used to pause our program, until user presses a key. This function is not necessary in your program, I use it to see my outputs at a paused screen. If you use cmd to run your programs, you might not need this. If you use linux/unix you might not need this. Moreover, removing this line of code from this program, doesn't affect the functionality of the program.
Output(s)
Download Source Code
No comments:
Post a Comment
Need help?