Stack & Queue

CCI

• Three in One
• Stack Min
• Stack of plates
• Queue with 2 stacks
• Sort stack
• Animal shelter

Three in One

Use a single array to implement three stacks.

Solution

• Fixed Division
• Flexible Divisions

Stack Min

Implement min feature for stack. O(1)

Solution

• Using additional stack, keep track of stack value.
• If number pushed is smaller than the top of minStack,which means the smallest number, push the number to minStack.
• If the number popped out is the min number, also pop the number from min stack.

var stack = [3, 14, 21, 2, 32, 5, 7, 1, 11]
var minStack = [3, 2, 1]

Code

Stack of plates

Implement multiple stacks -push() and pop() inside SetOfStacks() which is container of stacks.

Solution

• Prepare array of stack
• If the current stack is full, create new stack.
• If stack is empty, remove it.

Code

Queue with 2 stacks

Implement queue using 2 stacks.

Solution

• When it is needed to dequeue, pop() all elements except for index 0 from a stack and put them into temp stack.
• pop() last element which is index 0.
• pop() all element from temp stack and put them back to main stack.

Code

Sort stack

sort a stack such that the smallest items are on the top. Use only an additional stack.

Solution

• Create mainStack and tempStack.

• pop() from mainStack.

• Make temp variable to store pop() ed element.

• If element poped is smaller than last element of tempStack, put all larger elements back to mainStack

• Do this process until mainStack is empty.
• If mainStackis empty, pop each elements ontempStackand push them to mainStack.

https://stackoverflow.com/questions/41283590/sorting-elements-of-stack-using-javascript

Code