The Stack

A data structure of type array, store data in a linear order. The bridge between elements is thus abstracted as inherit by sequentiality, the prefixed order of memory locations. JavaScript have lot's of Array methods and the four most basic ones are push and pop, as well as the counterparts shift and unshift.

This post focus a problem borrowed from a text by Donald Knuth and tries to conceptualize the 'stack'.

Six railroad cars are positioned on the input trail. Each is numbered 1..6, left to right. Suppose we could move them to a "stack" (the blue track) one at a time, and from the stack (top first) to an output trail (the red one).

There are two possible operations. Let's call the operation to move a car from the input to the stack 'S' and the operation to move a car from the stack to the output 'X'.

How would you do it and what combinations would be possible?

Would the sequence 324641 be possible? How about 154623?

123456 into 325641:

S. input(123456) -> stack(,->1)
S. input(23456) -> stack(1, -> 2)
S. input(3456) -> stack (12, -> 3)
X. stack (123) -> output (,-> 3)
X. stack (12) -> output (3, -> 2)
S. input(456) -> stack(1, -> 4)
S. input(56) -> stack(14, -> 5)
X. stack(145) -> output (32, -> 5)
S. input(6) -> stack(14, -> 6)
X. stack(146) -> output (325, -> 6)
X. stack (14) -> output (3256, -> 4)
X. stack (1) -> output (32564, -> 1)
=========================
SSSXXSSXSXXX/success: 325641

123456 into 154623:

S. input(123456) -> stack(,->1)
X. stack (1) -> output (, ->1)
S. input(23456) -> stack(, ->2)
S. input(3456)  -> stack(2, ->3)
S. input(456)  -> stack(23, ->4)
S. input(56)  -> stack(234, ->5)
X. stack (2345) -> output (1, -> 5)
X. stack (234) -> output (15, -> 4)
S. input(6) -> stack(23, -> 6)
X. stack(236) -> output (154, -> 6)
X. stack(23) -> FAIL (car 2 can't jump over car 3)
=========================
SXSSSSXXSXX/fail: 1546

How should we understand this?

The sequence can be understood as a list of instructions, left to right. The first character of the sequence stream is the first element, the second character the second and so on.

An valid instruction of type 'X' must be proceeded by the same quantity (or more) of instruction type 'S'. This also means that any list of instruction must begin with an 'S' instruction since the 'stack' always is empty at first.

The solution is therefore quite simple:

function isSolutionValid(charStream, input) {
  // Firstly, we check if the stream is
  // an valid instructions.
  const instructions = charStream.split('');
  const isStreamValid =
    instructions.length % 2 === 0 &&
    instructions.filter(
        action => action === 'S'
      ).length === instructions.filter(
          action => action === 'X'
        ).length;
  if (!isStreamValid) {
    const errorMsg = `
A valid instructions must contain an even
number of both 'S' and 'X'.
    `;
    throw new TypeError(errorMsg);
  }

  // We declare a stack, an output
  // but also deep copies (just so we can return
  // things for pretty printing.
  let stack = [];
  let output = [];
  const _insts = [...instructions];
  const _input = [...input];

  // While we have more instructions to perform, 
  // continue. If 'S', push to stack and remove 
  // from bottom of the input. If 'X', remove 
  // from the top of the stack and push to 
  // the output.
  while (_insts.length > 0) {
    if (_insts[0] === 'S') {
      stack.push(_input[0]);
      _input.shift();
    } else if (_insts[0] === 'X' && stack.length > 0) {
      const topOfTheStack = stack[stack.length - 1];
      output.push(topOfTheStack);
      stack.pop();
    } else {
      throw new Error('ILLEGAL. Stack is empty!');
    }
    _insts.shift();
  }
  return {
    output,
    input,
    instructions: charStream,
  };
}

const {
  output,
  input,
  instructions
} = isSolutionValid('SSSXXSSXSXXX', [1, 2, 3, 4, 5, 6]); 

And with pretty printing of the output…

console.log('INSTRUCTIONS:');
console.log(instructions);
console.log('=============');
console.log('INPUT:');
console.log(input);
console.log('=============');
console.log('OUTPUT:');
console.log(output);

/*
INSTRUCTIONS:
SSSXXSSXSXXX
=============
INPUT:
[ 1, 2, 3, 4, 5, 6 ]
=============
OUTPUT:
[ 3, 2, 5, 6, 4, 1 ]
*/

This algorithm handles any sequence of instructions, if the set of instructions follows the rules. The solution above is also available at GitHub.