JavaScript 데이터 구조 및 알고리즘 스택 및 큐

학습원인

V2EX를 검색하던 중 이런 글을 본 적이 있습니다.
수학은 전적으로 선생님에게 맡겨져 있습니다. 아마도 고등학교 수준에서 기본적인 수학을 배우고 싶습니다. 어떤 책을 추천하시나요?
해당 글을 게시한 게시자는 대학에서 수학 고급과정을 이수하지 않았고, 출근 당시 프론트엔드 업무에 종사하고 있었습니다. 수학적 지식이 부족하다고 느껴서 수학을 따라잡고 싶어요.
포스팅을 읽어보니 저와 매우 비슷하다는 생각이 들었습니다. 제 전공은 고급 수학이 필요하지 않고, 프론트엔드도 공부했기 때문입니다. 수학적 지식의 부족으로 인한 어려움도 느꼈습니다. 동시에, 나는 수학적 사고가 별로 좋지 않기 때문에 기본적인 수학과 컴퓨터 지식을 배우기 위해 열심히 노력하기로 결정했습니다.
당시 어떤 사람들은 "프론트 엔드에는 어떤 데이터 구조와 알고리즘이 필요합니까?"라고 말했습니다. 그러나 나는 이 문제에 대해 나만의 견해를 가지고 있습니다.
프론트엔드에는 알고리즘과 같은 지식이 필요하지 않다고 생각합니다. 제 생각에는 프론트엔드가 탄탄한 컴퓨터 기반을 갖추고 있어 자체 개발에 매우 도움이 됩니다. 나는 프로그래머가 되고 싶다. 평생 후배 프론트엔드와 코더가 되기보다는요.
나 자신에 대한 격려라고 할 수 있다. 역시 기본이 상한선을 정하는 거고, 컴퓨터에 관심이 많아서 배우는 게 피곤하더라도 아주 즐겁습니다. 그래서 저는 온라인에 접속하여 "JavaScript 데이터 구조 및 알고리즘 학습"이라는 책을 구입했습니다. 도서관에서 빌린 "Dahua 데이터 구조"와 함께 데이터 구조 및 알고리즘에 대한 예비 연구를 시작했습니다.

JavaScipt의 배열 연산

다음 단계는 데이터 구조의 첫 번째 부분인 스택입니다.
스택은 후입선출 원칙(LIFO, Last In First Out의 약어)을 따르는 정렬된 컬렉션입니다. 스택의 맨 위는 항상 최신 요소입니다.
예를 들어, 스택은 상자에 책을 쌓아 놓은 것과 같습니다. 아래쪽 책을 가져오려면 먼저 위쪽 책을 제거해야 합니다. (물론 아래 책을 먼저 가져갈 수는 없습니다.)

JavaScipt에서 스택 구현
먼저 생성자를 만듭니다.

/**
 * 栈的构造函数
 */
function Stack() {

 // 用数组来模拟栈
 var item = [];
}

로그인 후 복사

스택에는 다음 메서드가 있어야 합니다.
push(element(s)): 스택 상단에 여러 요소를 추가합니다
pop(): 스택의 최상위 요소를 제거하고 반환합니다
peek(): 스택의 최상위 요소를 반환합니다
isAmpty: 스택이 비어 있는지 확인하고, 비어 있으면 true를 반환합니다
지우기: 스택에서 모든 요소를 제거합니다
크기: 스택의 요소 수를 반환합니다.
print: 스택의 모든 내용을 문자열로 표시합니다
Push방식 구현
설명: 새 요소를 스택에 추가해야 하며 요소 위치는 대기열 끝에 있습니다. 즉, 배열의 push 메소드를 사용하여 구현을 시뮬레이션할 수 있습니다.

구현:

/**
 * 将元素送入栈，放置于数组的最后一位
 * @param {Any} element 接受的元素，不限制类型
 */
this.push = function(element) {
 items.push(element);
};

로그인 후 복사

팝방식 구현

설명: 스택의 최상위 요소를 팝하고 동시에 팝된 값을 반환해야 합니다. 배열의 pop 메소드를 사용하여 구현을 시뮬레이션할 수 있습니다.
구현:

/**
 * 弹出栈顶元素
 * @return {Any} 返回被弹出的值
 */
this.pop = function() {
 return items.pop();
};

로그인 후 복사

Peek 방식 구현
참고: 배열 길이를 사용하여 스택의 최상위 요소를 볼 수 있습니다.
구현:

/**
 * 查看栈顶元素
 * @return {Any} 返回栈顶元素
 */
this.peek = function() {
 return items[items.length - 1];
}

로그인 후 복사

다른 방법의 구현
참고: 처음 3개는 스택 방법의 핵심이며 나머지 방법은 여기에 한 번에 나열됩니다. 왜냐하면 아래에서 논의할 큐가 이 부분과 크게 겹칠 것이기 때문이다.
구현:

/**
 * 确定栈是否为空
 * @return {Boolean} 若栈为空则返回true,不为空则返回false
 */
this.isAmpty = function() {
 return items.length === 0
};

/**
 * 清空栈中所有内容
 */
this.clear = function() {
 items = [];
};

/**
 * 返回栈的长度
 * @return {Number} 栈的长度
 */
this.size = function() {
 return items.length;
};

/**
 * 以字符串显示栈中所有内容
 */
this.print = function() {
 console.log(items.toString());
};

로그인 후 복사

실습

스택을 실제로 적용할 수 있는 곳은 많습니다. 책에는 10진수를 2진수로 변환하는 함수가 있습니다. (바이너리 계산법을 모르시면 바이두를 이용하시면 됩니다.) 다음은 해당 함수의 소스코드입니다.
변환할 숫자를 입력하고 연속적으로 2로 나누어 반올림하는 것이 원칙입니다. 그리고 마지막으로 while 루프를 사용하여 스택의 모든 숫자를 출력용 문자열로 연결합니다.

/**
 * 将10进制数字转为2进制数字
 * @param {Number} decNumber 要转换的10进制数字
 * @return {Number}      转换后的2进制数字
 */
function divideBy2(decNumber) {

 var remStack = new Stack(),
  rem,
  binaryString = '';

 while (decNumber > 0) {
  rem = Math.floor(decNumber % 2);
  remStack.push(rem);
  decNumber = Math.floor(decNumber / 2);
 }

 while (!remStack.isAmpty()) {
  binaryString += remStack.pop().toString();
 }

 return binaryString;
};

로그인 후 복사

이쯤 되면 스택에 대한 연구가 끝나게 됩니다. 소스코드에는 댓글이 많기 때문에 소스코드 내용은 여기에 올리지 않겠습니다.

대기열

큐와 스택은 매우 유사한 데이터 구조입니다. 차이점은 큐가 선입선출(FIFO: First In First Out)이라는 것입니다.
예: 기차역에서 표를 사기 위해 줄을 설 때 먼저 오십시오. (줄서서 뛰어다니는 사람은 카운트 안됨) 이해하기 쉽죠~

JavaScipt에서 대기열 구현

큐의 구현은 스택과 매우 유사합니다. 첫 번째는 여전히 생성자입니다.

/**
 * 队列构造函数
 */
function Queue() {
 var items = [];
}

로그인 후 복사

대기열에는 다음 메서드가 있어야 합니다.
enqueue(element(s)): 대기열 끝에 여러 항목 추가
dequeue(): 대기열의 첫 번째 항목(즉, 최상위 항목)을 제거합니다
front(): 가장 최근에 추가된 대기열의 첫 번째 요소를 반환합니다
나머지 방법은 queue와 동일합니다

Enqueue 방식 구현

설명: 대기열 끝에 여러 항목을 추가합니다.
구현:

/**
 * 将元素推入队列尾部
 * @param {Any} ele 要推入队列的元素
 */
this.enqueue = function(ele) {
 items.push(ele);
};

로그인 후 복사

Dequeue 방식 구현

설명: 대기열에서 첫 번째 항목을 제거합니다.
구현:

/**
 * 将队列中第一个元素弹出
 * @return {Any} 返回被弹出的元素
 */
this.dequeue = function() {
 return items.shift()
};

로그인 후 복사

프론트 방식 구현

설명: 가장 최근에 추가된 대기열의 첫 번째 요소를 반환합니다.
구현:

/**
 * 查看队列的第一个元素
 * @return {Any} 返回队列中第一个元素
 */
this.front = function() {
 return items[0];
};

로그인 후 복사

以上的三个方法，就是队列这种数据结构的核心方法了。其实很好理解的。

实际应用
书上的是个击鼓传花的小游戏。原理就是循环到相应位置时，队列弹出那个元素。最后留下的就是赢家。
源代码如下:

/**
 * 击鼓传花的小游戏
 * @param {Array} nameList 参与人员列表
 * @param {Number} num   在循环中要被弹出的位置
 * @return {String}     返回赢家(也就是最后活下来的那个)
 */
function hotPotato(nameList, num) {
 var queue = new Queue();

 for (var i = 0; i < nameList.length; i++) {
  queue.enqueue(nameList[i]);
 }

 var eliminated = '';

 while (queue.size() > 1) {
  for (var i = 0; i < num; i++) {
   queue.enqueue(queue.dequeue());
  }

  eliminated = queue.dequeue();
  console.log(eliminated + " Get out!")
 }

 return queue.dequeue()
}

로그인 후 복사

队列的学习到此就告一段落了。下一期将讲述另外一种数据结构: 链表。

感想

很多时候看书，直接看算法导论或者一些数据结构的书，都是很迷糊的。后来才发现，看书从自己能看懂的开始，由浅入深才是适合自己的学习方式。