Bagaimana Anda menerapkan Stack dan Antrian dalam JavaScript?

741

Apa cara terbaik untuk menerapkan Stack dan Antrian dalam JavaScript?

Saya ingin melakukan algoritma shunting-yard dan saya akan membutuhkan struktur data ini.

KingNestor
sumber

Jawaban:

1347
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

diambil dari " 9 tips javascript yang mungkin tidak Anda ketahui "

Corey Ballou
sumber
218
Saya akan menyarankan agar berhati-hati dalam menggunakan queue.shift. IIRC itu bukan O (1), tetapi O (n) dan mungkin terlalu lambat jika antrian bertambah besar.
MAK
20
Saya akan mengatakan ini tergantung pada implementasi javascript. Saya tidak berpikir itu didefinisikan dalam spesifikasi javascript.
Georg Schölly
9
Lihat code.stephenmorley.org/javascript/queues untuk implementasi sederhana yang meningkatkan kinerja antrian.
Gili
15
Untuk masalah kinerja Antrian, lihat perbandingan yang bagus dari tiga jenis perilaku tumpukan yang berbeda di jsperf.com/queue-push-unshift-vs-shift-pop - Sekarang jika hanya seseorang yang cukup baik untuk menyertakan putaran jsperf yang akan mengandung skrip JS yang @Gili sebutkan ...
Nenotlep
3
Saya membangkitkan kembali posting blog yang ditautkan dalam jawaban ini karena archive.org tidak selalu paling berkinerja. Saya memperbarui tautan dan gambar agar berfungsi, tetapi saya tidak mengubah apa pun.
Chev
87

Javascript memiliki metode push dan pop, yang beroperasi pada objek array Javascript biasa.

Untuk antrian, lihat di sini:

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

Antrian dapat diimplementasikan dalam JavaScript menggunakan metode push dan shift atau metode unshift dan pop objek array. Meskipun ini adalah cara sederhana untuk mengimplementasikan antrian, itu sangat tidak efisien untuk antrian besar - karena metode beroperasi pada array, metode shift dan unshift memindahkan setiap elemen dalam array setiap kali mereka dipanggil.

Queue.js adalah implementasi antrian yang sederhana dan efisien untuk JavaScript yang fungsi dequeue berjalan dalam waktu konstan diamortisasi. Akibatnya, untuk antrian yang lebih besar, dapat secara signifikan lebih cepat daripada menggunakan array.

Robert Harvey
sumber
2
Dengan tautan yang Anda bagikan memiliki fungsi untuk memeriksa hasil benchmark & ​​saya tidak melihat peningkatan kinerja ketika diuji dengan Google Chrome versi 59. Queue.js tidak konsisten dengan kecepatannya tetapi Chrome masih konsisten dengan kecepatannya.
Shiljo Paulson
Juga saya membuat demo dengan queue.js, bahwa, fungsi dequeue tidak benar-benar menghapus item dari antrian, jadi saya bertanya-tanya apakah itu seharusnya cara kerjanya? Jika demikian, bagaimana Anda dapat mengambil antrian baru setelah membagikan item sebelumnya? codepen.io/adamchenwei/pen/VxgNrX?editors=0001
Ezeewei
sepertinya dequeue di queue.js juga memerlukan memori tambahan karena kloning array dengan slice.
JaTo
Selanjutnya, array yang mendasarinya semakin besar dan lebih besar dengan setiap elemen yang ditambahkan. Meskipun implementasi mengurangi ukuran array dari waktu ke waktu, ukuran keseluruhan meningkat.
Philipp Mitterer
73

Array.

Tumpukan:

var stack = [];

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

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

Antre:

var queue = [];

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

//Take first value from queue
var value = queue.shift();
Jani Hartikainen
sumber
1
Array.prototype.pop tidak menghapus nilai dari atas (elemen pertama) dari Array. Ini menghilangkan nilai dari bawah (elemen terakhir) dari Array.
Michael Geller
21
@MichaelGeller Bagian atas tumpukan adalah elemen terakhir dari Array. Metode push dan pop array berperilaku seperti tumpukan.
mrdommyg
@mrdommyg Array.prototype.pop menghapus elemen terakhir array (lihat developer.mozilla.org/en/docs/Web/JavaScript/Reference/… ). Terakhir dalam konteks ini berarti elemen dengan indeks tertinggi. Array di JS tidak ada hubungannya dengan stack. Ini bukan tumpukan hanya karena memiliki metode pop. Pop hanya berarti "hapus elemen terakhir dan kembalikan". Tentu saja Anda dapat meniru fungsionalitas tumpukan dengan array, tetapi array masih bukan tumpukan menurut definisi. Masih daftar (objek "daftar seperti" menurut MDN).
Michael Geller
5
@MichaelGeller Perilaku stack adalah "first in, last out". Jika Anda menerapkannya menggunakan Array dalam JavaScript dengan pushdan popmetodenya, maka masalah terpecahkan. Saya benar-benar tidak mengerti maksud Anda di sini.
Rax Weber
2
@MichaelGeller Tumpukan adalah konseptual. Array JS adalah (antara lain) dengan definisi stack berdasarkan penerapan semantik stack. Hanya karena itu juga mengimplementasikan semantik array tidak mengubah itu. Anda dapat menggunakan array JS seperti tumpukan di luar kotak, dan dalam konteks itu apa yang Anda dorong dan pop adalah elemen "atas".
Hans
32

Jika Anda ingin membuat struktur data Anda sendiri, Anda bisa membuat sendiri:

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

Dan untuk antrian:

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;
};
pengguna2954463
sumber
13
Untuk menghindari perlunya mengulangi seluruh hal untuk menambahkan sampai akhir, simpan referensi ke yang terakhir melalui this.last = node;
Perkins
9
Jangan pernah menerapkan Antrian seperti ini kecuali jika Anda memiliki alasan yang sangat bagus untuk itu ... walaupun tampaknya secara logis benar, CPU tidak beroperasi sesuai dengan abstraksi manusia. Iterasi pada struktur data yang memiliki pointer di semua tempat akan menghasilkan kesalahan cache di CPU, tidak seperti array berurutan yang sangat efisien. blog.davidecoppola.com/2014/05/... CPU HATE pointer dengan hasrat membara - mereka mungkin adalah penyebab No.1 cache yang hilang dan harus mengakses memori dari RAM.
Centril
1
ini adalah solusi yang menggoda, tapi saya tidak melihat ada yang dibuat Nodedihapus ketika muncul / keluar ... bukankah mereka hanya duduk-duduk memonopoli memori sampai browser mogok?
cneuro
5
@cneuro Tidak seperti C ++, JavaScript adalah bahasa sampah yang dikumpulkan. Ia memiliki deletekata kunci, tetapi itu hanya berguna untuk menandai properti suatu objek sebagai tidak ada — yang berbeda dari hanya menetapkan undefinedke properti . JavaScript juga memiliki newoperator, tetapi itu hanya digunakan untuk mengatur thiske objek kosong baru saat memanggil fungsi. Dalam C ++ Anda harus memasangkan setiap newdengan a delete, tetapi tidak dalam JavaScript karena GC. Untuk berhenti menggunakan memori dalam JavaScript, cukup berhenti merujuk objek dan akhirnya akan direklamasi.
binki
Bukankah perlu juga memeriksa stack untuk overflow dengan mengatur ukuran max stack?
lebah
16

Implementasi Stackdan Queuepenggunaan sayaLinked 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();

Rohit
sumber
10

Pergeseran array Javascript () lambat terutama saat memegang banyak elemen. Saya tahu dua cara untuk mengimplementasikan antrian dengan kompleksitas O (1) yang diamortisasi.

Pertama adalah dengan menggunakan buffer melingkar dan penggandaan tabel. Saya sudah menerapkan ini sebelumnya. Anda dapat melihat kode sumber saya di sini https://github.com/kevyuu/rapid-queue

Cara kedua adalah dengan menggunakan dua tumpukan. Ini adalah kode untuk antrian dengan dua tumpukan

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

Ini adalah perbandingan kinerja menggunakan jsPerf

CircularQueue.shift () vs Array.shift ()

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

Seperti yang Anda lihat, ini jauh lebih cepat dengan dataset besar

kevinyu
sumber
8

Ada beberapa cara di mana Anda dapat menerapkan Stacks dan Antrian dalam Javascript. Sebagian besar jawaban di atas adalah implementasi yang cukup dangkal dan saya akan mencoba untuk mengimplementasikan sesuatu yang lebih mudah dibaca (menggunakan fitur sintaks baru dari es6) dan kuat.

Inilah implementasi stack:

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

Dan ini adalah bagaimana Anda dapat menggunakan stack:

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

Jika Anda ingin melihat uraian terperinci tentang implementasi ini dan bagaimana peningkatannya, Anda dapat membaca di sini: http://jschap.com/data-structures-in-javascript-stack/

Berikut kode untuk implementasi antrian di 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
  }
}

Inilah cara Anda dapat menggunakan implementasi ini:

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

Untuk mempelajari tutorial lengkap tentang bagaimana struktur data ini telah diterapkan dan bagaimana ini dapat ditingkatkan lebih lanjut, Anda mungkin ingin membaca seri 'Bermain dengan struktur data dalam javascript' di jschap.com. Inilah tautan untuk antrian - http://jschap.com/playing-data-structures-javascript-queues/

Anish K.
sumber
7

Anda dapat menggunakan kelas kustom Anda sendiri berdasarkan konsep, di sini potongan kode yang dapat Anda gunakan untuk melakukan hal-hal tersebut

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

dan untuk memeriksa ini gunakan konsol Anda dan coba baris ini satu per satu.

>> var st = new Stack();

>> st.push("BP");

>> st.push("NK");

>> st.getTop();

>> st.getCount();

>> st.displayAll();

>> st.pop();

>> st.displayAll();

>> st.getTop();

>> st.peek();
jforjs
sumber
2
Downvote untuk konvensi penamaan: metode yang dimulai dengan modal yang dianggap sebagai konstruktor.
Pavlo
6
/*------------------------------------------------------------------ 
 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))
Arijit Basu
sumber
5

Atau Anda dapat menggunakan dua array untuk menerapkan struktur data antrian.

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

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

Jika saya memunculkan elemen sekarang maka hasilnya akan menjadi 3,2,1. Tetapi kami ingin struktur FIFO sehingga Anda dapat melakukan hal berikut.

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
Ni3
sumber
1
Ini hanya berfungsi jika Anda tidak pernah pushsetelah pertama kali Andapop
jnnnnn
5

Berikut ini adalah implementasi antrian yang cukup sederhana dengan dua tujuan:

  • Tidak seperti array.shift (), Anda tahu metode dequeue ini membutuhkan waktu yang konstan (O (1)).
  • Untuk meningkatkan kecepatan, pendekatan ini menggunakan alokasi yang jauh lebih sedikit daripada pendekatan daftar-tertaut.

Implementasi stack hanya berbagi tujuan kedua.

// 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; };
snydergd
sumber
5

Implementasi stack sepele seperti yang dijelaskan dalam jawaban lain.

Namun, saya tidak menemukan jawaban yang memuaskan di utas ini untuk mengimplementasikan antrian di javascript, jadi saya membuatnya sendiri.

Ada tiga jenis solusi di utas ini:

  • Array - Solusi terburuk, menggunakan array.shift() array besar sangat tidak efisien.
  • Daftar tertaut - Ini O (1) tetapi menggunakan objek untuk setiap elemen agak berlebihan, terutama jika ada banyak dan mereka kecil, seperti menyimpan angka.
  • Array tunda tertunda - Ini terdiri dari mengaitkan indeks dengan array. Ketika sebuah elemen keluar, indeks bergerak maju. Ketika indeks mencapai bagian tengah array, array diiris menjadi dua untuk menghapus bagian pertama.

Array tunda tertunda adalah solusi paling memuaskan dalam pikiran saya, tetapi mereka masih menyimpan semuanya dalam satu array bersebelahan besar yang dapat bermasalah, dan aplikasi akan terhuyung-huyung ketika array diiris.

Saya membuat implementasi menggunakan daftar array array kecil (masing-masing 1000 elemen maks). Array berperilaku seperti array shift tertunda, kecuali mereka tidak pernah diiris: ketika setiap elemen dalam array dihapus, array hanya dibuang.

Paket ini pada npm dengan fungsionalitas FIFO dasar, saya baru saja mendorongnya baru-baru ini. Kode ini dibagi menjadi dua bagian.

Inilah bagian pertama

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

Dan inilah Queuekelas utamanya :

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

Ketik anotasi ( : X) dapat dengan mudah dihapus untuk mendapatkan kode javascript ES6.

coyotte508
sumber
4

Jika Anda memahami tumpukan dengan fungsi push () dan pop (), maka antrian hanya untuk membuat salah satu dari operasi ini dalam arti yang berlawanan. Oposite of push () adalah unshift () dan oposite dari pop () adalah shift (). Kemudian:

//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
Javier Giovannini
sumber
Sebuah kata peringatan bagi mereka yang menulis perangkat lunak penting kinerja. The .shift()Metode ini tidak implementasi antrian yang tepat. Ini adalah O (n) dan bukan O (1), dan akan lambat untuk antrian besar.
Rudi Kershaw
3

Ini adalah versi daftar tertaut dari antrian yang juga menyertakan simpul terakhir, seperti yang disarankan oleh @perkins dan seperti yang paling sesuai.

// 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;
};
DrByrd
sumber
Dalam dequeue, Anda harus mengembalikan temp.data. Karena itulah yang sedang antri.
bukan-robot
3

Jika Anda mencari implementasi ES6 OOP dari struktur data Stack and Queue dengan beberapa operasi dasar (berdasarkan daftar tertaut) maka mungkin terlihat seperti ini:

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

Dan implementasi LinkedList yang digunakan untuk Stack dan Antrian dalam contoh di atas dapat ditemukan di GitHub di sini .

Oleksii Trekhleb
sumber
2

Tanpa Array

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

}
Andriy
sumber
Bagaimana saya bisa menjalankan fungsi internal yang diberikan seperti push pop?
Chandan Kumar
2

Struktur Array biasa dalam Javascript adalah Stack (masuk pertama, keluar terakhir) dan juga dapat digunakan sebagai Antrian (masuk pertama, keluar pertama) tergantung pada panggilan yang Anda buat.

Periksa tautan ini untuk melihat bagaimana membuat tindakan Array seperti Antrian:

Antrian

Justin Niessner
sumber
2

Salam,

Dalam Javascript implementasi tumpukan dan antrian adalah sebagai berikut:

Tumpukan: Tumpukan adalah wadah benda yang dimasukkan dan dihapus menurut prinsip last-in-first-out (LIFO).

  • Push: Metode menambahkan satu atau lebih elemen ke ujung array dan mengembalikan panjang array yang baru.
  • Pop: Metode menghapus elemen terakhir dari array dan mengembalikan elemen itu.

Antrian: Antrian adalah wadah benda (koleksi linier) yang dimasukkan dan dihapus sesuai dengan prinsip masuk pertama keluar pertama (FIFO).

  • Unshift: Metode menambahkan satu atau lebih elemen ke awal array.

  • Shift: Metode ini menghapus elemen pertama dari array.

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

Daniel Barrientos
sumber
1
  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]
Rajesh Kumar
sumber
1

Sepertinya saya bahwa built-in array baik untuk stack. Jika Anda ingin Antrian dalam TypeScript di sini adalah implementasi

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

}

Dan inilah Jestujian untuk itu

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

Semoga seseorang menemukan ini berguna,

Bersulang,

Stu

Stuart Clark
sumber
0

Buat sepasang kelas yang menyediakan berbagai metode yang dimiliki masing-masing struktur data ini (push, pop, mengintip, dll). Sekarang implementasikan metodenya. Jika Anda terbiasa dengan konsep di balik tumpukan / antrian, ini seharusnya cukup mudah. Anda dapat menerapkan tumpukan dengan array, dan antrian dengan daftar tertaut, meskipun pasti ada cara lain untuk melakukannya. Javascript akan memudahkan ini, karena diketik dengan lemah, jadi Anda bahkan tidak perlu khawatir tentang tipe generik, yang harus Anda lakukan jika Anda menerapkannya di Java atau C #.

gema
sumber
0

Inilah Implementasi Stacks saya.

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());
Hitesh Joshi
sumber
0

Anda dapat menggunakan WeakMaps untuk mengimplementasikan properti pribadi di kelas ES6 dan manfaat dari properti String dan metode dalam bahasa JavaScript seperti di bawah ini:

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
Salar
sumber
0

Bangun Antrian menggunakan dua tumpukan.

O (1) untuk operasi enqueue dan dequeue.

class Queue {
  constructor() {
    this.s1 = []; // in
    this.s2 = []; // out
  }

  enqueue(val) {
    this.s1.push(val);
  }

  dequeue() {
    if (this.s2.length === 0) {
      this._move();
    }

    return this.s2.pop(); // return undefined if empty
  }

  _move() {
    while (this.s1.length) {
      this.s2.push(this.s1.pop());
    }
  }
}
Yuki-Pemimpi
sumber