JavaScript에서 스택을 구현하는 방법
- 不言원래의
- 2018-07-11 16:54:124625검색
이 글은 주로 JavaScript를 사용하여 스택을 구현하는 방법을 소개하며, 이는 특정 참조 값을 가지고 있습니다. 이제 도움이 필요한 친구들이 참고할 수 있습니다.
스택이란?
스택은 LIFO(후입선출) 원칙을 따르는 정렬된 컬렉션입니다.
새로 추가되거나 삭제될 요소는 스택의 끝 부분에 저장되는데, 이를 스택의 상단(top)이라고 하고, 반대쪽 끝을 하단(bottom)이라고 합니다. 스택.
스택에서 새 요소는 스택의 맨 위에 가까우며, 이전 요소는 스택의 맨 아래에 가까움
Reality
에 나오는 예들은 생활 속 스택의 예에서도 많이 찾아볼 수 있습니다. 예를 들어 주방에 쌓인 접시 중 맨 위에 쌓인 접시가 항상 먼저 사용되며, 입력 상자의 내용이 삭제되면 항상 마지막 입력이 먼저 삭제되고 탄창에 있는 총알이 그대로 먼저 발사됩니다. ....
수동으로 스택 구현
먼저 스택을 나타내는 클래스를 만듭니다
function Stack () { }
저장할 데이터 구조 스택의 요소에 대해 배열을 선택할 수 있습니다
function Stack(){
var items = []; //用来保存栈里的元素
}
다음으로 스택에 몇 가지 메서드를 추가합니다
push(element(s)); //添加新元素到栈顶 pop(); //移除栈顶的元素，同时返回被移除的元素 peek(); //返回栈顶的元素，不对栈做任何修改 isEmpty(); //如果栈里没有任何元素就返回true，否则false clear(); //移除栈里的所有元素 size(); //返回栈里的元素个数,类似于数组的length属性
구현해야 할 첫 번째 메서드는 다음과 같습니다. 푸시. 스택에 새 요소를 추가하는 데 사용되는 한 가지 매우 중요한 점은 이 방법은 스택의 끝인 스택 상단에만 추가한다는 것입니다. 따라서 다음과 같이 작성할 수 있습니다. push。用来往栈里添加新元素，有一点很重要：该方法只添加到栈顶，也就是栈的末尾。所以，可以这样写：
this.push = function (element) {
items.push(element);
}
利用数组的push方法，就可以实现在栈顶末尾添加新的元素了。
接着，来实现pop方法，用来实现移除栈里的元素。栈遵从LIFO（后进先出）原则。移出去的是最后添加进去的元素。因此，可以使用数组的pop方法。
this.pop = function () {
return items.pop();
}
这样一来，这个栈自然就遵从了LIFO原则
现在，再来为这个栈添额外的辅助方法。
如果想知道栈里最后添加的元素是什么，可以用peek方法。这个方法将返回栈顶的元素
this.peek = function () {
return items[items.length-1];
}
因为类内部是用数组保存元素的，所以这里访问数组最后一个元素用length-1
下一个要实现的方法是isEmpty,如果栈为空的话，就返回true，否则返回false：
this.isEmpty = function () {
return items.length == 0;
}
使用isEmpty方法，就能简单地判断栈内部是否为空。
类似于数组地length属性，我们也可以实现栈地length。
this.size = function () {
return items.length;
}
因为栈地内部使用数组保存元素，所以数组地length就是栈的长度。
实现clear方法，clear方法用来清空栈中所有的元素。最简单的实现方法是：
this.clear = function () {
items = [];
}
其实多次调用pop方法也可以，但是没有这个方法来的简单快捷。
最后，为了检查栈里的内容，还需要实现一个辅助方法：print
this.print = function () {
console.log(items.toString());
}배열의 push 메소드를 사용하면 스택 상단 끝에 새 요소를 추가할 수 있습니다. 다음으로 pop 메서드를 구현하여 스택에서 요소를 제거합니다. 스택은 LIFO(후입선출) 원칙을 따릅니다. 제거되는 것은 마지막으로 추가된 요소입니다. 따라서 배열의 pop 메소드를 사용할 수 있습니다.
function Stack(){
var items = []; //用来保存栈里的元素
this.push = function (element) {
items.push(element);
}
this.pop = function () {
return items.pop();
}
this.peek = function () {
return items[items.length-1];
}
this.isEmpty = function () {
return items.length == 0;
}
this.size = function () {
return items.length;
}
this.clear = function () {
items = [];
}
this.print = function () {
console.log(items.toString());
}
}이런 방식으로 이 스택은 자연스럽게 LIFO 원칙을 따릅니다. 이제 이 스택에 보조 메서드를 추가해 보겠습니다. 스택에 마지막으로 추가된 요소를 알고 싶다면 peek 방법을 사용할 수 있습니다. 이 메소드는 스택의 맨 위에 있는 요소를 반환합니다.
var stack = new Stack(); console.log(stack.isEmpty()); //控制台输出true클래스는 요소를 저장하기 위해 배열을 사용하므로 여기서는
length-1를 사용합니다.# 🎜🎜#다음으로 구현할 메서드는 isEmpty입니다. 스택이 비어 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
stack.push(5); stack.push(8);
isEmpty 메소드를 사용하면 스택이 비어 있는지 간단히 확인할 수 있습니다.
배열의 길이 속성과 유사하게 스택의 길이도 구현할 수 있습니다.
console.log(stack.peek()); //控制台输出8
스택은 요소를 저장하기 위해 내부적으로 배열을 사용하기 때문에 배열의 길이는 스택의 길이와 같습니다.
clear 메소드를 구현합니다. Clear 메소드는 스택의 모든 요소를 지우는 데 사용됩니다. 가장 간단한 구현 방법은 다음과 같습니다.
stack.push(11); console.log(stack.size()); //控制台输出3
사실 pop 메소드를 여러 번 호출하는 것도 가능하지만 이 메소드만큼 간단하고 빠르지는 않습니다.
마지막으로 스택의 내용을 확인하려면 print라는 보조 메서드를 구현해야 합니다. 스택의 모든 요소를 콘솔에 출력합니다.
stack.push(15);
이 시점에서
stack!
stack이 완전히 생성되었습니다. 전체 코드
stack.pop(); stack.pop(); console.log(stack.size()); //控制台输出2 stack.print(); //控制台输出[5,8]
Stack 클래스 사용하기
function pideBy2 (decNumber) {
var remStack = new Stack(),
rem,
binaryString = '';
while (decNumber>0) { //{1}
rem = Math.floor(decNumber % 2); //{2}
remStack.push(rem); //{3}
decNumber = Math.floor(decNumber / 2); //{4}
}
while (!remStack.isEmpty()) { //{5}
binaryString += remStack.pop().toString();
}
return binaryString;
}console.log(pideBy2(520)); //输出1000001000 console.log(pideBy2(10)); //输出1010 console.log(pideBy2(1000)); //输出1111101000peek 메서드를 호출하면 분명히 8이 출력됩니다. 스택 맨 위에 있는 요소입니다.
function baseConverter (decNumber, base) {
var remStack = new Stack(),
rem,
baseString = '';
digits = '0123456789ABCDEF'; //{6}
while (decNumber>0) {
rem = Math.floor(decNumber % base);
remStack.push(rem); //{3}
decNumber = Math.floor(decNumber / base);
}
while (!remStack.isEmpty()) {
baseString += digits[remStack.pop()]; //{7}
}
return baseString;
}다른 요소 추가:
console.log(baseConverter(1231,2)); //输出10011001111 console.log(baseConverter(1231,8)); //输出2317 console.log(baseConverter(1231,16)); //输出4CF스택에 11개를 더 추가했습니다. size 메서드가 호출되면 스택에 세 개의 요소(5, 8, 11)가 있으므로 출력은 3입니다. 이때 isEmpty 메소드를 호출하면 거짓 출력이 출력됩니다(이때 스택이 비어 있지 않기 때문입니다). 마지막으로 다른 요소를 추가합니다: #🎜🎜#rrreee#🎜🎜#그런 다음 pop 메서드를 두 번 호출하여 스택에서 두 요소를 제거합니다. #🎜🎜#rrreee#🎜🎜#이 시점에서 전체 스택 테스트가 완료되었습니다. #🎜🎜##🎜🎜#스택을 사용하여 문제 해결 #🎜🎜##🎜🎜#스택을 사용하여 16진수 변환을 완료합니다. #🎜🎜##🎜🎜#실생활에서는 주로 10진법을 사용하지만 컴퓨팅 과학에서는 이진법이 매우 중요합니다. 컴퓨터의 모든 것은 이진수 0과 1로 표현되기 때문입니다. 대학의 컴퓨터 수업에서는 먼저 진수 변환을 가르칩니다. 바이너리를 예로 들어보겠습니다: #🎜🎜##🎜🎜##🎜🎜##🎜🎜#rrreee#🎜🎜#이 코드에서 결과가 2로 균등하게 나누어지는 조건을 충족하는 경우, (라인 {1}) , we 현재 결과와 나머지 2가 얻어져 스택에 배치됩니다(라인 {2}, {3}). 그런 다음 결과를 2로 균등하게 나눕니다(라인 {4}) #🎜🎜##🎜🎜# 참고: JavaScript에는 숫자 유형이 있지만 정수와 부동 소수점 숫자를 구분하지 않습니다. 따라서 나누기 연산이 정수 부분만 반환하도록 하려면 Math.floor 함수를 사용하십시오. #🎜🎜##🎜🎜#마지막으로 pop 메서드를 사용하여 스택에서 모든 요소를 제거하고 팝된 요소를 문자열({5}행)로 연결합니다. #🎜🎜##🎜🎜#테스트해 보세요: #🎜🎜#rrreee#🎜🎜#다음으로, 십진수를 임의의 진수로 변환할 수 있도록 위의 알고리즘을 쉽게 수정할 수 있습니다. 십진수와 2의 나눗셈을 이진수로 변환하는 것 외에도 다음 알고리즘과 같이 다른 임의의 진수를 매개변수로 전달할 수도 있습니다. #🎜🎜#
function baseConverter (decNumber, base) {
var remStack = new Stack(),
rem,
baseString = '';
digits = '0123456789ABCDEF'; //{6}
while (decNumber>0) {
rem = Math.floor(decNumber % base);
remStack.push(rem); //{3}
decNumber = Math.floor(decNumber / base);
}
while (!remStack.isEmpty()) {
baseString += digits[remStack.pop()]; //{7}
}
return baseString;
}
在将十进制转成二进制时，余数是0或1；在将十进制转成八进制时，余数时0-8之间的数；但是将十进制转成十六进制时，余数时0-9之间的数字加上A、B、C、D、E、F（对应10、11、12、13、14和15）。因此，需要对栈中的数字做个转化才可以（行{6}、{7}）。
来测试一下输出结果：
console.log(baseConverter(1231,2)); //输出10011001111 console.log(baseConverter(1231,8)); //输出2317 console.log(baseConverter(1231,16)); //输出4CF
显然是正确的。
小结
我们用js代码自己实现了栈。并且通过进制转换的例子来实际应用了它。栈的应用实例还有很多，比如平衡圆括号和汉诺塔。
以上就是本文的全部内容，希望对大家的学习有所帮助，更多相关内容请关注PHP中文网！
相关推荐：
위 내용은 JavaScript에서 스택을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!