javascript - आप जावास्क्रिप्ट में स्टैक और कतार कैसे कार्यान्वित करते हैं?




data-structures stack (14)

जावास्क्रिप्ट में स्टैक और कतार को लागू करने का सबसे अच्छा तरीका क्या है?

मैं शंटिंग-यार्ड एल्गोरिदम करना चाहता हूं और मुझे इन डेटा-संरचनाओं की आवश्यकता होगी।


अन्य उत्तरों में समझाया गया है कि ढेर कार्यान्वयन छोटा है।

हालांकि, मुझे जावास्क्रिप्ट में कतार लागू करने के लिए इस धागे में कोई संतोषजनक उत्तर नहीं मिला, इसलिए मैंने अपना खुद का बना दिया।

इस धागे में तीन प्रकार के समाधान हैं:

  • Arrays - एक बड़ी सरणी पर array.shift() का उपयोग कर सबसे खराब समाधान बहुत अक्षम है
  • लिंक्ड सूचियां - यह ओ (1) है लेकिन प्रत्येक तत्व के लिए ऑब्जेक्ट का उपयोग करना थोड़ा अधिक है, खासकर यदि उनमें से बहुत सारे हैं और वे छोटे हैं, जैसे स्टोर नंबर
  • विलंबित शिफ्ट सरणी - इसमें सरणी के साथ एक इंडेक्स को जोड़ना शामिल है। जब एक तत्व को हटा दिया जाता है, तो सूचकांक आगे बढ़ता है। जब सूचकांक सरणी के बीच तक पहुंच जाता है, तो पहली छमाही को हटाने के लिए सरणी को दो में काटा जाता है।

विलंबित शिफ्ट arrays मेरे दिमाग में सबसे संतोषजनक समाधान हैं, लेकिन वे अभी भी सब कुछ एक बड़ी संगत सरणी में स्टोर करते हैं जो समस्याग्रस्त हो सकता है, और जब सरणी काटा जाता है तो एप्लिकेशन घबराएगा।

मैंने छोटे सरणी (प्रत्येक 1000 अधिकतम तत्व) की एक लिंक्ड सूचियों का उपयोग करके कार्यान्वयन किया। सरणी देरी शिफ्ट सरणी की तरह व्यवहार करती है, सिवाय इसके कि उन्हें कभी कटाई नहीं होती है: जब सरणी में प्रत्येक तत्व हटा दिया जाता है, तो सरणी को त्याग दिया जाता है।

पैकेज मूल फीफो कार्यशीलता के साथ एनपीएम पर है , मैंने हाल ही में इसे धक्का दिया है। कोड दो भागों में विभाजित है।

यहां पहला भाग है

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

ईएस 6 जावास्क्रिप्ट कोड प्राप्त करने के लिए एनोटेशन टाइप करें ( : X ) आसानी से हटाया जा सकता है।


अन्यथा आप कतार डेटा संरचना को लागू करने के लिए दो सरणी का उपयोग कर सकते हैं।

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

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

अगर मैं अब तत्वों को पॉप करता हूं तो आउटपुट 3,2,1 होगा। लेकिन हम फीफो संरचना चाहते हैं ताकि आप निम्नलिखित कर सकें।

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

कक्षाओं की एक जोड़ी बनाएं जो विभिन्न विधियों को प्रदान करती है जिनमें से प्रत्येक डेटा संरचनाओं में (पुश, पॉप, पीक, इत्यादि) है। अब विधियों को लागू करें। यदि आप स्टैक / कतार के पीछे अवधारणाओं से परिचित हैं, तो यह बहुत सरल होना चाहिए। आप एक सरणी के साथ ढेर को लागू कर सकते हैं, और एक लिंक्ड सूची के साथ एक कतार, हालांकि इसके बारे में निश्चित रूप से अन्य तरीके हैं। जावास्क्रिप्ट इसे आसान बना देगा, क्योंकि इसे कमजोर टाइप किया गया है, इसलिए आपको जेनेरिक प्रकारों के बारे में भी चिंता करने की ज़रूरत नहीं है, जो आपको जावा या सी # में लागू करने पर करना होगा।


कोई ऐरे नहीं

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

}

जावास्क्रिप्ट में पुश और पॉप विधियां हैं, जो सामान्य जावास्क्रिप्ट सरणी ऑब्जेक्ट्स पर काम करती हैं।

कतारों के लिए, यहां देखें:

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

क्यूयू को या तो पुश और शिफ्ट विधियों या सरणी ऑब्जेक्ट के अवांछित और पॉप विधियों का उपयोग करके जावास्क्रिप्ट में कार्यान्वित किया जा सकता है। यद्यपि यह कतारों को लागू करने का एक आसान तरीका है, लेकिन यह बड़ी कतारों के लिए बहुत अक्षम है - क्योंकि विधियां सरणी पर चलती हैं, शिफ्ट और अनशिफ्ट विधियां प्रत्येक तत्व को प्रत्येक बार सरणी में स्थानांतरित करती हैं।

Queue.js जावास्क्रिप्ट के लिए एक सरल और कुशल कतार कार्यान्वयन है जिसका डेक्यू फ़ंक्शन अमूर्त निरंतर समय में चलता है। नतीजतन, बड़ी कतारों के लिए यह सरणी का उपयोग करने से काफी तेज हो सकता है।


जावास्क्रिप्ट में स्टैक और कतार लागू करने के कुछ तरीके हैं जिनमें आप हैं। उपरोक्त अधिकांश उत्तर काफी उथले कार्यान्वयन हैं और मैं कुछ और पठनीय (ईएस 6 की नई वाक्यविन्यास विशेषताओं का उपयोग करके) और मजबूत लागू करने की कोशिश करता हूं।

यहां ढेर कार्यान्वयन है:

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/ queues/


मुझे लगता है कि निर्मित सरणी एक ढेर के लिए ठीक है। यदि आप टाइपस्क्रिप्ट में एक कतार चाहते हैं तो यहां एक कार्यान्वयन है

/**
 * 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();
});

आशा है कि किसी को यह उपयोगी लगेगा,

चीयर्स,

स्टू


यदि आप अपनी खुद की डेटा संरचना बनाना चाहते हैं, तो आप अपना खुद का निर्माण कर सकते हैं:

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

यहां एक कतार का लिंक किया गया सूची संस्करण है जिसमें अंतिम नोड भी शामिल है, जैसा कि @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;
};

यहां ढेर का मेरा कार्यान्वयन है।

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());

सरणी।

ढेर:

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();

लिंक्ड लिस्ट का उपयोग करके स्टैक और कतार का मेरा कार्यान्वयन

// 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();


/*------------------------------------------------------------------ 
 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("")
                }
            },
            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))








queue