Πώς να εφαρμόσετε μια στοίβα σε JavaScript βανίλιας και ES6

Μια στοίβα είναι μια παραγγελθείσα συλλογή στοιχείων που ακολουθούν την αρχή Last In First Out (LIFO). Η προσθήκη και η αφαίρεση αντικειμένων πραγματοποιούνται στο ίδιο άκρο, δηλαδή στην κορυφή. Τα νεότερα στοιχεία βρίσκονται στην κορυφή και τα παλαιότερα στοιχεία βρίσκονται στο κάτω μέρος.

Έχουμε πολλά παραδείγματα στοιβών γύρω μας, όπως ένα σωρό βιβλίων, μια στοίβα δίσκων ή πιάτων κ.λπ.

Μια στοίβα χρησιμοποιείται από μεταγλωττιστές σε γλώσσες προγραμματισμού, από τη μνήμη του υπολογιστή για την αποθήκευση μεταβλητών και λειτουργιών, καθώς και σε προγράμματα επεξεργασίας κειμένου για την εκτέλεση αναίρεσης και επαναφοράς λειτουργιών

Λίστα λειτουργιών που εκτελούνται στο Stack

  • push () : Προσθέτει ένα ή περισσότερα στοιχεία στην κορυφή της στοίβας.
  • pop () : Αφαιρεί και επιστρέφει το κορυφαίο στοιχείο του Stack.
  • peek () : Επιστρέφει το κορυφαίο στοιχείο του Stack.
  • isEmpty () : Επιστρέφει Trueεάν η στοίβα είναι κενή, Falseδιαφορετικά.
  • διαγραφή () : Καταργεί όλα τα στοιχεία από το Stack.
  • size () : Επιστρέφει το μήκος της στοίβας.

Δημιουργία στοίβας

Μια κλασική προσέγγιση

Θα εφαρμόσουμε μια στοίβα όπως και πώς εφαρμόζεται σε άλλες γλώσσες εκτός από το JavaScript.

Θα χρησιμοποιήσουμε έναν πίνακα και μια επιπλέον μεταβλητή για να παρακολουθούμε τα στοιχεία.

function Stack(){ var items = []; var top = 0; //other methods go here }

Σπρώξτε ένα στοιχείο στη στοίβα

//Push an item in the Stackthis.push = function(element){ items[top++] = element } //top++, first performs the operation then increment's the value

Βάλτε ένα αντικείμενο από το Stack

//Pop an item from the Stackthis.pop = function(){ return items[--top]; } //--top, first decrements the value then performs the operation

Ρίξτε μια ματιά στο κορυφαίο στοιχείο από το Stack

//peek an item in the Stackthis.peek = function(){ return items[top - 1]; }

Ελέγξτε εάν η στοίβα είναι άδεια

//Is stack emptythis.isEmpty = function(){ return top === 0; }

Εκκαθάριση της στοίβας

//clear the stackthis.clear= function(){ top = 0; }

Μέγεθος της στοίβας

//Size of the Stackthis.size = function(){ return top; }

Πλήρης εφαρμογή του Stack

function Stack(){ var items = []; var top = 0; //other methods go here 
 //Push an item in the Stack this.push = function(element){ items[top++] = element } //top++, first performs the operation then increment's the value 
 //Pop an item from the Stack this.pop = function(){ return items[--top]; } //--top, first decrements the value then performs the operation 
 //Peek top item of the Stack this.peek = function(){ return items[top - 1]; } 
 //Is Stack empty this.isEmpty = function(){ return top === 0; } 
 //Clear the Stack this.clear = function(){ top = 0; } 
 //Size of the Stack this.size = function(){ return top; }
}

Παράδειγμα

Τώρα θα δημιουργήσουμε μια νέα παρουσία αυτού που έχουμε εφαρμόσει και θα ελέγξουμε εάν λειτουργεί σωστά.

var stack = new Stack(); //creating new instance of Stack stack.push(1); stack.push(2); stack.push(3); console.log(stack.peek()); console.log(stack.isEmpty()); console.log(stack.size()); console.log(stack.pop()); console.log(stack.size()); stack.clear(); console.log(stack.isEmpty()); 
Output: 3 false 3 3 2 true

Εφαρμογή στοίβας με JavaScript

Θα εφαρμόσουμε μια στοίβα με έναν πίνακα JavaScript που έχει ενσωματωμένες μεθόδους όπως push και pop.

function Stack(){ var items = []; //other methods go here }

Σπρώξτε ένα στοιχείο στη στοίβα

//push an item in the Stackthis.push = function(element){ items.push(element); }

Βάλτε ένα αντικείμενο από το Stack

//Pop an item from the Stackthis.pop = function(){ return items.pop(); }

Ρίξτε μια ματιά στο κορυφαίο στοιχείο από το Stack

//Peek top item of the Stackthis.peek = function(){ return items[items.length - 1]; }

Ελέγξτε εάν η στοίβα είναι άδεια

//Is Stack emptythis.isEmpty = function(){ return items.length === 0; }

Εκκαθάριση της στοίβας

//Clear the Stackthis.clear = function(){ items.length = 0; }

Μέγεθος της στοίβας

//Size of the Stackthis.size = function(){ return items.length; }

Πλήρης εφαρμογή του Stack

function Stack(){ var items = []; //other methods go here 
 //Push a item in the Stack this.push = function(element){ items.push(element); } 
 //Pop a item from the Stack this.pop = function(){ return items.pop(); } 
 //Peek top item of the Stack this.peek = function(){ return items[items.length - 1]; }
 //Is Stack empty this.isEmpty = function(){ return items.length === 0; } 
 //Clear the Stack this.clear = function(){ items.length = 0; } 
 //Size of the Stack this.size = function(){ return items.length; } 
}

Καθιστώντας τις ιδιότητες και τις μεθόδους ιδιωτικές με κλείσιμο και IIFE (Άμεση επίκληση της έκφρασης λειτουργίας).

var Stack = (function () { return function Stack(){ var items = []; //other methods go here 
 //Push an item in the Stack this.push = function(element){ items.push(element); } 
 //Pop an item from the Stack this.pop = function(){ return items.pop(); } 
 //Peek top item from the Stack this.peek = function(){ return items[items.length - 1]; } 
 //Is Stack empty this.isEmpty = function(){ return items.length === 0; } 
 //Clear the Stack this.clear = function(){ items.length = 0; } //Size of the Stack this.size = function(){ return items.length; } }})();

Στοίβα χρησιμοποιώντας ES6.

class Stack{ constructor(){ this.items = []; } //other methods go here //Push an item in the Stack push = function(element){ this.items.push(element); }
//Pop an item from the Stack pop = function(){ return this.items.pop(); } //Peek top item from the Stack peek = function(){ return this.items[this.items.length - 1]; }
//Is Stack empty isEmpty = function(){ return this.items.length === 0; }
//Clear the Stack clear = function(){ this.items.length = 0; } //Size of the Stack size = function(){ return this.items.length; }}

Στοίβα χρησιμοποιώντας το ES6 WeakMap.

const items = new WeakMap();class Stack{ constructor(){ items.set(this, []); } //other methods go here //Push an item in the Stack push = function(element){ let temp = items.get(this); temp.push(element); }
//Pop an item from the Stack pop = function(){ let temp = items.get(this); return temp.pop(); } //Peek top item from the Stack peek = function(){ let temp = items.get(this); return temp[temp.length - 1]; }
//Is Stack empty isEmpty = function(){ let temp = items.get(this); return temp.length === 0; }
//Clear the Stack clear = function(){ let temp = items.get(this); temp.length = 0; } //Size of the Stack size = function(){ let temp = items.get(this); return temp.length; }}

Καθιστώντας τις ιδιότητες και τις μεθόδους ιδιωτικές με κλείσιμο και IIFE (Άμεση επίκληση της λειτουργίας έκφρασης) για Stack χρησιμοποιώντας ES6 WeakMap.

let Stack = (() => { const items = new WeakMap(); return class Stack{ constructor(){ items.set(this, []); }
//other methods go here //Push an item in the Stack push = function(element){ let temp = items.get(this); temp.push(element); }
//Pop an item from the Stack pop = function(){ let temp = items.get(this); return temp.pop(); }
//Peek top item from the Stack peek = function(){ let temp = items.get(this); return temp[temp.length - 1]; }
//Is Stack empty isEmpty = function(){ let temp = items.get(this); return temp.length === 0; }
//Clear the Stack clear = function(){ let temp = items.get(this); temp.length = 0; }
//Size of the Stack size = function(){ let temp = items.get(this); return temp.length; } }})();

Χρόνος πολυπλοκότητας

# Μέση τιμή

Πρόσβαση: Θ (Ν)

Αναζήτηση: Θ (N)

Εισαγωγή: Θ (1)

Διαγραφή: Θ (1)

# Χειρότερο

Πρόσβαση: O (N)

Αναζήτηση: O (N)

Εισαγωγή: O (1)

Διαγραφή: O (1)

Διαστημική πολυπλοκότητα

# Χειρότερο : O (N)

Υπάρχουν πολλά προβλήματα όπου το Stack μπορεί να είναι η τέλεια δομή δεδομένων που απαιτείται για τη λύση.

  • Ο αλγόριθμος μετατροπέα βάσης
  • Ισορροπημένες παρενθέσεις

Εάν σας άρεσε αυτό το άρθρο, δώστε το λίγο; Εάν έχετε οποιεσδήποτε ερωτήσεις σχετικά με αυτό, μη διστάσετε να με ρωτήσετε.

Για περισσότερες παρόμοιες και αλγοριθμικές λύσεις στο Javascript, ακολουθήστε με στο Twitter . Γράφω για ES6, React, Nodejs, δομές δεδομένων και αλγόριθμους στο learnersbucket.com .