JavaScript의 스택 및 큐에 대한 알고리즘 분석

이 기사의 내용은 JavaScript의 스택 및 큐 알고리즘 분석에 관한 것입니다. 이는 특정 참고 가치가 있으므로 도움이 될 수 있습니다.

1. 데이터 구조를 이해하세요

데이터 구조란 무엇인가요? Wikipedia의 설명은 다음과 같습니다

데이터 구조는 컴퓨터가 데이터를 저장하고 구성하는 방식입니다.

데이터 구조는 인터페이스 또는 캡슐화를 의미합니다. 데이터 구조는 두 기능 간의 인터페이스로 볼 수도 있고 데이터 유형의 결합으로 구성된 저장소로 볼 수도 있습니다. 콘텐츠 액세스 방법 캡슐화

우리는 일상적인 코딩에서 데이터 구조를 사용합니다. 왜냐하면 배열은 가장 간단한 메모리 데이터 구조이기 때문입니다. 다음은 일반적인 데이터 구조입니다

• Array(Array)

• Stack(Stack)

• Queue

• Linked List

• Tree

• Graph

• Heap

• Hash

스택과 큐에 대해 알아봅시다..

2. 스택

2.1 스택 데이터 구조

스택은 LIFO(후입선출) 원칙을 따르는 정렬된 컬렉션입니다. 새로 추가되거나 삭제될 요소는 스택의 동일한 끝(스택 상단이라고 함)에 저장되고 다른 쪽 끝은 스택의 하단이라고 합니다. 스택에서 새 요소는 스택 상단 근처에 있고 이전 요소는 하단 근처에 있습니다.

인생의 사물에 비유: 책이나 접시를 함께 밀어 넣은 더미

2.2 스택 구현

일반적인 스택은 일반적으로 다음 방법을 사용합니다.

푸시를 눌러 하나(또는 여러 개)를 추가합니다. 스택의 상단

pop은 스택의 상단 요소를 오버플로하고 동시에 제거된 요소를 반환합니다.

peek는 스택을 수정하지 않고 스택의 상단 요소를 반환합니다.

isEmpty는 스택에 요소가 없으면 true를 반환합니다. stack, 그렇지 않으면 false를 반환

size return 스택의 요소 수

clear 스택 지우기

class Stack {
  constructor() {
    this._items = []; // 储存数据
  }
  // 向栈内压入一个元素
  push(item) {
    this._items.push(item);
  }
  // 把栈顶元素弹出
  pop() {
    return this._items.pop();
  }
  // 返回栈顶元素
  peek() {
    return this._items[this._items.length - 1];
  }
  // 判断栈是否为空
  isEmpty() {
    return !this._items.length;
  }
  // 栈元素个数
  size() {
    return this._items.length;
  }
  // 清空栈
  clear() {
    this._items = [];
  }
}

이제 데이터 구조에서 스택이 무엇인지 되돌아보고 생각해 봅시다.

갑자기 나는 그것이 그다지 마법적인 것이 아니라 단지 원본 데이터를 캡슐화한 것에 불과하다는 것을 발견했습니다. 캡슐화의 결과는 다음과 같습니다. 내부 요소는 신경 쓰지 않고 스택의 최상위 요소만 작동합니다. 이 경우 코딩을 더 쉽게 제어할 수 있습니다.

2.3 스택의 응용

(1) 십진수를 임의의 진수로 변환

요구 사항: 함수가 주어졌을 때 목표 값과 진수를 입력하고 해당하는 진수(최대 16진수)를 출력합니다.

baseConverter(10, 2) ==> 1010
baseConverter(30, 16) ==> 1E

분석 : 진수변환의 본질은 목표값을 기준값으로 한 번에 나누어서 반올림한 값이 새로운 목표값이 되고, 목표값이 0보다 작아질 때까지 나머지를 기록하고 마지막으로 나머지를 역순으로 합치는 것입니다. , 캔입니다. 스택을 사용하여 나머지를 기록하고 스택에 밀어넣고 결합할 때 튀어나옵니다

// 进制转换
function baseConverter(delNumber, base) {
  const stack = new Stack();
  let rem = null;
  let ret = [];
  // 十六进制中需要依次对应A~F
  const digits = '0123456789ABCDEF';

  while (delNumber > 0) {
    rem = Math.floor(delNumber % base);
    stack.push(rem);
    delNumber = Math.floor(delNumber / base);
  }

  while (!stack.isEmpty()) {
    ret.push(digits[stack.pop()]);
  }

  return ret.join('');
}

console.log(baseConverter(100345, 2)); //输出11000011111111001
console.log(baseConverter(100345, 8)); //输出303771
console.log(baseConverter(100345, 16)); //输出187F9

(2) 역 폴란드식 계산

요구 사항: 역 폴란드 식, 접미사 식이라고도 하며 복잡한 형식으로 변환합니다. 표현식을 간단한 연산에 의존하여 계산 결과를 얻는 표현식으로, 예를 들어 (a+b)*(c+d)는 a b + c d + *(a+b)*(c+d)转换为a b + c d + *

["4", "13", "5", "/", "+"] ==> (4 + (13 / 5)) = 6
["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
==> ((10 * (6 / ((9 + 3) * -11))) + 17) + 5

分析: 以符号为触发节点，一旦遇到符号，就将符号前两个元素按照该符号运算，并将新的结果入栈，直到栈内仅一个元素

function isOperator(str) {
  return ['+', '-', '*', '/'].includes(str);
}
// 逆波兰表达式计算
function clacExp(exp) {
  const stack = new Stack();
  for (let i = 0; i <p><strong>（3）利用普通栈实现一个有<code>min</code>方法的栈</strong></p><p><strong>思路:</strong> 使用两个栈来存储数据，其中一个命名为<code>dataStack</code>，专门用来存储数据，另一个命名为<code>minStack</code>，专门用来存储栈里最小的数据。始终保持两个栈中的元素个数相同，压栈时判别压入的元素与<code>minStack</code>栈顶元素比较大小，如果比栈顶元素小，则直接入栈，否则复制栈顶元素入栈；弹出栈顶时，两者均弹出即可。这样<code>minStack</code>的栈顶元素始终为最小值。</p><pre class="brush:php;toolbar:false">class MinStack {
  constructor() {
    this._dataStack = new Stack();
    this._minStack = new Stack();
  }

  push(item) {
    this._dataStack.push(item);
    // 为空或入栈元素小于栈顶元素，直接压入该元素
    if (this._minStack.isEmpty() || this._minStack.peek() > item) {
      this._minStack.push(item);
    } else {
      this._minStack.push(this._minStack.peek());
    }
  }

  pop() {
    this._dataStack.pop();
    return this._minStack.pop();
  }

  min() {
    return this._minStack.peek();
  }
}

const minstack = new MinStack();

minstack.push(3);
minstack.push(4);
minstack.push(8);
console.log(minstack.min()); // 3
minstack.push(2);
console.log(minstack.min()); // 2

三、队列

3.1 队列数据结构

队列是遵循先进先出（FIFO，也称为先来先服务）原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾

类比：日常生活中的购物排队

3.2 队列的实现

普通的队列常用的有以下几个方法：

• enqueue 向队列尾部添加一个(或多个)新的项

• dequeue 移除队列的第一(即排在队列最前面的)项，并返回被移除的元素

• head 返回队列第一个元素，队列不做任何变动

• tail

  class Queue {
    constructor() {
      this._items = [];
    }
  
    enqueue(item) {
      this._items.push(item);
    }
  
    dequeue() {
      return this._items.shift();
    }
  
    head() {
      return this._items[0];
    }
  
    tail() {
      return this._items[this._items.length - 1];
    }
  
    isEmpty() {
      return !this._items.length;
    }
  
    size() {
      return this._items.length;
    }
  
    clear() {
      this._items = [];
    }
  }

  로 변환됩니다. 🎜분석: 🎜 기호를 트리거 노드로 사용합니다. 기호가 발견되면 기호의 처음 두 요소가 기호에 따라 작동되고 스택에 요소가 하나만 있을 때까지 새 결과가 스택에 푸시됩니다. 🎜

  // 创建一个长度为100的数组
  const arr_100 = Array.from({ length: 100 }, (_, i) => i*i);
  
  function delRing(list) {
    const queue = new Queue();
    list.forEach(e => { queue.enqueue(e); });
    
    let index = 0;
    while (queue.size() !== 1) {
      const item = queue.dequeue();
      index += 1;
      if (index % 3 !== 0) {
        queue.enqueue(item);
      }
    }
  
    return queue.tail();
  }
  
  console.log(delRing(arr_100)); // 8100 此时index=297

  🎜🎜 (3) 일반 스택을 사용하여 min 메서드로 스택 구현 🎜🎜🎜🎜 아이디어: 🎜 두 개의 스택을 사용하여 데이터를 저장하고 그 중 하나의 이름은 dataStack code>는 데이터를 저장하는 데 특별히 사용되며 다른 하나는 <code>minStack이라는 이름으로 스택에서 가장 작은 데이터를 저장하는 데 특별히 사용됩니다. 두 스택의 요소 수를 항상 동일하게 유지하세요. 스택을 푸시할 때 푸시된 요소의 크기를 minStack 스택의 맨 위에 있는 요소와 비교하세요. 스택의 맨 위에서 스택으로 직접 푸시하고, 그렇지 않으면 스택을 복사합니다. 맨 위 요소가 스택에서 팝되면 두 요소가 모두 팝될 수 있습니다. 이런 방식으로 minStack의 최상위 요소는 항상 최소값입니다. 🎜

  function fibonacci(n) {
      const queue = new Queue();
      queue.enqueue(1);
      queue.enqueue(1);
      
      let index = 0;
      while(index 🎜🎜3. 대기열🎜🎜🎜🎜3.1 대기열 데이터 구조🎜🎜 대기열은 선입선출(FIFO, 선착순이라고도 함) 원칙을 따르는 정렬된 항목 집합입니다. . 큐는 꼬리에 새 요소를 추가하고 맨 위에서 요소를 제거합니다. 가장 최근에 추가된 요소는 대기열 끝에 있어야 합니다 🎜🎜<img src="https://img.php.cn//upload/image/578/667/838/1547602503534750.png" title="1547602503534750.png " alt="JavaScript의 스택 및 큐에 대한 알고리즘 분석">🎜🎜🎜비유: 일상생활의 쇼핑 대기열🎜🎜3.2 대기열 구현🎜🎜공통 대기열은 일반적으로 다음 방법을 사용합니다.🎜🎜🎜🎜<code>enqueue code> 추가 대기열 끝에 하나 이상의 새 항목 🎜🎜🎜🎜<code>dequeue</code> 대기열의 첫 번째 항목(즉, 대기열의 맨 앞부분)을 제거하고 제거된 항목 요소를 반환합니다 🎜🎜 🎜🎜<code>head</code> 대기열을 변경하지 않고 대기열의 첫 번째 요소를 반환합니다.🎜🎜🎜🎜<code>tail</code> 대기열을 변경하지 않고 대기열의 마지막 요소를 반환합니다. 🎜</code>

• isEmpty 队列内无元素返回true，否则返回false

• size 返回队列内元素个数

• clear 清空队列

class Queue {
  constructor() {
    this._items = [];
  }

  enqueue(item) {
    this._items.push(item);
  }

  dequeue() {
    return this._items.shift();
  }

  head() {
    return this._items[0];
  }

  tail() {
    return this._items[this._items.length - 1];
  }

  isEmpty() {
    return !this._items.length;
  }

  size() {
    return this._items.length;
  }

  clear() {
    this._items = [];
  }
}

与栈类比，栈仅能操作其头部，队列则首尾均能操作，但仅能在头部出尾部进。当然，也印证了上面的话：栈和队列并不关心其内部元素细节，也无法直接操作非首尾元素。

3.3 队列的应用

（1）约瑟夫环（普通模式）

要求: 有一个数组a[100]存放0~99；要求每隔两个数删掉一个数，到末尾时循环至开头继续进行，求最后一个被删掉的数。

分析: 按数组创建队列，依次判断元素是否满足为指定位置的数，如果不是则enqueue到尾部，否则忽略，当仅有一个元素时便输出

// 创建一个长度为100的数组
const arr_100 = Array.from({ length: 100 }, (_, i) => i*i);

function delRing(list) {
  const queue = new Queue();
  list.forEach(e => { queue.enqueue(e); });
  
  let index = 0;
  while (queue.size() !== 1) {
    const item = queue.dequeue();
    index += 1;
    if (index % 3 !== 0) {
      queue.enqueue(item);
    }
  }

  return queue.tail();
}

console.log(delRing(arr_100)); // 8100 此时index=297

（2）菲波那切数列（普通模式）

要求: 使用队列计算斐波那契数列的第n项
分析: 斐波那契数列的前两项固定为1，后面的项为前两项之和，依次向后，这便是斐波那契数列。

function fibonacci(n) {
    const queue = new Queue();
    queue.enqueue(1);
    queue.enqueue(1);
    
    let index = 0;
    while(index <p><strong>（3）用队列实现一个栈</strong></p><p><strong>要求:</strong> 用两个队列实现一个栈<br><strong>分析:</strong> 使用队列实现栈最主要的是在队列中找到栈顶元素并对其操作。具体的思路如下：</p><ol class=" list-paddingleft-2">
<li><p>两个队列，一个备份队列<code>emptyQueue</code>，一个是数据队列<code>dataQueue</code>；</p></li>
<li><p>在确认栈顶时，依次<code>dequeue</code>至备份队列，置换备份队列和数据队列的引用即可</p></li>
</ol><pre class="brush:php;toolbar:false">class QueueStack {
  constructor() {
    this.queue_1 = new Queue();
    this.queue_2 = new Queue();
    this._dataQueue = null; // 放数据的队列
    this._emptyQueue = null; // 空队列,备份使用
  }

  // 确认哪个队列放数据,哪个队列做备份空队列
  _initQueue() {
    if (this.queue_1.isEmpty() && this.queue_2.isEmpty()) {
      this._dataQueue = this.queue_1;
      this._emptyQueue = this.queue_2;
    } else if (this.queue_1.isEmpty()) {
      this._dataQueue = this.queue_2;
      this._emptyQueue = this.queue_1;
    } else {
      this._dataQueue = this.queue_1;
      this._emptyQueue = this.queue_2;
    }
  };

  push(item) {
    this.init_queue();
    this._dataQueue.enqueue(item);
  };

  peek() {
    this.init_queue();
    return this._dataQueue.tail();
  }

  pop() {
    this.init_queue();
    while (this._dataQueue.size() > 1) {
      this._emptyQueue.enqueue(this._dataQueue.dequeue());
    }
    return this._dataQueue.dequeue();
  };
};

学习了栈和队列这类简单的数据结构，我们会发现。数据结构并没有之前想象中那么神秘，它们只是规定了这类数据结构的操作方式：栈只能对栈顶进行操作，队列只能在尾部添加在头部弹出；且它们不关心内部的元素状态。

위 내용은 JavaScript의 스택 및 큐에 대한 알고리즘 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!