Stack và queue là 2 từ khoá luôn đi chung với nhau trong các bài toán giải thuật và cấu trúc dữ liệu. Vậy chúng là gì ? Theo dõi bài viết bên dưới của mình nhé
Stack
Hay còn gọi là hàng đợi một cấu trúc dữ liệu phổ biến trong lập trình. Nguyên tắc của nó là Last In First Out (Vào cuối nhưng ra trước)
Ứng dụng:
- Undo/Redo
- Browser history (forward, backward)
- Function stack in JS (callback)
Queue
Hay còn gọi là hàng đợi, cũng là một cấu trúc dữ liệu rất phổ biến trong lập trình. Khác với Stack, Queue có nguyên lý hoạt động như tên gọi của nó First In First Out (Vào trước thì ra trước)
Ứng dụng
- Máy in
- Hàng đợi
- Message queue
Tại sao nên dùng LinkedList để implement thành Stack và Queue hơn Array ?
Với Array
Với Queue
Khi thêm 1 item vào. cuối -> Độ phức tạp thường sẽ là O(1), tuy nhiên, trường hợp xâu nhất của JS (Trong JS Array là Dymanic Array, xem thêm >> Sự khác nhau giữa Static và Dynamic Arrays là gì ?) sẽ tự động phân bổ lại bộ nhớ và khi thêm vào cuối của mảng (Worst case => O(n))
Khi dequeue một phần tử đầu tiên (Xoá) sử dụng Array => Độ phức tạp là O(n) Vì các item array nếu xoá ở các phần tử đầu phải dịch chuyển lên trên
Javascript là Garbage collected language ?
Là gì ? Đây là một khái niệm về việc xoá các bộ nhớ dư thừa. Mình sẽ đề cập sau trong các bài viết tiếp theo
Xây dựng cấu trúc dữ liệu Stack sử dụng LinkedList
class Node {
value: any
next: any
constructor(value: any) {
this.value = value;
this.next = null;
}
}
export class Stack {
top: any
bottom: any
length: number
constructor() {
this.top = null;
this.bottom = null;
this.length = 0;
}
peek() {
return this.top
}
push(value: any) {
const newNode = new Node(value)
if (this.length == 0) {
this.top = newNode
this.bottom = newNode
} else {
const holdingPointer = this.top
this.top = newNode
this.top.next = holdingPointer
}
this.length++
return this
}
pop() {
if (!this.top) return null
const holderPointer = this.top
this.top = this.top.next
if (this.top == null) {
this.bottom = null
}
this.length--
return holderPointer
}
isEmpty() {
return this.length === 0
}
//isEmpty
}
const myStack = new Stack();
myStack.push(1)
myStack.push(3)
myStack.push(100)
myStack.push(3000)
console.log("myStack", myStack);
console.log("myStack", myStack.pop());
// console.log("myStack.pop()", myStack.pop());
// console.log("myStack", myStack);
// console.log("peek", myStack.peek());Xây dựng cấu trúc dữ liệu Queue sử dụng LinkedList
class Node {
value: any;
next: any;
constructor(value: any) {
this.value = value;
this.next = null;
}
}
export class Queue {
// Dùng Single LinkedList là được rồi!
first: any;
last: any;
length: number;
constructor() {
this.first = null;
this.last = null;
this.length = 0;
}
peek() {
return this.first
}
enqueue(value: any) {
const newNode = new Node(value)
if (this.length === 0) {
this.first = newNode
this.last = newNode
} else {
this.last.next = newNode
this.last = newNode
}
this.length++
return this.last
}
dequeue() {
if (!this.first) return null
const holder = this.first
if (this.first == this.last) {
this.last = null // Special case (When there is only one element)
}
this.first = this.first.next;
this.length--
return holder
}
isEmpty() {
return this.length === 0
}
//isEmpty;
}
const myQueue = new Queue();
myQueue.enqueue('Joy');
myQueue.enqueue('Matt');
myQueue.enqueue('Pavel');
myQueue.enqueue('Samir');
// console.log("myQueue", myQueue);
// myQueue.dequeue();
// myQueue.dequeue();
console.log("dequeue", myQueue.dequeue());
// console.log("myQueue after dequeue", myQueue);
//Joy
//Matt
//Pavel
//SamirReviews Stack and Queue
Liên quan
Đây là nội dung bài viết mình lấy nguồn từ khoá học của udemy.
Các bạn có thể thao dõi khoá học tại đây nhé: https://www.udemy.com/course/master-the-coding-interview-big-tech-faang-interviews/
#algorithm #data-structure #stack-queue
