Bạn chán việc, bạn muốn tìm một công việc làm thêm ngoài giờ. Bạn lên mạng và tìm xem có công việc nào phù hợp và gửi CV. Bạn pass vòng CV và tiến tới buổi phỏng vấn, trong buổi phỏng vấn một ông dev lạ hoắc tiến vào và bạn nghĩ rằng tên này có khi kém cả tuổi mình. Và trong quá trình interview hắn hỏi một câu đơn giản: Bạn còn nhớ Stack & Queue không, sự khác nhau giữa Stack & Queue là gì?

Ồ, khá đơn giản nhỉ, Stack là LIFO tức last in first out, Queue thì ngược lại là FIFO – fist in first out. Vậy là bạn đã pass vòng phỏng vấn. Oh no, đó là cách một vài công ty đang sử dụng để phỏng vấn ứng viên về thuật toán. Nhưng khi phỏng vấn cho một remote job thì lại khác. Nhà tuyển dụng đưa ra một câu hỏi: Do you know about Stack & Queue. Can you show me a short pseudo code of Stack and Queue? Đến đây nếu bạn chưa chuẩn bị kiến thức về thuật toán cho buổi phỏng vấn hoặc bạn là một đứa học thuật toán nhàng nhàng ở trường Đại học thì bạn chết ngắc. Bộ não của bạn đang tự nói với chính nó: A đù, năm năm đi làm tao có phải đụng vào thuật toán bao giờ đâu, làm sao viết được cái gì. Nếu bạn giống mình thì hôm nay chúng ta ôn lại về Stack và Queue.

Về cơ bản, Stack và Queue đều có 4 method, trong khi Stack là lookup, post, put, peek thì Queue là lookup, enqueue, dequeue, peek. Còn một điều quan trọng, Stack có thể khởi tạo từ Array hoặc Link List, còn Queue thì chỉ nên khởi tạo bằng Link List.

Create queue from list is really bad because we need re-index all list when use any update action with Queue. So we always create a queue from a Link List

StackQueue
Create FromArray & Link ListLink List
Method lookup: loop in stack
pop: remove first item
push: add an item
peek: read the first item
lookup: loop in queue
enqueue: add item in queue
dequeue: remove item in queue
peek: read the first item

Đến đây có lẽ bạn sẽ nhớ ra một chút về kiến thức đã học từ thời đại học rồi chứ. Nhưng câu hỏi quan trọng là làm sao để viết pseudo code cho Stack và Queue. Đề bài sẽ giống như thế này.

Write code to create a normal Stack:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


class Stack:
    def __init__(self):
        self.top = None
        self.bottom = None
        self.length = 0
    
    # read the first Item
    def peek(self):
        pass

    # Add an Item and return Stack
    def push(self, value):
        pass
    
    # Remove first Item and return Stack 
    def pop(self):
        pass

stack_instance = Stack()

Write code to create a normal Queue:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

    def __str__(self):
        return self.value


class Queue:
    def __init__(self):
        self.first = None
        self.last = None
        self.length = 0
    
    # read the first Item
    def peek(self):
        pass

    # Add an Item and return Queue
    def enqueue(self, value):
        pass
    
    # Remove first Item and return Queue 
    def dequeue(self):
        pass
    
queue_instance = Queue()

Và tất nhiên, vì mình đang học lại datastructure nên mình đã code lại với python và đáp án mình để ở đây: https://github.com/Longdh57/datastructure/blob/master/Stack%20%26%20Queue.ipynb

Sau khi các bạn hoàn thành bài tập có thể so sánh với đáp án nhé.

Vậy là xong một datatastructure cơ bản nhất: Stack & Queue