Cách triển khai ngăn xếp trong vanilla JavaScript và ES6

Một ngăn xếp là một bộ sưu tập có thứ tự các mặt hàng mà theo cuối Trong First Out nguyên tắc (LIFO). Việc thêm và bớt các mục diễn ra ở cùng một đầu, tức là ở đầu. Các phần tử mới nhất nằm ở trên cùng và các phần tử cũ nhất ở dưới cùng.

Chúng ta có nhiều ví dụ về các ngăn xếp xung quanh chúng ta như một chồng sách, một khay hoặc bát đĩa, v.v.

Một ngăn xếp được sử dụng bởi trình biên dịch bằng các ngôn ngữ lập trình, bởi bộ nhớ máy tính để biến cửa hàng và các cuộc gọi chức năng, và trong soạn thảo văn bản để thực hiện undo & hoạt động redo.

Danh sách các hoạt động được thực hiện trên Stack

  • push () : Thêm một hoặc nhiều mục vào đầu Ngăn xếp.
  • pop () : Loại bỏ và Trả về mục trên cùng của Ngăn xếp.
  • peek () : Trả về mục trên cùng của Ngăn xếp.
  • isEmpty () : Trả về Truenếu Stack trống, Falsengược lại.
  • clear () : Xóa tất cả các mục khỏi Ngăn xếp.
  • size () : Trả về chiều dài của ngăn xếp.

Tạo ngăn xếp

Một cách tiếp cận cổ điển

Chúng tôi sẽ triển khai một ngăn xếp giống như cách nó được triển khai trong các ngôn ngữ khác ngoài JavaScript.

Chúng tôi sẽ sử dụng một mảng và một biến phụ để theo dõi các mục.

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

Đẩy một mục vào ngăn xếp

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

Mở một mục từ Ngăn xếp

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

Xem mục hàng đầu từ Ngăn xếp

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

Kiểm tra xem Ngăn xếp có trống không

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

Xóa ngăn xếp

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

Kích thước của ngăn xếp

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

Hoàn thành việc triển khai Ngăn xếp

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

Thí dụ

Bây giờ chúng tôi sẽ tạo một phiên bản mới về những gì chúng tôi đã triển khai và kiểm tra xem nó có hoạt động chính xác hay không.

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

Triển khai ngăn xếp với JavaScript

Chúng tôi sẽ triển khai một ngăn xếp với một mảng JavaScript có các phương thức có sẵn như pushpop.

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

Đẩy một mục vào ngăn xếp

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

Mở một mục từ Ngăn xếp

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

Xem mục hàng đầu từ Ngăn xếp

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

Kiểm tra xem Ngăn xếp có trống không

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

Xóa ngăn xếp

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

Kích thước của ngăn xếp

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

Hoàn thành việc triển khai 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; } 
}

Đặt các thuộc tính và phương thức ở chế độ riêng tư với bao đóng và IIFE (Biểu thức hàm được gọi ngay lập tức).

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

Ngăn xếp bằng 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; }}

Ngăn xếp bằng 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; }}

Đặt các thuộc tính và phương thức ở chế độ riêng tư với hàm đóng và IIFE (Biểu thức hàm được gọi ngay lập tức) cho Stack bằng 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; } }})();

Thời gian phức tạp

# Trung bình cộng

Truy cập: Θ (N)

Tìm kiếm: Θ (N)

Chèn: Θ (1)

Xóa: Θ (1)

# Tệ nhất

Truy cập: O (N)

Tìm kiếm trên)

Chèn: O (1)

Xóa: O (1)

Không gian phức tạp

# Tồi tệ nhất : O (N)

Có rất nhiều vấn đề trong đó Stack có thể là cấu trúc dữ liệu hoàn hảo cần thiết cho giải pháp.

  • Thuật toán chuyển đổi cơ sở
  • Dấu ngoặc đơn cân đối

Nếu bạn thích bài viết này, hãy cho nó một ít? Và chia sẻ nó! Nếu bạn có bất kỳ câu hỏi nào liên quan đến vấn đề này, hãy hỏi tôi.

Để biết thêm thông tin như thế này và các giải pháp thuật toán trong Javascript, hãy theo dõi tôi trên Twitter . Tôi viết về ES6, Phản ứng, Nodejs, cấu trúc dữ liệu, thuật toán và trên learnersbucket.com .