JavaScript에서 스택과 큐를 구현하려면 어떻게 해야 합니까?

JavaScript에서 스택과 큐를 구현하려면 어떻게 해야 합니까?

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

션팅 야드 알고리즘을 사용하려고 하는데 이 데이터 구조가 필요해요

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 힌트(모르실 수 있는9가지 JavaScript 힌트)"에서 발췌했습니다.

Javascript에는 일반 Javascript 배열 객체에서 작동하는 푸시 및 팝 메서드가 있습니다.

큐에 대해서는, 여기를 참조해 주세요.

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

큐는 배열 객체의 푸시 및 시프트 메서드 또는 언시프트 및 팝 메서드를 사용하여 JavaScript에서 구현할 수 있습니다.이것은 큐를 구현하는 간단한 방법이지만, 대규모 큐에서는 매우 비효율적입니다.이러한 메서드는 어레이에서 동작하기 때문에 시프트 메서드와 언시프트 메서드는 호출될 때마다 어레이 내의 모든 요소를 이동합니다.

Queue.js는 JavaScript를 위한 단순하고 효율적인 큐 구현으로, dequeue 함수는 상각된 상수 시간에 실행됩니다.따라서 큐가 클수록 어레이를 사용하는 것보다 훨씬 빠릅니다.

어레이

스택:

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;
};

링크 리스트를 사용한 스택과 큐의 실장을 다음에 나타냅니다.

// 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 에서 보실 수 있습니다.

두 번째 방법은 2개의 스택을 사용하는 것입니다.이것은 2개의 스택을 가진 큐의 코드입니다.

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를 사용한 퍼포먼스 비교입니다.

Circular Queue.shift()와 어레이.시프트()

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

보다시피 대규모 데이터셋을 사용하면 훨씬 더 빠릅니다.

스택의 실장은 다른 답변에서 설명한 것처럼 단순합니다.

그러나 이 스레드에서 javascript의 큐 구현에 대한 만족스러운 답변을 찾을 수 없어서 직접 만들었습니다.

이 스레드에는 다음 3가지 유형의 솔루션이 있습니다.

• - ('-"를 사용합니다.array.shift()을 사용하다
• 링크 리스트 - O(1)입니다만, 각 요소에 오브젝트를 사용하는 것은 조금 과합니다.특히 수가 많고 숫자가 저장되는 것과 같이 작은 경우에는 더욱 그렇습니다.
• 지연된 시프트 배열 - 인덱스를 배열과 연결하는 것으로 구성됩니다.요소가 큐에서 해제되면 인덱스는 앞으로 이동합니다.인덱스가 어레이의 중앙에 도달하면 어레이가 두 개로 분할되어 첫 번째 절반이 제거됩니다.

지연된 시프트 어레이는 가장 만족스러운 해결책이지만, 여전히 모든 것을 하나의 큰 연속 어레이에 저장하기 때문에 문제가 발생할 수 있습니다.또한 어레이를 슬라이스하면 어플리케이션이 불안정해집니다.

소규모 어레이의 링크 리스트를 사용해 실장했습니다(각각 최대 1000개의 요소).어레이는 슬라이스되지 않는 것을 제외하고 지연된 시프트 어레이와 같이 동작합니다.어레이 내의 모든 요소를 제거하면 어레이는 단순히 폐기됩니다.

패키지는 기본 FIFO 기능으로 npm에 있습니다.최근에 push 했습니다.코드는 두 부분으로 분할됩니다.

여기 첫 번째 부분이 있습니다.

/** Queue contains a linked list of Subqueue */
class Subqueue <T> {
  public full() {
    return this.array.length >= 1000;
  }

  public get size() {
    return this.array.length - this.index;
  }

  public peek(): T {
    return this.array[this.index];
  }

  public last(): T {
    return this.array[this.array.length-1];
  }

  public dequeue(): T {
    return this.array[this.index++];
  }

  public enqueue(elem: T) {
    this.array.push(elem);
  }

  private index: number = 0;
  private array: T [] = [];

  public next: Subqueue<T> = null;
}

여기 .Queue 링크:

class Queue<T> {
  get length() {
    return this._size;
  }

  public push(...elems: T[]) {
    for (let elem of elems) {
      if (this.bottom.full()) {
        this.bottom = this.bottom.next = new Subqueue<T>();
      }
      this.bottom.enqueue(elem);
    }

    this._size += elems.length;
  }

  public shift(): T {
    if (this._size === 0) {
      return undefined;
    }

    const val = this.top.dequeue();
    this._size--;
    if (this._size > 0 && this.top.size === 0 && this.top.full()) {
      // Discard current subqueue and point top to the one after
      this.top = this.top.next;
    }
    return val;
  }

  public peek(): T {
    return this.top.peek();
  }

  public last(): T {
    return this.bottom.last();
  }

  public clear() {
    this.bottom = this.top = new Subqueue();
    this._size = 0;
  }

  private top: Subqueue<T> = new Subqueue();
  private bottom: Subqueue<T> = this.top;
  private _size: number = 0;
}

을 입력합니다( : XES6 javascript 。

컨셉에 따라 독자적인 커스터마이즈 클래스를 사용할 수 있습니다.여기에는 작업을 수행하는 데 사용할 수 있는 코드 스니펫입니다.

/*
*   Stack implementation in JavaScript
*/



function Stack() {
  this.top = null;
  this.count = 0;

  this.getCount = function() {
    return this.count;
  }

  this.getTop = function() {
    return this.top;
  }

  this.push = function(data) {
    var node = {
      data: data,
      next: null
    }

    node.next = this.top;
    this.top = node;

    this.count++;
  }

  this.peek = function() {
    if (this.top === null) {
      return null;
    } else {
      return this.top.data;
    }
  }

  this.pop = function() {
    if (this.top === null) {
      return null;
    } else {
      var out = this.top;
      this.top = this.top.next;
      if (this.count > 0) {
        this.count--;
      }

      return out.data;
    }
  }

  this.displayAll = function() {
    if (this.top === null) {
      return null;
    } else {
      var arr = new Array();

      var current = this.top;
      //console.log(current);
      for (var i = 0; i < this.count; i++) {
        arr[i] = current.data;
        current = current.next;
      }

      return arr;
    }
  }
}

이를 확인하려면 콘솔을 사용하여 다음 행을 하나씩 사용해 보십시오.

>> var st = new Stack();

>> st.push("BP");

>> st.push("NK");

>> st.getTop();

>> st.getCount();

>> st.displayAll();

>> st.pop();

>> st.displayAll();

>> st.getTop();

>> st.peek();

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에서 'Javascript에서 데이터 구조를 재생하기' 시리즈를 참조하십시오.여기 큐 링크가 있습니다.http://jschap.com/playing-data-structures-javascript-queues/

스택과 큐를 구현하는 가장 깨끗한 방법은 양끝에서 추가와 삭제를 허용하는 컨테이너를 사용하여 Javascript의 심플한 어레이를 통해 실행할 수 있는 한끝의 기능을 제한하는 것입니다.

// 캡슐화 중 스택컨테이너에서 사용되는 문

// Allow push and pop from the same end
array.push(element);
array.pop();

// 캡슐화 중 큐컨테이너에서 사용되는 문

// Allow push and pop from different ends
array.push(element);
array.shift();

또는 2개의 어레이를 사용하여 큐 데이터 구조를 구현할 수 있습니다.

var temp_stack = new Array();
var stack = new Array();

temp_stack.push(1);
temp_stack.push(2);
temp_stack.push(3);

여기서 요소를 팝하면 출력은 3, 2, 1이 됩니다.다만, 다음과 같은 FIFO 구조가 필요합니다.

stack.push(temp_stack.pop());
stack.push(temp_stack.pop());
stack.push(temp_stack.pop());

stack.pop(); //Pop out 1
stack.pop(); //Pop out 2
stack.pop(); //Pop out 3

/*------------------------------------------------------------------ 
 Defining Stack Operations using Closures in Javascript, privacy and
 state of stack operations are maintained

 @author:Arijt Basu
 Log: Sun Dec 27, 2015, 3:25PM
 ------------------------------------------------------------------- 
 */
var stackControl = true;
var stack = (function(array) {
        array = [];
        //--Define the max size of the stack
        var MAX_SIZE = 5;

        function isEmpty() {
            if (array.length < 1) console.log("Stack is empty");
        };
        isEmpty();

        return {

            push: function(ele) {
                if (array.length < MAX_SIZE) {
                    array.push(ele)
                    return array;
                } else {
                    console.log("Stack Overflow")
                }
            },
            pop: function() {
                if (array.length > 1) {
                    array.pop();
                    return array;
                } else {
                    console.log("Stack Underflow");
                }
            }

        }
    })()
    // var list = 5;
    // console.log(stack(list))
if (stackControl) {
    console.log(stack.pop());
    console.log(stack.push(3));
    console.log(stack.push(2));
    console.log(stack.pop());
    console.log(stack.push(1));
    console.log(stack.pop());
    console.log(stack.push(38));
    console.log(stack.push(22));
    console.log(stack.pop());
    console.log(stack.pop());
    console.log(stack.push(6));
    console.log(stack.pop());
}
//End of STACK Logic

/* Defining Queue operations*/

var queue = (function(array) {
    array = [];
    var reversearray;
    //--Define the max size of the stack
    var MAX_SIZE = 5;

    function isEmpty() {
        if (array.length < 1) console.log("Queue is empty");
    };
    isEmpty();

    return {
        insert: function(ele) {
            if (array.length < MAX_SIZE) {
                array.push(ele)
                reversearray = array.reverse();
                return reversearray;
            } else {
                console.log("Queue Overflow")
            }
        },
        delete: function() {
            if (array.length > 1) {
                //reversearray = array.reverse();
                array.pop();
                return array;
            } else {
                console.log("Queue Underflow");
            }
        }
    }



})()

console.log(queue.insert(5))
console.log(queue.insert(3))
console.log(queue.delete(3))

다음으로 2가지 목적을 가진 매우 단순한 큐 실장을 나타냅니다.

• 어레이와 달리shift(). 이 디큐 메서드는 일정한 시간이 소요됩니다(O(1)).
• 속도를 향상시키기 위해 이 접근법은 링크드 리스트 접근법보다 훨씬 적은 할당량을 사용합니다.

스택 실장은 두 번째 목적만을 공유합니다.

// Queue
function Queue() {
        this.q = new Array(5);
        this.first = 0;
        this.size = 0;
}
Queue.prototype.enqueue = function(a) {
        var other;
        if (this.size == this.q.length) {
                other = new Array(this.size*2);
                for (var i = 0; i < this.size; i++) {
                        other[i] = this.q[(this.first+i)%this.size];
                }
                this.first = 0;
                this.q = other;
        }
        this.q[(this.first+this.size)%this.q.length] = a;
        this.size++;
};
Queue.prototype.dequeue = function() {
        if (this.size == 0) return undefined;
        this.size--;
        var ret = this.q[this.first];
        this.first = (this.first+1)%this.q.length;
        return ret;
};
Queue.prototype.peek = function() { return this.size > 0 ? this.q[this.first] : undefined; };
Queue.prototype.isEmpty = function() { return this.size == 0; };

// Stack
function Stack() {
        this.s = new Array(5);
        this.size = 0;
}
Stack.prototype.push = function(a) {
        var other;
    if (this.size == this.s.length) {
            other = new Array(this.s.length*2);
            for (var i = 0; i < this.s.length; i++) other[i] = this.s[i];
            this.s = other;
    }
    this.s[this.size++] = a;
};
Stack.prototype.pop = function() {
        if (this.size == 0) return undefined;
        return this.s[--this.size];
};
Stack.prototype.peek = function() { return this.size > 0 ? this.s[this.size-1] : undefined; };

push() 및 pop() 함수가 있는 스택을 이해하고 있는 경우 큐는 이러한 조작 중 하나를 oposite의 의미로 실행하는 것입니다.push()의 oposite는 unshift()이고 pop() es shift()의 oposite입니다.그 후, 다음과 같이 입력합니다.

//classic stack
var stack = [];
stack.push("first"); // push inserts at the end
stack.push("second");
stack.push("last");
stack.pop(); //pop takes the "last" element

//One way to implement queue is to insert elements in the oposite sense than a stack
var queue = [];
queue.unshift("first"); //unshift inserts at the beginning
queue.unshift("second");
queue.unshift("last");
queue.pop(); //"first"

//other way to do queues is to take the elements in the oposite sense than stack
var queue = [];
queue.push("first"); //push, as in the stack inserts at the end
queue.push("second");
queue.push("last");
queue.shift(); //but shift takes the "first" element

조금 늦은 답변이지만 이 답변은 여기에 있어야 할 것 같습니다.은 O O(1)를 의 구현입니다.enqueueO(1 o O(1)dequeue powerssparse Array를 합니다.

JS의 스파스 어레이는 대부분 무시되지만, 실제로는 매우 귀중한 것이므로 중요한 태스크에 그 힘을 사용해야 합니다.

, 여기 가 있습니다.Queue「」를 확장하는 실장Array【O(1)】【O(1)】【O(1)】

class Queue extends Array {
  constructor(){
    super()
    Object.defineProperty(this,"head",{ value   : 0
                                      , writable: true
                                      });
  }
  enqueue(x) {
    this.push(x);
    return this;
  }
  dequeue() {
    var first;
    return this.head < this.length ? ( first = this[this.head]
                                     , delete this[this.head++]
                                     , first
                                     )
                                   : void 0; // perfect undefined
  }
  peek() {
    return this[this.head];
  }
}

var q = new Queue();
console.log(q.dequeue());      // doesn't break
console.log(q.enqueue(10));    // add 10
console.log(q.enqueue("DIO")); // add "DIO" (Last In Line cCc R.J.DIO reis cCc)
console.log(q);                // display q
console.log(q.dequeue());      // lets get the first one in the line
console.log(q.dequeue());      // lets get DIO out from the line

.as-console-wrapper {
  max-height: 100% !important;
}

그럼 여기 메모리 유출 가능성이 있는 건가요?아니, 난 그렇게 생각하지 않아.JS 스파스 배열은 연속되지 않습니다.따라서 삭제된 항목은 어레이의 메모리 용량에 포함되지 않습니다.GC가 알아서 하게 놔둬무료입니다.

할 수 문제 중 「 」입니다.length큐에 항목을 계속 큐잉하면 속성이 무한히 커집니다.단, 길이가 특정 값에 도달하면 킥인하는 자동 리프레시(응축) 메커니즘을 구현할 수도 있습니다.

편집:

이지만, 「」는 정상입니다.deleteO(1)라고 합니다. 최신 항목>과 JS 25000 항목에 대해 ..shift()O(1)라고 하다그래서 더 나은 게 필요해

이 경우에는 엔진이 발전함에 따라 새로운 힘을 활용해야 합니다.아래 코드는 링크 리스트를 사용하며 2021년 현재 가장 빠르고 안전한 현대 JS Queue 구조라고 생각합니다.

class Queue {
  #head;
  #last;
  constructor(){
    this.#head;
    this.#last;
  };
  enqueue(value){
    var link = {value, next: void 0};
    this.#last = this.#head ? this.#last.next = link
                            : this.#head      = link;
  }
  dequeue(){
    var first;
    return this.#head && ( first = this.#head.value
                         , this.#head = this.#head.next
                         , first
                         );
  }
  peek(){
    return this.#head && this.#head.value;
  }
};

이는 매우 빠른 큐 구조이며 개인 클래스 필드를 사용하여 중요한 변수를 탐색자로부터 숨깁니다.

(링크 리스트에 근거해) 기본적인 조작을 수반하는 스택 및 큐 데이터 구조의 ES6 OOP 실장을 검토하고 있는 경우는, 다음과 같습니다.

큐.js

import LinkedList from '../linked-list/LinkedList';

export default class Queue {
  constructor() {
    this.linkedList = new LinkedList();
  }

  isEmpty() {
    return !this.linkedList.tail;
  }

  peek() {
    if (!this.linkedList.head) {
      return null;
    }

    return this.linkedList.head.value;
  }

  enqueue(value) {
    this.linkedList.append(value);
  }

  dequeue() {
    const removedHead = this.linkedList.deleteHead();
    return removedHead ? removedHead.value : null;
  }

  toString(callback) {
    return this.linkedList.toString(callback);
  }
}

스택.js

import LinkedList from '../linked-list/LinkedList';

export default class Stack {
  constructor() {
    this.linkedList = new LinkedList();
  }

  /**
   * @return {boolean}
   */
  isEmpty() {
    return !this.linkedList.tail;
  }

  /**
   * @return {*}
   */
  peek() {
    if (!this.linkedList.tail) {
      return null;
    }

    return this.linkedList.tail.value;
  }

  /**
   * @param {*} value
   */
  push(value) {
    this.linkedList.append(value);
  }

  /**
   * @return {*}
   */
  pop() {
    const removedTail = this.linkedList.deleteTail();
    return removedTail ? removedTail.value : null;
  }

  /**
   * @return {*[]}
   */
  toArray() {
    return this.linkedList
      .toArray()
      .map(linkedListNode => linkedListNode.value)
      .reverse();
  }

  /**
   * @param {function} [callback]
   * @return {string}
   */
  toString(callback) {
    return this.linkedList.toString(callback);
  }
}

그리고 위의 예에서 스택과 큐에 사용되는 LinkedList 구현은 여기 GitHub에서 찾을 수 있습니다.

어레이 없음

//Javascript stack linked list data structure (no array)

function node(value, noderef) {
    this.value = value;
    this.next = noderef;
}
function stack() {
    this.push = function (value) {
        this.next = this.first;
        this.first = new node(value, this.next);
    }
    this.pop = function () {
        var popvalue = this.first.value;
        this.first = this.first.next;
        return popvalue;
    }
    this.hasnext = function () {
        return this.next != undefined;
    }
    this.isempty = function () {
        return this.first == undefined;
    }

}

//Javascript stack linked list data structure (no array)
function node(value, noderef) {
    this.value = value;
    this.next = undefined;
}
function queue() {
    this.enqueue = function (value) {
        this.oldlast = this.last;
        this.last = new node(value);
        if (this.isempty())
            this.first = this.last;
        else 
           this.oldlast.next = this.last;
    }
    this.dequeue = function () {
        var queuvalue = this.first.value;
        this.first = this.first.next;
        return queuvalue;
    }
    this.hasnext = function () {
        return this.first.next != undefined;
    }
    this.isempty = function () {
        return this.first == undefined;
    }

}

다음은 @perkins에서 제안하고 가장 적절한 마지막 노드를 포함하는 큐의 링크 목록 버전입니다.

// QUEUE Object Definition

var Queue = function() {
  this.first = null;
  this.last = 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){ // for empty list first and last are the same
    this.first = node;
    this.last = node;
  } else { // otherwise we stick it on the end
    this.last.next=node;
    this.last=node;
  }

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

Queue.prototype.dequeue = function() {
  if (!this.first) //check for empty list
    return null;

  temp = this.first; // grab top of list
  if (this.first==this.last) {
    this.last=null;  // when we need to pop the last one
  }
  this.first = this.first.next; // move top of list down
  this.size -= 1;
  return temp;
};

Javascript의 표준 배열 구조는 스택(선입선출)이며, 발신 콜에 따라 큐(선입선출선출)로도 사용할 수 있습니다.

어레이를 큐처럼 동작시키는 방법에 대해서는, 다음의 링크를 참조해 주세요.

큐

  var x = 10; 
  var y = 11; 
  var Queue = new Array();
  Queue.unshift(x);
  Queue.unshift(y);

  console.log(Queue)
  // Output [11, 10]

  Queue.pop()
  console.log(Queue)
  // Output [11]

내장 어레이는 스택으로 충분할 것 같습니다.TypeScript에서 큐잉을 원하는 경우 구현은 다음과 같습니다.

/**
 * A Typescript implementation of a queue.
 */
export default class Queue {

  private queue = [];
  private offset = 0;

  constructor(array = []) {
    // Init the queue using the contents of the array
    for (const item of array) {
      this.enqueue(item);
    }
  }

  /**
   * @returns {number} the length of the queue.
   */
  public getLength(): number {
    return (this.queue.length - this.offset);
  }

  /**
   * @returns {boolean} true if the queue is empty, and false otherwise.
   */
  public isEmpty(): boolean {
    return (this.queue.length === 0);
  }

  /**
   * Enqueues the specified item.
   *
   * @param item - the item to enqueue
   */
  public enqueue(item) {
    this.queue.push(item);
  }

  /**
   *  Dequeues an item and returns it. If the queue is empty, the value
   * {@code null} is returned.
   *
   * @returns {any}
   */
  public dequeue(): any {
    // if the queue is empty, return immediately
    if (this.queue.length === 0) {
      return null;
    }

    // store the item at the front of the queue
    const item = this.queue[this.offset];

    // increment the offset and remove the free space if necessary
    if (++this.offset * 2 >= this.queue.length) {
      this.queue = this.queue.slice(this.offset);
      this.offset = 0;
    }

    // return the dequeued item
    return item;
  };

  /**
   * Returns the item at the front of the queue (without dequeuing it).
   * If the queue is empty then {@code null} is returned.
   *
   * @returns {any}
   */
  public peek(): any {
    return (this.queue.length > 0 ? this.queue[this.offset] : null);
  }

}

여기 ★★★★★★★★★★★★★★★★★★★★★★★.Jest해 보다

it('Queue', () => {
  const queue = new Queue();
  expect(queue.getLength()).toBe(0);
  expect(queue.peek()).toBeNull();
  expect(queue.dequeue()).toBeNull();

  queue.enqueue(1);
  expect(queue.getLength()).toBe(1);
  queue.enqueue(2);
  expect(queue.getLength()).toBe(2);
  queue.enqueue(3);
  expect(queue.getLength()).toBe(3);

  expect(queue.peek()).toBe(1);
  expect(queue.getLength()).toBe(3);
  expect(queue.dequeue()).toBe(1);
  expect(queue.getLength()).toBe(2);

  expect(queue.peek()).toBe(2);
  expect(queue.getLength()).toBe(2);
  expect(queue.dequeue()).toBe(2);
  expect(queue.getLength()).toBe(1);

  expect(queue.peek()).toBe(3);
  expect(queue.getLength()).toBe(1);
  expect(queue.dequeue()).toBe(3);
  expect(queue.getLength()).toBe(0);

  expect(queue.peek()).toBeNull();
  expect(queue.dequeue()).toBeNull();
});

누군가 이걸 유용하게 찾았으면 좋겠는데

건배.

스튜

싱글 엔드 큐

여기 지도를 사용한 큐가 있습니다.삽입 순서가 보장되므로 배열처럼 반복할 수 있습니다.그 외에는 Queue.js와 매우 유사합니다.

간단한 테스트를 몇 가지 해봤지만 광범위하게 테스트하지는 않았습니다. 좋다고 쉬운 고고고고고고고어어어어어어어어어어어)도 추가했습니다.last() ★★★★★★★★★★★★★★★★★」first()를 참조해 주세요.

그 배후에 있는 간단한 버전/직관은 다음과 같습니다.

class Queue {
    constructor() {
        this.offset = 0
        this.data = new Map()
    }

    enqueue(item) {
        const current = this.offset + this.length()
        this.data.set(current, item)
    }

    dequeue() {
        if (this.length() > 0) {
            this.data.delete(this.offset)
            this.offset += 1
        }
    }

    first() {
        return this.data.get(this.offset)
    }

    last() {
        return this.data.get(this.offset + this.length() - 1)
    }

    length() {
        return this.data.size
    }
}

약9은 9,000조)를 넘었을 때 메모리를 다시 매핑해야 한다는 것입니다.Number.MAX_SAFE_INTEGER또한 어레이 구축이 있으면 좋을 것 같고, 큐잉 및 디큐잉된 값이 반환되는 것을 볼 수 있어 좋습니다.다음 코드를 작성하면 이를 설명할 수 있습니다.

class Queue {
    constructor() {
        this.offset = 0
        this.data = new Map()
        if (arguments.length === 1) this._initializeFromArray(arguments[0])
    }

    enqueue(item) {
        const current = this.offset + this.length()
        this.data.set(current, item)
        let result = this.data.get(current)
        this._remapDataIfMaxMemoryViolation(current, Number.MAX_SAFE_INTEGER)
        return result
    }

    dequeue() {
        let result = undefined
        if (this.length() > 0) {
            result = this.data.get(this.offset)
            this.data.delete(this.offset)
            this.offset += 1
        }
        if (this.length() === 0) this.offset = 0
        return result
    }

    first() {
        return this.data.get(this.offset)
    }

    last() {
        return this.data.get(this.offset + this.length() - 1)
    }

    length() {
        return this.data.size
    }

    _remapDataIfMaxMemoryViolation(current, threshhold) {
        if (current+1 === threshhold) {
            const length = this.length()
            this.offset = 0
            for (const [key, value] of this.data) {
                this.data.set(this.offset, value)
                this.data.delete(key, value)
                this.offset += 1
                if (this.offset === length) break
            }       
        }
    }

    _initializeFromArray(array) {
        for (const value of array) {
            this.data.set(this.offset, value)
            this.offset += 1
        }
    }
}

Chrome 개발자 콘솔에서 풀버전으로 다음 콜을 통해 테스트를 실시했습니다.

l = console.log // I'm lazy with typing
q = new Queue()
l('enqueue', q.enqueue(1))
l('enqueue', q.enqueue(2))
l('enqueue', q.enqueue(3))
l('enqueue', q.enqueue("hello"))
l('enqueue', q.enqueue("monkey"))
l('show 5 elements: ', q.data)
l('length', q.length())
l('first', q.first())
l('last', q.last())
l('dequeue', q.dequeue())
l('dequeue', q.dequeue())
l('show 3 elements', q.data)
q._remapDataIfMaxMemoryViolation(q.length()+q.offset-1, 5)
l('show 3 remapped elements', q.data)

l(queue = new Queue([3,4,5,6,7,8,9]))
l(queue.data)

이 토픽을 설명하게 되어 죄송합니다만, O(1)를 사용하여 큐잉 및 디큐잉을 수행할 수 있고 메모리 낭비가 없는 오브젝트 기반 큐의 실장은 보이지 않습니다.

Dmitri Pavlutin은 그의 블로그 https://dmitripavlutin.com/javascript-queue/에 멋진 스타터 코드를 가지고 있습니다.

0 렝스 체크만 누락됩니다.이것은 추가하는 것이 간단한 것입니다.

이 솔루션의 크고 유일한 문제는 큐가 장시간 및/또는 고속으로 실행될 경우 인덱스가 한 시점에 어느 정도 수 제한에 도달할 수 있다는 것입니다(내 목적은 오디오 = 고속 처리).

이에 대한 완벽한 해결책은 없다...큐가 비어 있을 때마다 인덱스를 0으로 재설정하는 것이 가장 쉬운 방법입니다.

는 지막 a a a a a a a a a a a a a a를 했다.refactor큐가 비어 있지 않은 경우에 사용하기 위해 비용이 많이 드는 모든 인덱스를 선두로 되돌리는 메서드.

퍼포먼스는 확실히 향상됩니다(숫자는 10,000개의 번호를 큐잉한 후 큐를 해제하는 시간(밀리초 단위).

class QueueObject {
  constructor () {
    this.data = {}
    this.head = 0
    this.tail = 0
    this.length = 0
  }
  enqueue (value) {
    this.data[this.tail++] = value
    this.length++
  }
  dequeue () {
    let value
    if (this.length > 0) {
      this.length--
      value = this.data[this.head]
      delete this.data[this.head++]
    } else {
      this.head = 0
      this.tail = 0
      value = null
    }
    return value
  }
  refactor () {
    if (this.head > 0) {
      for (let i = this.head; i < this.tail; i++) {
        this.data[i - this.head] = this.data[i]
        delete this.data[i]
      }
      this.tail = this.length
      this.head = 0
    }
  }
}

이러한 데이터 구조 각각이 가지는 다양한 메서드(푸시, 팝, 엿보기 등)를 제공하는 클래스 쌍을 만듭니다.이제 방법을 구현합니다.스택/큐의 이면에 있는 개념을 잘 알고 계시다면, 이것은 매우 간단합니다.스택은 어레이를 사용하여 구현할 수 있습니다.또한 링크 리스트가 있는 큐도 구현할 수 있습니다.다만, 다른 방법이 있습니다.Javascript는 약하게 타이핑되어 있기 때문에 Java나 C#에서 구현했을 경우에는 범용 타입에 대해 걱정할 필요가 없기 때문에 쉽게 할 수고를 덜 수 있습니다.

스택의 실장은 다음과 같습니다.

function Stack() {
this.dataStore = [];
this.top = 0;
this.push = push;
this.pop = pop;
this.peek = peek;
this.clear = clear;
this.length = length;
}
function push(element) {
this.dataStore[this.top++] = element;
}
function peek() {
return this.dataStore[this.top-1];
}
function pop() {
return this.dataStore[--this.top];
}
function clear() {
this.top = 0;
}
function length() {
return this.top;
}

var s = new Stack();
s.push("David");
s.push("Raymond");
s.push("Bryan");
console.log("length: " + s.length());
console.log(s.peek());

ES6 클래스에서 프라이빗 속성을 구현하기 위해 WeakMaps를 사용할 수 있습니다.또, JavaScript 언어에서의 String propries나 메서드의 메리트는 다음과 같습니다.

const _items = new WeakMap();

class Stack {
  constructor() {
    _items.set(this, []);
  }

push(obj) {
  _items.get(this).push(obj);
}

pop() {
  const L = _items.get(this).length;
  if(L===0)
    throw new Error('Stack is empty');
  return _items.get(this).pop();
}

peek() {
  const items = _items.get(this);
  if(items.length === 0)
    throw new Error ('Stack is empty');
  return items[items.length-1];
}

get count() {
  return _items.get(this).length;
}
}

const stack = new Stack();

//now in console:
//stack.push('a')
//stack.push(1)
//stack.count   => 2
//stack.peek()  => 1
//stack.pop()   => 1
//stack.pop()   => "a"
//stack.count   => 0
//stack.pop()   => Error Stack is empty

안부 전해요,

Javascript에서 스택과 큐의 구현은 다음과 같습니다.

스택: 스택은 LIFO(Last-In-First-Out) 원칙에 따라 삽입 및 삭제되는 객체의 컨테이너입니다.

• 푸시: 메서드는 배열 끝에 하나 이상의 요소를 추가하고 배열의 새 길이를 반환합니다.
• Pop: 메서드는 배열에서 마지막 요소를 제거하고 해당 요소를 반환합니다.

큐: 큐는 First-In-First-Out(FIFO; 선입선출) 원칙에 따라 삽입 및 삭제되는 오브젝트(선형 컬렉션)의 컨테이너입니다.

• Unshift: 메서드는 배열의 선두에 하나 이상의 요소를 추가합니다.

• Shift: 메서드는 배열에서 첫 번째 요소를 제거합니다.

let stack = [];
 stack.push(1);//[1]
 stack.push(2);//[1,2]
 stack.push(3);//[1,2,3]
 
console.log('It was inserted 1,2,3 in stack:', ...stack);

stack.pop(); //[1,2]
console.log('Item 3 was removed:', ...stack);

stack.pop(); //[1]
console.log('Item 2 was removed:', ...stack);


let queue = [];
queue.push(1);//[1]
queue.push(2);//[1,2]
queue.push(3);//[1,2,3]

console.log('It was inserted 1,2,3 in queue:', ...queue);

queue.shift();// [2,3]
console.log('Item 1 was removed:', ...queue);

queue.shift();// [3]
console.log('Item 2 was removed:', ...queue);

BFS를 실장하고 있을 때 이 스레드에 부딪혔습니다.왜 이렇게 성능이 안 좋은지 궁금해서 조사를 좀 해봤어요. 배열.shift()는 일반적으로 O(n)에서 실행되며, 이로 인해 BFS 실행 시간이 O(V+E)에서 O(V^2+E)로 증가합니다.

처음부터 큐를 실장하는 것이 아니라 이전에 사용하던 어레이 방식과 호환성이 있어 매력적으로 동작하는 npm 패키지 더블 엔드 큐를 사용했습니다.deque는 스택 또는 큐로 사용할 수 있습니다.

    //import package
    import Deque from 'double-ended-queue';

    //create queue
    let queue = new Deque();
    //append
    queue.push(item);
    //dequeue (get first item inserted)
    let firstItem = queue.shift();

    //pop (get last item inserted)
    let lastItem = queue.pop();

배열은 Javascript의 스택입니다.그냥 사용하다arr.push(x)그리고.y = arr.pop().

다음은 Javascript에서 대기열을 구현하기 위한 가장 간단한 방법으로 상각된 시간은 다음과 같습니다.O(1)쌍방에게enqueue(x)그리고.y = dequeue()삽입 인덱스에서 요소로의 매핑을 사용합니다.

function newQueue() {
    const queue = {
        headIdx: 0,
        tailIdx: 0,
        elts: {},
        enqueue: (elt) => queue.elts[queue.tailIdx++] = elt,
        dequeue: () => {
            if (queue.headIdx == queue.tailIdx) {
                throw new Error("Queue is empty");
            }
            return queue.elts[queue.headIdx++];
        },
        size: () => queue.tailIdx - queue.headIdx,
        isEmpty: () => queue.tailIdx == queue.headIdx
    };
    return queue;
}

링크 리스트를 사용하여 실장된 큐는 이 맵베이스 방식보다 효율적이며, 순환 버퍼를 사용하여 실장된 큐는 이 맵베이스 방식보다 훨씬 효율적이지만 이들 2개의 데이터 구조(특히 순환 버퍼 데이터 구조)의 실장은 더 복잡하다.

다른 사람이 필요할 경우 이 NPM 패키지 https://www.npmjs.com/package/data-structures-typescript,를 사용하면 됩니다.큐와 스택이 있으며 javascript와 typescript를 모두 지원하므로 일반적이므로 자신의 가치로 사용할 수 있습니다.

언급URL : https://stackoverflow.com/questions/1590247/how-do-you-implement-a-stack-and-a-queue-in-javascript