AWK data structures

deque.awk

function deque_init(d) {d["+"] = d["-"] = 0}
function deque_is_empty(d) {return d["+"] == d["-"]}
function deque_push_back(d, val) {d[d["+"]++] = val}
function deque_push_front(d, val) {d[--d["-"]] = val}
function deque_back(d) {return d[d["+"] - 1]}
function deque_front(d) {return d[d["-"]]}
function deque_pop_back(d) {if(deque_is_empty(d)) {return NULL} else {i = --d["+"]; x = d[i]; delete d[i]; return x}} 
function deque_pop_front(d) {if(deque_is_empty(d)) {return NULL} else {i = d["-"]++; x = d[i]; delete d[i]; return x}} 
function deque_print(d){x="["; for (i=d["-"]; i<d["+"] - 1; i++) x = x d[i]", "; print x d[d["+"] - 1]"]; size: "d["+"] - d["-"] " [" d["-"] ", " d["+"] ")"}

stack.awk

function stack_is_empty(a) {return a[0] == 0}
function stack_top(a) {return a[a[0]]}
function stack_push(a, val) {a[++a[0]] = val}  # a[0] is a stack size
function stack_pop(a) {if(stack_is_empty(a)) {return NULL} else {i = a[0]--; x = a[i]; delete a[i]; return x}}