
Data Structure

This illustrates a data structure, a means of storing data within a program.

You may see other such structures in the Data Structures category.
 Illustration of FIFO behavior
Task

Create a queue data structure and demonstrate its operations.

(For implementations of queues, see the FIFO task.)



Operations:

   push       (aka enqueue) - add element
   pop         (aka dequeue) - pop first element
   empty     - return truth value when empty


See also

 Array
 Associative array: Creation, Iteration
 Collections
 Compound data type
 Doubly-linked list: Definition, Element definition, Element insertion, List Traversal, Element Removal
 Linked list
 Queue: Definition, Usage
 Set
 Singly-linked list: Element definition, Element insertion, List Traversal, Element Removal
 Stack


function deque(arr) {
    arr["start"] = 0
    arr["end"] = 0
}
 
function dequelen(arr) {
    return arr["end"] - arr["start"]
}
 
function empty(arr) {
    return dequelen(arr) == 0
}
 
function push(arr, elem) {
    arr[++arr["end"]] = elem
}
 
function pop(arr) {
    if (empty(arr)) {
        return
    }
    return arr[arr["end"]--]
}
 
function unshift(arr, elem) {
    arr[arr["start"]--] = elem
}
 
function shift(arr) {
    if (empty(arr)) {
        return
    }
    return arr[++arr["start"]]
}
 
function printdeque(arr,    i, sep) {
    printf("[")
    for (i = arr["start"] + 1; i <= arr["end"]; i++) {
        printf("%s%s", sep, arr[i])
        sep = ", "
    }
    printf("]\n")
}
 
BEGIN {
    deque(q)
    for (i = 1; i <= 10; i++) {
        push(q, i)
    }
    printdeque(q)
    for (i = 1; i <= 10; i++) {
        print shift(q)
    }
    printdeque(q)
}