Stack: Difference between revisions

=={{header|jq}}==

For most purposes, jq's arrays can be used for stacks if needed, without much further ado.

However, since the present task requires the definition of special stack-oriented operations,

we shall start with the following definitions:

<syntaxhighlight lang=jq>

# create a Stack

def Stack: {stack: []};

# check an object is a Stack

def isStack:

type == "object" and has("stack") and (.stack|type) == "array";

def pop:

if .stack|length == 0 then "pop: stack is empty" | error

else {stack: .stack[1:], item: .stack[0]]

end;

def push($x):

.stack = [$x] + .stack | .item = null;

def size:

.stack | length;

def isEmpty:

size == 0;

</syntaxhighlight>

Depending on context, additional code to check for or to enforce

type discipline could be added, but is omitted for simplicity here.

If using the C implementation of jq, the function names could also

be prefixed with "Stack::" to distinguish them as stack-oriented

operations.

For some purposes, this approach may be sufficient, but it can easily

become cumbersome if a sequence of operations must be performed

while also producing outputs that reflect intermediate states.

Suppose for example that we wish to create a stack, push some value,

and then pop the stack, obtaining the popped value as the final

result. This could be accomplished by the pipe:

<syntaxhighlight lang=jq>

Stack | push(3) | pop | .item

</syntaxhighlight>

Now suppose we also wish to record the size of the stack after each of these three operations.

One way to do this would be to write:

<syntaxhighlight lang=jq>

Stack

| size, (push(3)

| size, (pop

| size, .item ))

</syntaxhighlight>

Unfortunately this approach is error-prone and can quickly become tedious, so

we introduce an "observer" function that can "observe" intermediate states following any operation.

With observer/2 as defined below, we can instead write:

<syntaxhighlight lang=jq>

null

| observe(Stack; size)

| observe(push(3); size)

| observe(pop; size)

| .emit, item

</syntaxhighlight>

The idea is that each call to `observe` updates the "emit" slot, so that

all the accumulated messages are available at any point in the pipeline.

<syntaxhighlight lang=jq>

# Input: an object

# Output: the updated object with .emit filled in from `update|emit`.

# `emit` may produce a stream of values, which need not be strings.

def observe(update; emit):

def s(stream): reduce stream as $_ (null;

if $_ == null then .

elif . == null then "\($_)"

else . + "\n\($_)"

end);

.emit as $x

| update

| .emit = s($x // null, emit);

</syntaxhighlight>