Simple queue structure with Structured Text (ST)

This example describes the simplest implementation of a queue. A queue is used when e.g. there are many packages on a conveyer belt, waiting for treatment by a machine in a large plant. The packages often require information like weight, receiver, size or content. Weight gives information about a package which must be saved in a queue, so that the information can follow the package through the plant. If the package has a readable bar code, it is not necessary to implement a queue, as the information about the package can be accessed from a shared database – i.e. the company’s production control system, often named:

Manufacturing Execution Systems (MES),

Manufacturing Information Systems (MIS) or

Warehouse Control System (WCS)

When implementing a queue, the objects must not change their place in the queue. However, if the packages provide e.g. a bar code or any kind of ID the packages may change their place in the queue.

An ARRAY should be created with the maximum length the queue is expected to be. Exceeding the required length of the ARRAY will take up memory unnecessarily and increase the execution time of the program.

A simple example is shown below where an ARRAY with 6 positions of the data type INT is created. Firstly, all the ARRAY positions are initialized to -1, because -1 can be used to check whether the position is empty:

PROGRAM MAIN
VAR
 Que: ARRAY[QueMin..QueMax] OF INT;
 n: INT; //Counter to FOR loop
END_VAR
VAR CONSTANT
 QueMax: INT := 5;
 QueMin: INT := 0;
END_VAR
FOR n:= QueMin TO QueMax DO
 Que[n]:= -1; //Init ARRAY
END_FOR;

The number above the ARRAY shows the position no:
ARRAY
Next: The ARRAY is now filled with three values (23, 35, 71). Values are inserted into the ARRAY from left to right, so that the value inserted first (with the value 23), is positioned all the way to the left, and the value inserted last is positioned all the way to the right on position 2 (with the value 71) as shown below
ARRAY

Inserting values in the queue can be carried out with this PLC code, where

the ARRAY is named Que:

Que [0] := 23;
Que [1] := 35;
Que [2] := 71;

The oldest value in the queue is 23, and is also the value which is taken out first. The simplest way to keep control of the queue, is to make sure that the oldest value is always positioned at position 0.

When the oldest value is taken out, all the values have to be moved one position to the left. The next value to be taken out is therefore 35.

FOR loop is used to move all the values one position to the left. The values are always moved left to not overwrite the values which already exist in the queue. The FOR loop must be executed one time less than the maximum positions in the ARRAY (array length), as shown in the example below:

FOR n:= 0 TO 5 - 1 DO
 Que [n]:= Que [n + 1];
END_FOR;

The ARRAY has 6 positions and the values have to be moved 5 times. Therefore, the FOR loop is executed 5 times as illustrated below:

1. Loop: Que [0]:= Que [0 + 1]
2. Loop: Que [1]:= Que [1 + 1]
3. Loop: Que [2]:= Que [2 + 1]
4. Loop: Que [3]:= Que [3 + 1]
5. Loop: Que [4]:= Que [4 + 1]

ARRAY

To keep track of which position the next value must be inserted at, a variable must be used called index or pointer. It starts by pointing at position 0, because the queue is empty. Every time a new value is inserted into the queue, the pointer is moved one position to the right, and if a value is removed (taken out) from the queue, the pointer have to be moved one position left.

The disadvantage of the simple queue is that a lot of time is spend executing the whole queue to ‘move’/’push’ the values every time a value is taken out. To solve this problem a circular buffer can be used which uses pointers instead of moving the values, every time a value is taken out or inserted.

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top