Reverse a String Using Stack
Stacks
JavaScript
Problem:
Given a string, reverse it using stack. Do not use any built in string or array reverse functions.
Example:
Input String: JavaScript
Output String: tpircSavaJ
Algorithm:
This is a relatively simple problem. The approach involves pushing all the characters of the string onto a stack and then reading them by popping them off. Since a stack follows the Last-In-First-Out (LIFO) principle, the string is automatically reversed during the pop operations.
Steps:
- Create an empty stack and push all the characters of the string onto it.
- Pop the characters from the stack one by one and concatenate them to form the reversed string.
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:
Output:
solution.js
stack.js
stack-displayer.js
animator-module.js
function stackSolution(args) {
let string = args[0];
const stack = new Stack(
[],
{
name: 'Stack',
description: 'This stack is used to hold the string characters.'
}
);
animatorModule.displayComment('Push individual characters of the string to the stack.');
for (var i = 0; i < string.length; i++) {
stack.push(string[i]);
}
animatorModule.displayComment('Now pop the characters from stack and concatenate them.');
let reversedString = '';
while (! stack.isEmpty()) {
reversedString += stack.pop();
animatorModule.displayOutput(reversedString);
}
animatorModule.displayComment('');
return reversedString;
}
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
}
})();