@OP
This short tutorial may be helpful for OP to understand how items are added, removed/retrieved, displayed etc. in a linear queue. This tutorial has received inspirations from Post-6, 9, 10, and an example of this book: C Complete Reference By: Herbert Schildt.
1. Linear Queue Definition
A Linear Queue is a list of “linear information”; where the item that is stored first is taken out first. It is a FIFO (First-in First-out). In Fig-1, we have a queue which can store five characters. The queue has been implemented using an array named myData[].
2. Understanding Linear Queue Principles and Operations by Diagrams
Fig-1 is a conceptual view of a queue with no elements inside it. The queue is empty. The
spos (storage position) variable always refers an empty location; where, we can insert/store a data/character item. The
rpos variable refers a location from where we take out/remove/retrieve the data item that was inserted first. The
rpos variable is also known as
head/front and the
rpos is known as
tail/rear. In an empty queue, spos and rpos variables have same numerical values.
Fig-2 shows a queue in which user has inserted a character A. Now, the spos variable has sifted to the right and has assumed value 1. It is pointing a location where next data item could be inserted. The rpos variable keeps the value 0 to indicate that the data item of this location must be taken out first.
Fig-3 show a queue where the user has inserted the character
B at the current empty position being pointed by spos variable. Now, the value of spos variable has increased to 2 and is pointing a new empty location.
Fig-4 shows the same queue with another data item - the character C.
Fig-5 shows the queue with the removal/retrieval of data item (character A) from location being pointed by rpos variable. Now, spos variable has assumed value 1 (spos++) to indicate that the next data item must be removed from location as referred by rpos.
Fig-6 shows the queue with the insertion of another data item - the character D.
Fig-7 shows the queue with the removal of the data item (character B) from location pointed by rpos variable. Now, rpos has assumed the value 2.
Fig-8 shows queue with the removal of data item - the character C. Now, the queue holds only one character - the D. If we add one more item in the queue, the queue will be Full and spos variable will assume 6. The following codes could check that the queue is full.
if(spos == 6)
{
Serial.println("Queue is Full!");
}
If we keep removing items from queue, then at one time rpos variable will also assume 6. This is the "Empty Condition" of queue. The following codes will check the emptiness of the queue:
if(rpos == spos)
{
Serial.println("Queue is EMpty!");
}
3. Assume that we have qstore() function to place a data item into the queue in an empty position. We have qretrieve() function to retrieve/remove a data item from the queue. The following Table-1 shows the effect of the operations we carried out on the queue of Step-2.
Action Meaning Contents of Queue Comments
qstore(‘A’) A is placed in queue A spos = 1, rpos = 0 (Fig-2)
qstore(‘B’) B is placed in queue AB spos = 2, rpos = 0 (Fig-3)
qstore(‘C’) C is placed in queue ABC spos = 3, rpos = 0 (Fig-4)
qretrieve() Take out A from queue BC spos = 3, rpos = 1 (Fig-5)
qstore(‘D’) D is place in queue BCD spos = 4, rpos = 1 (Fig-6)
qretrieve() Take out B fro queue CD spos = 4, rpos = 2 (Fig-7)
qretrieve() Take out C from queue D spos = 4, rpos = 3 (Fig-8)
4. A simple Sketch using C-codes to demonstrate the principles of queue operation of Step-2.
char myData[6] = ""; //all locations hold 0s (null charcaters)
byte spos = 0; //storage postion of item
byte rpos = 0; //retrieve position of item
char myChar[5];
char z;
void setup()
{
Serial.begin(9600);
Serial.println("Eneter (from InputBox) P to Place, R to Remove, D to Display, Q to Quit: ");
}
void loop()
{
byte y = Serial.available();
if (y != 0)
{
byte m = Serial.readBytesUntil('\n', myChar, 5);
myChar[m] = '\0'; //insert null character
z = myChar[0];
memset(myChar, 0, 5);
}
switch (z)
{
case 'P':
{
Serial.println("Placing an item in queue: ");
z = NULL;
qstore('A');
break;
}
case 'R':
{
qretrieve();
break;
}
case 'D':
{
Display();
z = NULL;
break;
}
case 'Q':
{
break;
}
}
}
void qstore(char x)
{
myData[spos] = x;
spos++;
}
void qretrieve()
{
}
void Display()
{
Serial.print("Displaying the contents of queue: ");
Serial.println(myData);
rpos++;
}
5. Upload the sketch of Step-4 in UNO.
6. Press RESET button of UNO.
7. Follow the menu of Serial Monitor.
(1) Choose Newline option for the Line ending tab of Serial Monitor.
(2) Enter P (to place an item in the queue)) in the InputBox and then click on Send button,
(3) Enter A (the item to be placed in queue) in the InputBox and then click on Send button.
(4) Enter D (to display contents of queue) in the InputBox and then click on Send button.
(5) Check that the OutputBox of Serial Monitor shows messages as in Fig-9.
Figure-9:
8. Study the program codes in consultation with the diagrams of Step-2.
9. Add C-codes with the sketch of Step-4 to implement full queue operations of Step-3.
char myData[6] = ""; //all locations hold 0s (null charcaters)
byte spos = 0; //storage postion of item
byte rpos = 0; //retrieve position of item
char myChar[5];
char z;
void setup()
{
Serial.begin(9600);
Serial.println("Eneter (from InputBox) P to Place, R to Remove, D to Display, Q to Quit: ");
}
void loop()
{
z = getChar(); //get a single Newline terminated character from Serial Monitor
switch (z)
{
case 'P':
{
Serial.print("Placing an item in queue: ");
z = NULL;
char p = getChar();
Serial.println(p);
qstore(p);
break;
}
case 'R':
{
qretrieve();
break;
}
case 'D':
{
Display();
z = NULL;
break;
}
case 'Q':
{
break;
}
}
}
void qstore(char x)
{
if(spos == 5)
{
Serial.println("Queue is Full!");
return;
}
myData[spos] = x;
spos++;
}
void qretrieve()
{
Serial.println("Removeing/Retrieveing first item from queue.");
if(rpos == spos)
{
Serial.print("Queue is Empty!");
return;
}
(void)myData[rpos]; //retrieve and discard
myData[rpos] = ' ';
rpos++; //move pointer to the next position
}
void Display()
{
Serial.print("Displaying the contents of queue: ");
Serial.println(myData);
}
char getChar() //get a single Newline terminated character from Serial Monitor
{
while (1)
{
byte y = Serial.available();
if (y != 0)
{
byte m = Serial.readBytesUntil('\n', myChar, 5);
myChar[m] = '\0'; //insert null character
z = myChar[0];
memset(myChar, 0, 5);
return (z);
}
}
}
Figure-10:
10. Create your own sketch to make a queue of your requirements.
11. Re-write C-codes of Step-4, 9 using C++ codes to realize advantage of C++ codes.
