Data structure - Queue và Stack

Mình vô tình thấy chủ đề này trên web :slight_smile: có nhiều bạn nói về nó nên hôm nay mình xin mạnh dạn chia sẻ tổng hợp lại thành 1 bài này giúp ai cần chúng có thể biết thêm về QUEUESTACK .

I. Data structure - Queue

1. Khái niệm

Hàng đợi (Queue) là một cấu trúc dữ liệu trừu tượng. Đặc điểm của hàng đợi là FIFO (first in first out) - có nghĩa là vào trước ra trước. Đặt tên là hàng đợi bởi vì nó là một cái gì đó tương tự như hàng đợi trong đời sống hàng ngày (xếp hàng).

Khác với ngăn xếp, hàng đợi là mở ở cả hai đầu. Một đầu luôn luôn được sử dụng để chèn dữ liệu vào (hay còn gọi là sắp vào hàng) và đầu kia được sử dụng để xóa dữ liệu (rời hàng). Cấu trúc dữ liệu hàng đợi tuân theo phương pháp First-In-First-Out, tức là dữ liệu được nhập vào đầu tiên sẽ được truy cập đầu tiên.


Biểu diễn cấu trúc dữ liệu hàng đợi (Queue)

Giờ thì có lẽ bạn đã tưởng tượng ra hàng đợi là gì rồi. Chúng ta có thể truy cập cả hai đầu của hàng đợi. Dưới đây là biểu diễn hàng đợi dưới dạng cấu trúc dữ liệu:

Cấu trúc dữ liệu hàng đợi (Queue)

Tương tự như cấu trúc dữ liệu ngăn xếp, thì cấu trúc dữ liệu hàng đợi cũng có thể được triển khai bởi sử dụng Mảng (Array), Danh sách liên kết (Linked List), Con trỏ (Pointer) và Cấu trúc (Struct). Để đơn giản, phần tiếp theo chúng ta sẽ tìm hiểu tiếp về hàng đợi được triển khai bởi sử dụng mảng một chiều.

2. Ví dụ

  • Trong đời sống thực chúng ta có rất nhiều ví dụ về hàng đợi, chẳng hạn như hàng xe ô tô trên đường một chiều (đặc biệt là khi tắc xe), trong đó xe nào vào đầu tiên sẽ thoát ra đầu tiên. Một vài ví dụ khác là xếp hàng học sinh, xếp hàng mua vé, …

II. Data Structure - Stack

1. Khái niệm

Stack (ngăn xếp) là một cấu trúc dữ liệu hoạt động theo nguyên lý LIFO (vào sau ra trước)

Một ngăn xếp là như một thùng chứa, nó chứa các dữ liệu bên trong thùng chứa đó

Cơ chế của stack là dữ liệu được đưa vào (push) và khi muốn lấy ra thì sẽ lấy dữ liệu từ mới nhất đến cũ nhất (pop) cho tới khi stack trống

Sau khi đọc khái niệm nếu các bạn còn thấy mơ hồ thì hãy qua phần ví dụ, mình sẽ ví dụ cụ thể hơn về stack

2. Ví dụ

Có nhiều bài viết có lấy ví dụ về chồng đĩa (không biết là đĩa DVD thời xưa hay là đĩa đựng thức ăn nữa)

Nhưng để dễ hình dung hơn khi đang đọc bài viết này, mình sẽ lấy một ví dụ đơn giản ngay trên trình duyệt bạn đang online

Khi bạn truy cập vào trình duyệt, search Google và bạn nhấn vào Kết quả tìm kiếm nào đó (ví dụ là link 1), sau đó bạn lại nhấn vào link 2, link 3,… nghĩa là bạn đã đẩy vào stack theo thứ tự link 1 → link 2 → link 3 → …

Và khi bạn nhấn nút back ở góc trên bên trái thì bạn sẽ được quay lại theo từng link là link 3 → link 2 → link 1

III. Kết luận

  • Bài viết sẽ trình nói về 2 cấu trúc dữ liệu khá cơ bản nhưng cực kì quan trong lập trình là Stack và Queue, về cách cài đặt cũng như ứng dụng của 2 cấu trúc dữ liệu này trên thực tế mà mình đã tổng hợp được từ một số trang khác nhau
  • Mong rằng bài này sẽ giúp được các bạn có thể biết thêm về 2 món này.
  • Cảm ơn và chúc các bạn học tốt! :vulcan_salute: