[EN] Queue data structure with array and Singly Linked List.

This article describes Queue Data Structures previously written in the Python Queue Data Structure article and is frequently used with the MicroPython example, but this article is written in C via Arduino IDE to use with microcontroller board LGT8F328P, SAM-D21, ESP8266, ESP32 and ESP32-S2 as shown in Figure 1 by using an example of the array structure and a single link list as a queued data structure. This article is probably the last article on JarutEx.

Queue data structure

A queue is a finite-member data structure that operates according to FIFO (First-in-First-out) principles. It can be used in a variety of applications, for example as storage and when the data is full but needs to be inserted new data we must remove the old data number 1 that was inserted into it which corresponds to the principle of FIFO or the principle of whoever comes first, gets out first, etc.

There are two components of a queue data structure:

1. Storage node which can choose to use an array of data structures as storage or a linked list data structure.
2. A set of instructions for using data structures under queue operations.

There are two commands for using the queue:

• push(X) For importing data x to store in the queue as shown in Figure 2.
• export_value = pop() to remove the first data in the queue as shown in Figure 3.

There are two working methods for importing:

1. Import queued data that can still be stored.
2. Import data to a queue with a defined full member count, resulting in Queue Overflow

There are two types of ejection cases as well:

1. In the case of removing from the queue where data exists
2. The case of exporting data with an empty queue resulting in a problem called Queue Underflow.

Algorithm of push(x)

To import data into a queue data structure, follow these steps:

1. Check the number of members
2. If there are already full members, report Queue Overflow and exit.
3. Put the data to the end of the queue.
4. Increase the number of members in the queue counter by 1 value.

Algorithm of pop()

There are steps for removing data from the queue:

1. Check the number of members in the queue.
2. If the number of members is 0, report Queue Underflow and exit.
3. Remember the first member fee.
4. Decrease the number of stack members counter by 1 value.
5. Move the next member to replace the one that was removed.
6. Return the member remembered from item 3.

Row-based queues

Using queue data structures to store data in array variables, you can create array variables and a variable to store the number of members stored in the queue. Then write a function to perform push() and pop() functions as follows.

Data

The variable to store data and the number of members is written as follows.

const uint8_t queMaxElm = 5;
uint8_t queData[5];
uint8_t queElmCounter = 0;

bool queInit() {
  queElmCounter = 0;
  return true;
}

push

Code

bool quePush( uint8_t x ) {
  if (queElmCounter == queMaxElm) {
    return false;
  }
  queData[queElmCounter] = x;
  queElmCounter += 1;
  return true;
}

pop

Code

bool quePop( uint8_t& x ) {
  if (queElmCounter == 0) {
    return false;
  }
  x = queData[0];
  queElmCounter -= 1;
  if (queElmCounter > 0) {
    for (int i = 0; i < queElmCounter; i++) {
      queData[i] = queData[i + 1];
    }
  }
  return true;
}

Example Code

Here’s an example program to test the functionality of a queue: The sample result is as shown in Figure 4.

const uint8_t queMaxElm = 5;
uint8_t queData[5];
uint8_t queElmCounter = 0;

bool queInit() {
  queElmCounter = 0;
  return true;
}

bool quePush( uint8_t x ) {
  if (queElmCounter == queMaxElm) {
    return false;
  }
  queData[queElmCounter] = x;
  queElmCounter += 1;
  return true;
}

bool quePop( uint8_t& x ) {
  if (queElmCounter == 0) {
    return false;
  }
  x = queData[0];
  queElmCounter -= 1;
  if (queElmCounter > 0) {
    for (int i = 0; i < queElmCounter; i++) {
      queData[i] = queData[i + 1];
    }
  }
  return true;
}

void queShow() {
  Serial.print("Queue data=[ ");
  for (int i = 0; i < queElmCounter; i++) {
    Serial.print(queData[i]);
    Serial.print(" ");
  }
  Serial.println("]");
}

void queDemo() {
  queInit();
  queShow();
  for (int i = 0; i < 6; i++) {
    Serial.print("push(");
    Serial.print(i);
    Serial.print(") ... ");
    if (quePush(i)) {
      Serial.println("done.");
      queShow();
    } else {
      Serial.println(" Queue overflow!");
    }
  }
  uint8_t data;
  for (int i = 0; i < 6; i++) {
    Serial.print("pop() ... ");
    if (quePop(data)) {
      Serial.println(data);
      queShow();
    } else {
      Serial.println(" Queue underflow!");
    }
  }
}

void setup() {
  Serial.begin( 9600 );

}

void loop() {
  queDemo();
  delay(30000);
}

Single-List Link Queue

The case of using a single link list instead of an array saves the program at startup because memory is not required to pre-empt the program before it starts. However, there may be problems with the number of members in the queue being less than intended when there is insufficient memory for the reservation. However, experimenting with building a stack using a single link list is another option for practicing programming and experimenting with a different function from the array approach.

Data

The data or variables for a queue like this are the same as for creating a single link list: the node structure must be created. There is a pointer variable to the first node, the last node, and has reserved and unreserved for adding and removing nodes:

const uint8_t queMaxElm = 5;
struct queNode {
  uint8_t data;
  queNode * next;
};

queNode * queRoot;
queNode * queCurrentNode;
queNode * queNewNode;
uint8_t queElmCounter = 0;

bool queInit() {
  queElmCounter = 0;
  queRoot = NULL;
  queCurrentNode = NULL;
  queNewNode = NULL;
  return true;
}

push

Push() or adding a node has more steps using arrays:

1. Push() or adding a node has more steps using arrays.
2. Memory Reserve If there is not enough, exit the function.
3. Put the x value in the data.
4. If it’s the first node, define queRoot and queCurrentNode. Points to the node created from clause 2.
5. Increase the number of members counter

bool quePush( uint8_t x ) {
  if (queElmCounter == queMaxElm) {
    return false;
  }
  queNewNode = (queNode*)malloc( sizeof( queNode ) );
  if (queNewNode == NULL) {
    return false;
  }
  queNewNode->next = NULL;
  queNewNode->data = x;
  if (queElmCounter == 0) {
    queRoot = queNewNode;
  } else {
    queCurrentNode->next = queNewNode;
  }
  queCurrentNode = queNewNode;
  queElmCounter += 1;
  return true;
}

pop

The pop() procedure works as follows.

1. If the number of members is 0, exit the function.
2. If there is only one node, delete the first node and set queRoot and queCurrentNode to NULL.
3. Otherwise, delete the first node and move queRoot to the next node adjacent to the first node removed.
4. Decrease the number of members of the node by 1.

bool quePop( uint8_t& x ) {
  if (queElmCounter == 0) {
    return false;
  }

  if (queRoot == queCurrentNode) {
    x = queRoot->data;
    free(queRoot);
    queRoot = NULL;
    queCurrentNode = NULL;
  } else {
    queNode * p = queRoot;
    x = p->data;
    queRoot = p->next;
    free(p);
  }
  queElmCounter -= 1;
  return true;
}

Example Code

Here is an example program for using a single link list as a programming queue data structure: The result of the work is the same as using the array in Figure 4.

const uint8_t queMaxElm = 5;
struct queNode {
  uint8_t data;
  queNode * next;
};

queNode * queRoot;
queNode * queCurrentNode;
queNode * queNewNode;
uint8_t queElmCounter = 0;

bool queInit() {
  queElmCounter = 0;
  queRoot = NULL;
  queCurrentNode = NULL;
  queNewNode = NULL;
  return true;
}

bool quePush( uint8_t x ) {
  if (queElmCounter == queMaxElm) {
    return false;
  }
  queNewNode = (queNode*)malloc( sizeof( queNode ) );
  if (queNewNode == NULL) {
    return false;
  }
  queNewNode->next = NULL;
  queNewNode->data = x;
  if (queElmCounter == 0) {
    queRoot = queNewNode;
  } else {
    queCurrentNode->next = queNewNode;
  }
  queCurrentNode = queNewNode;
  queElmCounter += 1;
  return true;
}

bool quePop( uint8_t& x ) {
  if (queElmCounter == 0) {
    return false;
  }

  if (queRoot == queCurrentNode) {
    x = queRoot->data;
    free(queRoot);
    queRoot = NULL;
    queCurrentNode = NULL;
  } else {
    queNode * p = queRoot;
    x = p->data;
    queRoot = p->next;
    free(p);
  }
  queElmCounter -= 1;
  return true;
}

void queShow() {
  Serial.print("Queue data=[ ");
  queNode * currentNode = queRoot;
  while (currentNode) {
    Serial.print(currentNode->data);
    Serial.print(" ");
    currentNode = currentNode->next;
  }
  Serial.println("]");
}

void queDemo() {
  queInit();
  queShow();
  for (int i = 0; i < 6; i++) {
    Serial.print("push(");
    Serial.print(i);
    Serial.print(") ... ");
    if (quePush(i)) {
      Serial.println("done.");
      queShow();
    } else {
      Serial.println(" Queue overflow! or not enough memory!");
    }
  }
  uint8_t data;
  for (int i = 0; i < 6; i++) {
    Serial.print("pop() ... ");
    if (quePop(data)) {
      Serial.println(data);
      queShow();
    } else {
      Serial.println(" Queue underflow!");
    }
  }
}

void setup() {
  Serial.begin( 9600 );

}

void loop() {
  queDemo();
  delay(30000);
}

Conclusion

In this article, you will find that programming for queue data structures is similar to stacked data structures but differs in the order in which the data is extracted. Because of the queued data structure, remove the first imported data set while in the stack structure, remove the last imported data first. We hope that readers will see either a static or array-based approach to data storage and a dynamic or application of a single-link list structure instead of a single-link list structure. Use arrays that have different advantages and disadvantages. As for the choice, it all depends on the situation and the necessity of the work is the reason for making the decision. Finally, have fun with programming. JarutEx maybe stops here.

(C) 2022, By Jarut Busarathid and Danai Jedsadathitikul
Updated 2022-03-08