1. Introduction

Introduction to Queues

A Queue is a FIFO (First-In, First-Out) data structure, as opposed to a LIFO (Last-In, First-Out) structure such as a stack. A queue is like a list, or a line. The first one to get in line is the first to get out of line. The items get removed from the top of the queue and entered at the bottom. As in a stack, when something is taken off the top of a queue it is removed from the queue (except when the preservation prefix operator is used -- see below).

All objects in Q-BAL are queues or functions. For now, we will just deal with queues of numbers (see below for functions and compound data types). A queue of numbers is a simple FIFO structure of integers (Q-BAL has no floating point capacity as yet).

Declaring Queues of Numbers

An object is declared by a declaration statement, as follows:

Q queue_name

This declares a queue of numbers named queue_name. The name is an alphanumeric sequence which can include letters, numbers, and underscores, but cannot begin with a number. There is another part to the declaration: the type. For now, the only type we'll be using is "Q", meaning a queue of numbers.


A queue may be initialized to a certain list of numbers. This is done using the = initialization operator and the { , } literal queue operators. An example follows:

Q squares = {1,4,9,16,25}

The first number inside the { , } comes at the top of the queue and the last comes at the bottom. Literal queues can also be used in expressions and assignments (see below).


The attachment operators

All non-declarations in Q-BAL are assignments or attachments. That is, all statements that do not create a queue or function are classed as assignments or attachments and are thus built around the assignment operator, =, or one of the two attachment operators, -> and <-. We will discuss attachment first.

Note: Unicode character /u2192 (and /u2090 the other way) is a nice arrow. Unfortunately most computers are still running on ASCII or ANSI so we are unable to type unicode characters in our programs. :( Hence we use the two characters ->.

Of the two attachment operators, the second is identical to the first except with reversed arguments. That is to say, x -> y is equivalent to y <- x.

It is a good idea to be consistent in which you use, unless for some reason the clarity is improved by switching, or you are trying to confuse people. The queue from which the arrow points is known as the source, and the one to which it points is known as the destination. Attachment is also known as appending, or "sticking on the bottom."

What they do

What the first attachment does is to pop the top of x and append it to the bottom of y. That is, this code:

Q x = {1,2,3}
Q y = {4,5,6}
x -> y
y -> x

will end up with x = {2,3,4} and y = {5,6,1}.


Arithmetic may be performed on the number after it is popped and before it is attached. More than one number may be popped off the same or different queues and arithmetic may be performed on them. Reading from left to right in an expression, numbers are popped off queues in the order they appear. This is important if more than one number is to be popped off one queue in an expression. One queue can appear on both the source and destination sides, such as in the attachment x + 1 -> x, which serves as an increment if x is a one-element queue.

The arithmetic operators are +, -, /, \, |, and ^. Of these, + adds, - subtracts, / finds the quotient, | finds the remainder, \ multiplies (the opposite of division, naturally), and ^ exponentiates. Remember, these are all integer operators. The parenthesis operators, ( and ), are used to separate operations and override the natural order of operations (which is ^ \ / | + -). They are also often used for clarity.


The traditional logical operators may also be applied. They return 1 if true and 0 if not true. They are used in program control (see program counter, below). They are ==, <, >, <= or =<, >= or =>, !=, and ! (logical NOT turns nonzero into zero and zero into one).


The assignment sets one queue equal to another. It does not modify the source queue (the one on the right), but the destination queue is completely overwritten by the source queue. An example will illustrate:

Q x = {1,2,3}
Q y = {4,6}
y = x

This example produces x = {1,2,3} and y = {1,2,3}. As it shows, the assignment operator does not care about how many elements are in the destination queue. There is no "flipped" form of the assignment operator as there is with the attachment operators; the left is always the destination and the right is always the source.

The Basic Prefix Operators

Prefix operators are an important part of Q-BAL. For the most part they control access to a queue or force different types of access to a queue. They have higher precedence than any other operators and are evaluated from inside to outside.

The Preservation Operator (*)

The preservation operator returns the top element of a queue without that element being removed from the queue.

The Number Operator (#)

The number operator returns the number of elements in the queue it is applied to. It is often used by functions to determine if they have enough arguments to execute (see functions, below).

Other Prefix Operators

The &, @, ~, and : operators really only have meaning when used with functions and will be discussed in that section. The $ and % operators only have meaning when used with different data types and will be discussed in that section.

The Use of the Null

In either an attachment or assignment, either the source or the destination (or theoretically both, but this would be useless) may be left blank. This is called the "null queue." The null queue is never modified and is considered to have no elements. Here are the possible combinations:

x ->
-> x
x =
= x

Of these, the fourth is the only one with no use whatever. The first pops an element from x and discards it, and the third erases x completely (i.e. makes it a null queue.). The second does nothing to x if it is a queue, but if x is a function it makes the function's code execute without storing anything in the input queue (see functions, below).


A comment is, as in any programming language, a statement ignored by the compiler/interpreter. The sole function of comments is to make the program more readable to the programmer and anyone else. In Q-BAL all characters between a backquote (`) and carriage return/linefeed are considered comments and ignored by the compiler or interpreter.

Compiler/Interpreter Directives

As in other languages (especially C) the programmer in Q-BAL can instruct the compiler or interpreter in certain ways. In Q-BAL any line beginning in a period (.) is considered a directive. There must be one letter after the period designating what type of directive it is, then a space and any parameters required by the directives. At the time this is being written there are only three directives:

.I "included.qbl"
.P ;-1 -> ;
.M print 'out?

The first tells the compiler/interpreter to include a specified file at that point. The pathname can be relative or absolute. The second changes the end-of-line statment from the default ;+1 -> ; to anything the programmer specifies. (We'll find out about ; and program control later.) The third creates a macro, like C's #define statement. Macros and other predefined objects are generally made with ALL CAPS.

Next: Input and Output