[javascript] JavaScript로 스택과 큐를 어떻게 구현합니까?

JavaScript에서 스택 및 큐를 구현하는 가장 좋은 방법은 무엇입니까?

Shunting-yard 알고리즘을 찾고 있는데 이러한 데이터 구조가 필요합니다.

답변

var stack = [];
stack.push(2);       // stack is now [2]
stack.push(5);       // stack is now [2, 5]
var i = stack.pop(); // stack is now [2]
alert(i);            // displays 5

var queue = [];
queue.push(2);         // queue is now [2]
queue.push(5);         // queue is now [2, 5]
var i = queue.shift(); // queue is now [5]
alert(i);              // displays 2

” 당신이 모르는 9 개의 자바 스크립트 팁 에서 발췌 “

답변

Javascript에는 일반 Javascript 배열 객체에서 작동하는 push 및 pop 메소드가 있습니다.

대기열은 여기를 참조하십시오.

http://safalra.com/web-design/javascript/queues/

배열 객체의 push 및 shift 메소드 또는 unshift 및 pop 메소드를 사용하여 JavaScript로 큐를 구현할 수 있습니다. 이 방법은 대기열을 구현하는 간단한 방법이지만 대형 대기열의 경우 비효율적입니다. 메서드가 배열에서 작동하기 때문에 shift 및 unshift 메서드는 호출 될 때마다 배열의 모든 요소를 이동합니다.

Queue.js는 dequeue 함수가 상각 된 일정한 시간에 실행되는 JavaScript를위한 간단하고 효율적인 큐 구현입니다. 결과적으로 더 큰 대기열의 경우 배열을 사용하는 것보다 훨씬 빠를 수 있습니다.

답변

배열.

스택:

var stack = [];

//put value on top of stack
stack.push(1);

//remove value from top of stack
var value = stack.pop();

열:

var queue = [];

//put value on end of queue
queue.push(1);

//Take first value from queue
var value = queue.shift();

답변

자신 만의 데이터 구조를 만들고 싶다면 자신 만의 데이터 구조를 만들 수 있습니다.

var Stack = function(){
  this.top = null;
  this.size = 0;
};

var Node = function(data){
  this.data = data;
  this.previous = null;
};

Stack.prototype.push = function(data) {
  var node = new Node(data);

  node.previous = this.top;
  this.top = node;
  this.size += 1;
  return this.top;
};

Stack.prototype.pop = function() {
  temp = this.top;
  this.top = this.top.previous;
  this.size -= 1;
  return temp;
};

그리고 대기열 :

var Queue = function() {
  this.first = null;
  this.size = 0;
};

var Node = function(data) {
  this.data = data;
  this.next = null;
};

Queue.prototype.enqueue = function(data) {
  var node = new Node(data);

  if (!this.first){
    this.first = node;
  } else {
    n = this.first;
    while (n.next) {
      n = n.next;
    }
    n.next = node;
  }

  this.size += 1;
  return node;
};

Queue.prototype.dequeue = function() {
  temp = this.first;
  this.first = this.first.next;
  this.size -= 1;
  return temp;
};

답변

내 구현 Stack및 Queue사용Linked List

// Linked List
function Node(data) {
  this.data = data;
  this.next = null;
}

// Stack implemented using LinkedList
function Stack() {
  this.top = null;
}

Stack.prototype.push = function(data) {
  var newNode = new Node(data);

  newNode.next = this.top; //Special attention
  this.top = newNode;
}

Stack.prototype.pop = function() {
  if (this.top !== null) {
    var topItem = this.top.data;
    this.top = this.top.next;
    return topItem;
  }
  return null;
}

Stack.prototype.print = function() {
  var curr = this.top;
  while (curr) {
    console.log(curr.data);
    curr = curr.next;
  }
}

// var stack = new Stack();
// stack.push(3);
// stack.push(5);
// stack.push(7);
// stack.print();

// Queue implemented using LinkedList
function Queue() {
  this.head = null;
  this.tail = null;
}

Queue.prototype.enqueue = function(data) {
  var newNode = new Node(data);

  if (this.head === null) {
    this.head = newNode;
    this.tail = newNode;
  } else {
    this.tail.next = newNode;
    this.tail = newNode;
  }
}

Queue.prototype.dequeue = function() {
  var newNode;
  if (this.head !== null) {
    newNode = this.head.data;
    this.head = this.head.next;
  }
  return newNode;
}

Queue.prototype.print = function() {
  var curr = this.head;
  while (curr) {
    console.log(curr.data);
    curr = curr.next;
  }
}

var queue = new Queue();
queue.enqueue(3);
queue.enqueue(5);
queue.enqueue(7);
queue.print();
queue.dequeue();
queue.dequeue();
queue.print();

스 니펫 확장

답변

Javascript 배열 shift ()는 특히 많은 요소를 보유 할 때 느립니다. 상각 된 O (1) 복잡도로 대기열을 구현하는 두 가지 방법을 알고 있습니다.

첫 번째는 순환 버퍼와 테이블 이중화를 사용하는 것입니다. 나는 이것을 전에 구현했다. 내 소스 코드는 https://github.com/kevyuu/rapid-queue에서 볼 수 있습니다.

두 번째 방법은 두 개의 스택을 사용하는 것입니다. 이것은 두 개의 스택이있는 대기열의 코드입니다.

function createDoubleStackQueue() {
var that = {};
var pushContainer = [];
var popContainer = [];

function moveElementToPopContainer() {
    while (pushContainer.length !==0 ) {
        var element = pushContainer.pop();
        popContainer.push(element);
    }
}

that.push = function(element) {
    pushContainer.push(element);
};

that.shift = function() {
    if (popContainer.length === 0) {
        moveElementToPopContainer();
    }
    if (popContainer.length === 0) {
        return null;
    } else {
        return popContainer.pop();
    }
};

that.front = function() {
    if (popContainer.length === 0) {
        moveElementToPopContainer();
    }
    if (popContainer.length === 0) {
        return null;
    }
    return popContainer[popContainer.length - 1];
};

that.length = function() {
    return pushContainer.length + popContainer.length;
};

that.isEmpty = function() {
    return (pushContainer.length + popContainer.length) === 0;
};

return that;}

이것은 jsPerf를 사용한 성능 비교입니다.

CircularQueue.shift () 및 Array.shift ()

http://jsperf.com/rapidqueue-shift-vs-array-shift

보시다시피 큰 데이터 세트의 경우 훨씬 빠릅니다.

답변

Javascript에서 스택 및 큐를 구현할 수있는 몇 가지 방법이 있습니다. 위의 답변 대부분은 상당히 얕은 구현이며 es6의 새로운 구문 기능을 사용하여 더 읽기 쉽고 강력한 것을 구현하려고합니다.

스택 구현은 다음과 같습니다.

class Stack {
  constructor(...items){
    this._items = []

    if(items.length>0)
      items.forEach(item => this._items.push(item) )

  }

  push(...items){
    //push item to the stack
     items.forEach(item => this._items.push(item) )
     return this._items;

  }

  pop(count=0){
    //pull out the topmost item (last item) from stack
    if(count===0)
      return this._items.pop()
     else
       return this._items.splice( -count, count )
  }

  peek(){
    // see what's the last item in stack
    return this._items[this._items.length-1]
  }

  size(){
    //no. of items in stack
    return this._items.length
  }

  isEmpty(){
    // return whether the stack is empty or not
    return this._items.length==0
  }

  toArray(){
    return this._items;
  }
}

그리고 이것이 스택을 사용하는 방법입니다.

let my_stack = new Stack(1,24,4);
// [1, 24, 4]
my_stack.push(23)
//[1, 24, 4, 23]
my_stack.push(1,2,342);
//[1, 24, 4, 23, 1, 2, 342]
my_stack.pop();
//[1, 24, 4, 23, 1, 2]
my_stack.pop(3)
//[1, 24, 4]
my_stack.isEmpty()
// false
my_stack.size();
//3

이 구현에 대한 자세한 설명과 추가 개선 방법을 보려면 여기를 참조하십시오. http://jschap.com/data-structures-in-javascript-stack/

es6의 큐 구현 코드는 다음과 같습니다.

class Queue{
 constructor(...items){
   //initialize the items in queue
   this._items = []
   // enqueuing the items passed to the constructor
   this.enqueue(...items)
 }

  enqueue(...items){
    //push items into the queue
    items.forEach( item => this._items.push(item) )
    return this._items;
  }

  dequeue(count=1){
    //pull out the first item from the queue
    this._items.splice(0,count);
    return this._items;
  }

  peek(){
    //peek at the first item from the queue
    return this._items[0]
  }

  size(){
    //get the length of queue
    return this._items.length
  }

  isEmpty(){
    //find whether the queue is empty or no
    return this._items.length===0
  }
}

이 구현을 사용하는 방법은 다음과 같습니다.

let my_queue = new Queue(1,24,4);
// [1, 24, 4]
my_queue.enqueue(23)
//[1, 24, 4, 23]
my_queue.enqueue(1,2,342);
//[1, 24, 4, 23, 1, 2, 342]
my_queue.dequeue();
//[24, 4, 23, 1, 2, 342]
my_queue.dequeue(3)
//[1, 2, 342]
my_queue.isEmpty()
// false
my_queue.size();
//3

이러한 데이터 구조의 구현 방법과 추가 개선 방법에 대한 전체 자습서를 보려면 jschap.com의 ‘자바 스크립트의 데이터 구조로 재생’시리즈를 살펴보십시오. 다음은 대기열에 대한 링크입니다-http: //jschap.com/playing-data-structures-javascript-queues/