반응형
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는 대기열에서 빼기 기능이 상각 된 일정한 시간에 실행되는 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();자바 스크립트에서 스택과 큐를 구현할 수있는 몇 가지 방법이 있습니다. 위의 답변 대부분은 매우 얕은 구현이며 더 읽기 쉽고 (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/
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
보시다시피 큰 데이터 세트를 사용하면 훨씬 더 빠릅니다.
/*------------------------------------------------------------------
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))
또는 두 개의 배열을 사용하여 큐 데이터 구조를 구현할 수 있습니다.
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
다음은 두 가지 목적을 가진 매우 간단한 큐 구현입니다.
- array.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; };
개념에 따라 사용자 정의 클래스를 사용할 수 있습니다. 여기에는 작업을 수행하는 데 사용할 수있는 코드 스 니펫이 있습니다.
/*
* 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();
push () 및 pop () 함수로 스택을 이해하는 경우 대기열은 이러한 작업 중 하나를 반대의 의미로 만드는 것입니다. push ()의 반대는 unshift ()이고 pop ()의 반대는 shift ()입니다. 그때:
//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
다음은 @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;
};
스택 구현은 다른 답변에서 설명한 것처럼 사소합니다.
그러나이 스레드에서 자바 스크립트로 대기열을 구현하는 데 만족스러운 답변을 찾지 못했기 때문에 직접 만들었습니다.
이 스레드에는 세 가지 유형의 솔루션이 있습니다.
- 어레이-
array.shift()대형 어레이 에서 사용하는 최악의 솔루션 은 매우 비효율적입니다. - 연결된 목록-O (1)이지만 각 요소에 대해 객체를 사용하는 것은 약간 과도합니다. 특히 숫자를 저장하는 것처럼 많고 작은 경우에는 더욱 그렇습니다.
- 지연된 시프트 배열-인덱스와 배열을 연결하는 것으로 구성됩니다. 요소가 대기열에서 제외되면 인덱스가 앞으로 이동합니다. 인덱스가 배열의 중간에 도달하면 배열이 두 개로 분할되어 전반부가 제거됩니다.
지연된 시프트 배열은 내 마음에 가장 만족스러운 솔루션이지만 문제가 될 수있는 하나의 큰 연속 배열에 모든 것을 저장하고 배열이 슬라이스 될 때 응용 프로그램이 비틀 거릴 것입니다.
작은 배열의 연결 목록 (각각 최대 1000 개 요소)을 사용하여 구현했습니다. 배열은 슬라이스되지 않는다는 점을 제외하면 지연된 시프트 배열처럼 동작합니다. 배열의 모든 요소가 제거되면 배열이 단순히 삭제됩니다.
패키지는 기본 FIFO 기능을 갖춘 npm에 있으며 최근에 방금 푸시했습니다. 코드는 두 부분으로 나뉩니다.
여기 첫 번째 부분입니다
/** 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;
}
유형 주석 ( : X)을 쉽게 제거하여 ES6 자바 스크립트 코드를 얻을 수 있습니다.
어레이 없음
//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;
}
}
자바 스크립트의 일반적인 배열 구조는 스택 (선입 선출)이며 호출에 따라 대기열 (선입 선출)로 사용할 수도 있습니다.
이 링크를 확인하여 어레이가 대기열처럼 작동하도록하는 방법을 확인하십시오.
몇 가지 기본 작업 (연결 목록 기반)을 사용하여 스택 및 큐 데이터 구조의 ES6 OOP 구현을 찾고 있다면 다음과 같을 수 있습니다.
Queue.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);
}
}
Stack.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);
}
}
위의 예제에서 Stack 및 Queue에 사용되는 LinkedList 구현은 여기 GitHub에서 찾을 수 있습니다 .
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();
});
누군가가 유용하다고 생각하기를 바랍니다.
건배,
Stu
문안 인사,
Javascript에서 스택 및 큐의 구현은 다음과 같습니다.
스택 : 스택은 LIFO (후입 선출) 원칙에 따라 삽입 및 제거되는 개체의 컨테이너입니다.
- 푸시 : 메서드는 배열 끝에 하나 이상의 요소를 추가하고 배열의 새 길이를 반환합니다.
- Pop : 메서드는 배열에서 마지막 요소를 제거하고 해당 요소를 반환합니다.
대기열 : 대기열은 선입 선출 (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);이러한 각 데이터 구조가 갖는 다양한 메서드 (푸시, 팝, 픽 등)를 제공하는 클래스 쌍을 만듭니다. 이제 메소드를 구현하십시오. 스택 / 큐의 개념에 익숙하다면 이것은 매우 간단합니다. 배열을 사용하여 스택을 구현하고 연결 목록이있는 큐를 구현할 수 있습니다. 물론 다른 방법도 있습니다. 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());
WeakMaps를 사용하여 ES6 클래스에서 개인 속성을 구현하고 아래와 같은 JavaScript 언어의 String 속성 및 메서드의 이점을 사용할 수 있습니다.
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
참고URL : https://stackoverflow.com/questions/1590247/how-do-you-implement-a-stack-and-a-queue-in-javascript
반응형
'Program Tip' 카테고리의 다른 글
| 자바에서 확인 된 예외와 확인되지 않은 예외 이해 (0) | 2020.09.30 |
|---|---|
| git-merge --dry-run 옵션이 있습니까? (0) | 2020.09.30 |
| Java 9에서 java.lang.NoClassDefFoundError : javax / xml / bind / JAXBException을 해결하는 방법 (0) | 2020.09.30 |
| 로컬 git 커밋을 취소하는 방법 (0) | 2020.09.30 |
| 파일 및 관련 데이터를 가급적 JSON으로 RESTful 웹 서비스에 게시 (0) | 2020.09.30 |