Created
September 1, 2014 09:19
-
-
Save easonhan007/9c0c9e0d0a0fff31b888 to your computer and use it in GitHub Desktop.
How to implement a stack using javascript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function Stack() { | |
this.dataSource = []; | |
this.top = 0; | |
this.push = push; | |
this.pop = pop; | |
this.peek = peek; | |
this.clear = clear; | |
this.length = length; | |
function push(element) { | |
this.dataSource[this.top++] = element; | |
} | |
function pop() { | |
return this.dataSource[--this.top]; | |
} | |
function peek() { | |
return this.dataSource[this.top - 1]; | |
} | |
function length() { | |
return this.top; | |
} | |
function clear() { | |
this.top = 0; | |
} | |
} | |
// test Stack | |
/* | |
var s = new Stack(); | |
s.push('ada'); | |
s.push('bob'); | |
s.push('cook'); | |
s.push('david'); | |
console.log("length is: " + s.length()); | |
console.log(s.peek()); | |
var poped = s.pop(); | |
console.log("the poped element is: " + poped); | |
console.log(s.peek()); | |
s.clear(); | |
console.log("after clear length is: " + s.length()); | |
console.log(s.peek()); | |
s.push('erik'); | |
console.log(s.peek()); | |
*/ | |
// convert base | |
// convert 50 to base 2 | |
// 将10进制转换成2进制,使用stack | |
function mulBase(num, base) { | |
var s = new Stack() ; | |
do { | |
s.push(num % base); | |
num = Math.floor(num /= base); | |
} while(num > 0); | |
var converted = ''; | |
while(s.length() > 0) converted += s.pop(); | |
return converted; | |
} | |
console.log("50 convert to base 2 is "); | |
console.log(mulBase(50, 2)); | |
console.log(""); | |
// 实现回文检测 | |
// test palindrome | |
function isPalindrome(word) { | |
var s = new Stack(); | |
for (var i = 0; i < word.length; i++) { | |
s.push(word[i]); | |
} | |
var rword = ""; | |
while(s.length() > 0) { | |
rword += s.pop(); | |
} | |
if(word == rword) return true; | |
else return false; | |
} | |
var word = 'hello'; | |
if(isPalindrome(word)) | |
console.log(word + " is palindrome"); | |
else | |
console.log(word + " is not palindrome"); | |
var word = "racecar"; | |
if(isPalindrome(word)) | |
console.log(word + " is palindrome"); | |
else | |
console.log(word + " is not palindrome"); | |
// simulating recursive process | |
function fact(n) { | |
var s = new Stack(); | |
while(n > 1) s.push(n--); | |
var product = 1; | |
while(s.length() > 0) product *= s.pop(); | |
return product; | |
} | |
// is miss parenthesis | |
function isParenthesisMissing(expression) { | |
var s = new Stack(); | |
var position = 0; | |
for(var i = 0; i < expression.length; i++) { | |
position = i + 1; | |
if(expression[i] == '(') s.push(position); | |
if(expression[i] == ')') s.pop(); | |
} | |
var result = ''; | |
if (s.length() !== 0) { | |
while(s.length() > 0) result = result + s.pop() + ' '; | |
} | |
return result; | |
} | |
var expression = '2.3 + 23 / 12 + (3.14159 * .24'; | |
console.log(isParenthesisMissing(expression)); | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment