Write a script to demonstrate Stack operations like below:

`push($n)`

– add`$n`

to the stack`pop()`

– remove the top element`top()`

– get the top element`min()`

– return the minimum element

This challenge starts off normal; `push`

, `pop`

, and `top`

are regular stack operation, but it takes an unexpected twist at the end. `min`

is not a regular stack operation. In fact, it’s not a stack operation at all. If you need a datastructure where you need to find the minimum value, a stack is a horrible choice. You ought to be using a heap, or a balanced tree instead.

## Solutions

For all solutions, we let `top`

and `min`

print an error message if the are called on an empty stack. `pop`

on an empty stack is a no-op.

Our input consists of a set of commands, one command per line. `pop`

, `top`

and `min`

won’t take arguments, while `push`

will be followed by a space, and the number to be pushed. There won’t be parenthesis in the input.

### Perl

Perl has `push`

and `pop`

operations, which act on arrays, where the last element of the array acts as the top of the stack. For the `min`

operation, we will use the `min`

function from `List::Util`

module:

```
use List::Util 'min';
my $ERROR = "Stack is empty";
my @stack;
while (<>) {
if (/^push\s+(.*)/) {push @stack => $1}
if (/^pop/) {pop @stack}
if (/^top/) {say $stack [-1] // $ERROR}
if (/^min/) {say min (@stack) // $ERROR}
}
```

Find the complete program on GitHub.

### Node.js

Node.js has `push`

and `pop`

methods, which, just like in Perl, act on arrays. The last element of the array acts as the top of the stack. For the `min`

operator, we make use of `Math . min`

.

We iterate over the input, and process each line as follows (at this point, `command`

contains the line of input, stripped from its newline):

```
let stack = [];
let ERROR = "Stack is empty";
{
let [m, operator, value] =
command . match (/^(push|pop|top|min)\s*(.*)$/);
if (operator == "push") {stack . push (+value)}
if (operator == "pop") {stack . pop ()}
if (operator == "top") {
console . log (stack . length ? stack [stack . length - 1] : ERROR)
}
if (operator == "min") {
console . log (stack . length ? Math . min (... stack) : ERROR)
}
}
```

Note the use of the unary `+`

operator, in `+value`

. Since we have parsed `value`

out of the string, `value`

is a string. If we take the minimum of a set of strings, we get the first string in alphabetic order — which is not what we want. Unary plus returns a numerical value, so we’re pushing numbers on the stack, and get the smallest number when using `min`

.

Node.js does not flatten arrays when passed into functions, but `Math . min`

takes a list, not an array. Therefore, we use the *spread* (`...`

) operator, which, when applied on an array, returns a list with the array elements.

Find the complete program on GitHub.

### Python

Just like Perl and Node.js Python does have a push method, although they call it `append`

. A `pop`

method exists as well.

Python does have a `min`

buildin, which can take an array as argument.

This leads to the following program:

```
import fileinput
stack = []
error = "Stack is empty"
for line in fileinput . input ():
chunks = line . split ()
command = chunks [0]
if command == "push":
stack . append (int (chunks [1]))
if command == "pop":
if len (stack):
stack . pop ()
if command == "top":
if len (stack):
print stack [len (stack) - 1]
else:
print error
if command == "min":
if len (stack):
print min (stack)
else:
print error
```

Find the complete program on GitHub.

### AWK

AWK does not have a `push`

operator. But it dynamically grows array, that is, if you add an element to an array, and the index doesn’t exist yet, AWK grows the array as needed. So we can simulate a push by just adding the pushed element to the first index after the largest current index.

To simulate `pop`

, we make use of the `delete`

function, which removes an element from an array.

There is no AWK buildin to get the minimum value of a list or array, so we have to iterate over the array, and find the minimum.

AWK programs automatically iterate over the input, executing blocks where preceding conditions are met:

```
BEGIN {error = "Stack is empty"}
{size = length (stack)}
```

A `BEGIN`

block is executed once, before processing any input (if you are wondering where Perl got its `BEGIN`

blocks from, the answer is AWK); this sets up an error message. The second block is executed for every line of input (there is no condition, which in AWK means, it’s always true). Here we store the current number of elements of the stack in the variable `size`

, so we can refer to it in other blocks. Note that we do not have to declare variables.

Each of the four possible commands get their own block.

```
/^push/ {
split($0, a, / +/)
stack [size + 1] = a [2]
}
```

In AWK, the current line is in the variable `$0`

. `split`

works like split in Perl, but it has arguments in a different order. The first argument is the string to be split (here, the current line of input); the second argument is an array, in which the results are placed. The third argument is the pattern to split on. So, in the block, we split on whitespace, placing the command (which we already know is `"push"`

) in `a [1]`

, and the value to be pushed in `a [2]`

. Note that in AWK, array indexes are 1-based.

We then assign the value to be pushed just passed the end of the current stack, in effect, pushing a value on the stack.

```
/^pop/ {
delete stack [size]
}
```

Remove the last element of the array `stack`

.

```
/^top/ {
print size ? stack [size] : error
}
```

Print the last element of the array `stack`

, or an error if the stack is empty.

```
/^min/ {
if (size) {
min = stack [1]
for (i = 2; i <= size; i ++) {
if (min > stack [i]) {
min = stack [i]
}
}
print min
}
else {
print error
}
}
```

Here we iterate over the array `stack`

, finding the minimum value.

Find the complete program on GitHub.

### C

As usual, C requires the most work. There are no `push`

or `pop`

operations, and arrays don’t automatically resize.

So, we will not be using an array. Instead, we will be using a linked list using records and pointers. Just like algorithms 101!

We will be using the following type and variable:

```
struct node {
long value;
struct node * next;
};
struct node * stack = NULL;
```

Our stack is pointer to a record; this record holds two elements: `value`

, and `next`

, where the former is a value pushed on the stack, and the latter a pointer to another record. We initialize the stack to `NULL`

, indicating the stack is empty.

We iterate over the input, putting each line into the variable `line`

. Then, we do our actions:

```
if (strncmp (line, "push", 4) == 0) {
long val;
if (sscanf (line + 4, " %ld", &val)) {
struct node * head;
head = (struct node *) malloc (sizeof (struct node));
if (head == NULL) {
fprintf (stderr, "Out of memory!\n");
exit (1);
}
head -> value = val;
head -> next = stack;
stack = head;
}
}
```

If we encounter a `push`

command, we will be using `sscanf`

to extract the value from the current line of input. We then create a new record by using `malloc`

. In the new record, we set the just parsed value, and we let the new record point to the current stack. Finally, we update `stack`

to point to the new record.

```
if (strncmp (line, "pop", 3) == 0 && stack != NULL) {
struct node * next;
next = stack -> next;
free (stack);
stack = next;
}
```

When we have to pop an element from the stack, we use a temporary variable `next`

, which we set to the second element on the stack. We `free`

`stack`

, returning the memory, and then update `stack`

.

```
if (strncmp (line, "top", 3) == 0) {
if (stack == NULL) {
printf ("%s\n", error);
}
else {
printf ("%ld\n", stack -> value);
}
}
```

This prints the top of the stack, or an error message if the stack is empty.

```
if (strncmp (line, "min", 3) == 0) {
if (stack == NULL) {
printf ("%s\n", error);
}
else {
long min = stack -> value;
struct node * pointer = stack -> next;
while (pointer != NULL) {
if (pointer -> value < min) {
min = pointer -> value;
}
pointer = pointer -> next;
}
printf ("%ld\n", min);
}
}
```

To find the minimum element of the stack, we have to walk through our linked list. Assuming the stack isn’t empty, we start with the top of the stack (first element of the linked list), and then walk the list by following the `next`

pointer to the end. Each time we find an element which is less than the smallest element found so far, we remember it.

Find the complete program program on GitHub.