Sort A Given Stack
Stacks
JavaScript
Problem:
Given a stack of integers, sort it in ascending order.
Example:
Input Array: [36, 9, 22, 75, 92, 23]
Output Array: [9, 22, 23, 36, 75, 92]
Algorithm:
To solve this, we will use an additional temporary stack. We will pop elements from the input stack and push them to the temporary stack, comparing each element with those already in the temporary stack to maintain the correct order.
Steps:
- Create a temporary stack, tempStack.
- While the input stack is not empty, do the following:
- Pop an element from the input stack and call it temp.
- While the temporary stack is not empty and the top element of tempStack is greater than temp, pop elements from tempStack and push them back to the input stack.
- Push temp into tempStack.
- After the loop ends, the sorted elements will be in tempStack.
Solution & Visualize:
The animation/visualization below demonstrates how the algorithm to reverse a string works. Feel free to experiment by changing the input strings.
Result
Code
Input:
Enter the array elements followed by a comma
Output:
solution.js
stack.js
stack-displayer.js
animator-module.js
function stackSolution(args) {
let array = args[0];
const stack = new Stack(
array,
{
name: 'Input Stack',
description: 'This stack holds the input array elements.'
}
);
const tempStack = new Stack(
[],
{
name: 'Temp Stack',
description: 'This stack will hold the sorted array elements.'
}
);
let temp = '';
while (! stack.isEmpty()) {
animatorModule.displayComment('Pop the element from the input stack.', 500);
temp = stack.pop();
while (! tempStack.isEmpty() && tempStack.top() < temp) {
animatorModule.displayComment(
'If the popped element('+ temp +') is greater than the elements in the tempStack, then push the elements from tempStack to input stack.',
700
);
stack.push(tempStack.pop());
}
animatorModule.displayComment('Add the popped element to the tempStack.', 500);
tempStack.push(temp);
}
let sortedArray = [];
while (! tempStack.isEmpty()) {
animatorModule.displayComment(
'Finally we get the sorted list in the tempStack. Pop and get the sorted list.',
500
);
animatorModule.displayOutput([...sortedArray]);
sortedArray.push(tempStack.pop());
}
animatorModule.displayOutput(sortedArray);
animatorModule.displayComment('');
return sortedArray;
}
class Stack {
metaData = {
'name': 'Stack',
'description': '',
'animation_duration': 1500,
}
constructor(initialData, metaData) {
this.initialData = [...initialData];
this.metaData = Object.assign({}, this.metaData, metaData);
this.stackDisplayer = new StackDisplayer(initialData, this.metaData);
this.stackId = this.stackDisplayer.display();
}
getStackData() {
return this.initialData;
}
push(value) {
this.initialData.push(value);
// Perform the animation
animatorModule.performPushAnimation(this.stackId, value);
}
pop() {
if (this.initialData.length == 0) return;
const value = this.initialData.pop();
// Perform the animation
animatorModule.performPopAnimation(this.stackId, value);
return value;
}
top() {
if (this.initialData.length == 0) return;
const value = this.initialData[this.initialData.length - 1];
return value;
}
isEmpty() {
return this.initialData.length === 0;
}
}
class StackDisplayer {
constructor(initialData, metaData) {
this.initialData = initialData;
this.metaData = metaData;
}
display() {
// Display stack on the screen
const stackTemplate = document.getElementById('stack-template');
const clone = stackTemplate.content.cloneNode(true);
const stackCount = document.getElementsByClassName('stack-wrapper').length + 1;
// Add an unique ID to the clone
const stackWrapperId = 'stack-' + stackCount;
const stackWrapper = clone.querySelector('.stack-wrapper');
stackWrapper.id = stackWrapperId;
// Add initial stack items
const stackElement = clone.querySelector('.stack');
while(this.initialData.length) {
stackElement.insertAdjacentHTML(
'beforeend',
'<div class="stack-item">'+ this.initialData.pop() +'</div>'
)
}
clone.querySelector('.stack-description h4')
.textContent = this.metaData.name;
clone.querySelector('.stack-description p')
.textContent = this.metaData.description;
document.getElementById('stack-visualizer')
.appendChild(clone);
return stackWrapperId;
}
}
class AnimationList {
animations = [];
length() {
return this.animations.length;
}
push(animation) {
this.animations.push(animation);
}
shift() {
return this.animations.shift();
}
}
let animatorModule = (function() {
let animations = new AnimationList();
let animationsRunning = false;
let animationSpeed = 1200;
function getMoveDownAnimation(animation) {
let topElement = animation.stackElement.children[0];
let distance = animation.stackElement.offsetHeight;
if (topElement) {
distance = topElement.getBoundingClientRect().y
- animation.pushElement.getBoundingClientRect().y
- animation.pushElement.getBoundingClientRect().height
- 2; // Margin bottom
}
let moveDownAnimation = [
'0',
'0',
'0',
'0',
'0',
'0',
'0',
'0',
'0',
'0',
'0',
'0',
(0.2 * distance) + 'px',
(0.37 * distance) + 'px',
(0.55 * distance) + 'px',
(0.7 * distance) + 'px',
(0.87 * distance) + 'px',
distance + 'px',
distance + 'px'
];
return moveDownAnimation;
}
function getMoveUpAnimation(animation) {
let topElement = animation.stackElement.children[0];
let distance = topElement.getBoundingClientRect().y
- animation.pushElement.getBoundingClientRect().y;
let moveUpAnimation = [
(distance - 0.95 * distance) + 'px',
(distance - 0.87 * distance) + 'px',
(distance - 0.7 * distance) + 'px',
(distance - 0.55 * distance) + 'px',
(distance - 0.37 * distance) + 'px',
(distance - 0.2 * distance) + 'px',
distance + 'px',
distance + 'px',
distance + 'px',
distance + 'px',
distance + 'px',
distance + 'px',
distance + 'px'
];
return moveUpAnimation;
}
function pushAnimate(animation) {
animation.pushElement.textContent = animation.value;
let pushAnimationKeyFrames = {
// 25% - Show element
opacity: ['0', '0.3', '0.7', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1', '1'],
left: ['0', '0', '0', '0', '7px', '20px', '35px', '60px', '75px', '90px', '100px', '100px', '100px', '100px', '100px', '100px', '100px', '100px', '100px'],
top: getMoveDownAnimation(animation),
offset: [0, 0.08, 0.16, 0.25, 0.25, 0.31, 0.37, 0.43, 0.5, 0.56, 0.62, 0.68, 0.73, 0.78, 0.83, 0.88, 0.93, 0.98, 1]
};
let duplicateElement = animation.pushElement.cloneNode(true);
duplicateElement.classList.remove('hidden');
// TODO: Increase the height of the stack before pushing
let pushAnimation = animation.pushElement.animate(pushAnimationKeyFrames, animationSpeed);
return new Promise((resolve) => {
return pushAnimation.finished.then(() => {
animation.stackElement.prepend(duplicateElement);
resolve(`Push Animation completed!`);
});
})
}
function popAnimate(animation) {
let popAnimationKeyFrames = {
bottom: getMoveUpAnimation(animation),
left: ['0', '0', '0', '0', '0', '0', '7px', '20px', '35px', '60px', '75px', '90px', '100px'],
offset: [0, 0.07, 0.15, 0.22, 0.3, 0.37, 0.45, 0.52, 0.6, 0.67, 0.75, 0.82, 0.9, 1]
};
let topElement = animation.stackElement.children[0];
let popAnimation = topElement.animate(popAnimationKeyFrames, animationSpeed);
// The animation is not smooth
// So remove the item before animation is completed
setTimeout(() => {
topElement.remove();
animation.popElement.textContent = topElement.textContent;
}, animationSpeed - 200);
return new Promise((resolve) => {
return popAnimation.finished.then(() => {
// topElement.remove();
// animation.popElement.textContent = topElement.textContent;
resolve(`Pop Animation completed!`);
});
})
}
function displayCommentAnimate(animation) {
return new Promise((resolve) => {
document.getElementsByClassName('sv-comment')[0]
.innerHTML = animation.value;
setTimeout(() => {
resolve('Comment displayed!');
}, animation.timeout);
})
}
function displayOutputAnimate(animation) {
return new Promise((resolve) => {
let outputELement = document.getElementById('final-output');
outputELement.innerHTML = animation.value;
resolve('Output displayed!');
})
}
function runSingleAnimation(animation) {
switch (animation.type) {
case 'push':
return pushAnimate(animation);
break;
case 'pop':
return popAnimate(animation);
break;
case 'display-comment':
return displayCommentAnimate(animation);
break;
case 'display-output':
return displayOutputAnimate(animation);
break;
}
}
function runAnimations() {
if (animationsRunning) return;
animationsRunning = true;
// Perform the animations one after the other
let animation = animations.shift();
runSingleAnimation(animation)
.then(() => {
animationsRunning = false;
if (animations.length()) {
runAnimations();
}
});
}
function getStackElements(stackId) {
let stackWrapper = document.getElementById(stackId);
return {
stackElement: stackWrapper.getElementsByClassName('stack')[0],
pushElement: stackWrapper.getElementsByClassName('push-element')[0],
popElement: stackWrapper.getElementsByClassName('pop-element')[0]
}
}
let performPushAnimation = function (stackId, value) {
let animationObject = Object.assign(
{type: 'push', value: value},
getStackElements(stackId)
);
animations.push(animationObject);
runAnimations();
}
let performPopAnimation = function (stackId, value) {
let animationObject = Object.assign(
{type: 'pop', value: value},
getStackElements(stackId)
);
animations.push(animationObject);
runAnimations();
}
/**
* Set the animation duration.
*
* @param flot speed Duration in seconds (1, 2.5...)
*/
let setAnimationSpeed = function (speed) {
animationSpeed = speed * 1000;
}
let displayComment = function (comment, timeout = 0) {
let animationObject = {
type: 'display-comment',
value: comment,
timeout: timeout
};
animations.push(animationObject);
runAnimations();
}
let displayOutput = function (output) {
let animationObject = {
type: 'display-output',
value: output
};
animations.push(animationObject);
runAnimations();
}
let clearAnimations = function () {
animations = new AnimationList();
animationsRunning = false;
}
return {
performPushAnimation: performPushAnimation,
performPopAnimation: performPopAnimation,
setAnimationSpeed: setAnimationSpeed,
displayComment: displayComment,
displayOutput: displayOutput,
clearAnimations: clearAnimations
}
})();