Stacks

Giới thiệu

Là cấu trúc dữ liệu LIFO (Last In First Out).

Stacks được dùng để xử lý lời gọi hàm (call stack), chức năng undo/redo, cho routing, …

Khởi tạo

Tạo stack từ linked list

class NodeLinkedList { value: string; next: NodeLinkedList | null; constructor(value) { this.value = value; this.next = null; }
} class Stack { top: NodeLinkedList | null; size: number;
}

Khởi tạo các method

push

 push(val) { const newNode = new NodeLinkedList(val); if (!this.top) { this.top = newNode; } else { newNode.next = this.top; this.top = newNode; } this.size++; return this; }

pop

 pop() { if (!this.top) return null; const poppedValue = this.top.value; this.top = this.top.next; this.size--; return poppedValue; }

Độ phức tạp

Queues

Là kiểu dữ liệu FIFO (Fist In First Out)

Khởi tạo

Khởi tạo từ linked list

class NodeLinkedListQueue { value: string; next: NodeLinkedListQueue | null; constructor(value) { this.value = value; this.next = null; }
} class Queue { rear: NodeLinkedListQueue | null; front: NodeLinkedListQueue | null; size: number; constructor() { this.rear = null; this.front = null; this.size = 0; } enqueue(val) {} dequeue() {}
}

Khởi tạo các method

enqueue

 enqueue(val) { const newNode = new NodeLinkedListQueue(val); if (!this.rear) { this.rear = newNode; this.front = newNode; } else { this.front.next = newNode; this.front = newNode; } this.size++; return this; }

dequeue

 dequeue() { if (!this.front) return null; const dequeueValue = this.rear.value; this.rear = this.rear.next; return dequeueValue; }

Độ phức tạp