Sự khác biệt giữa Stack và Queue

NộI Dung

Biểu đồ so sánh
Định nghĩa về ngăn xếp
Thí dụ
Định nghĩa hàng đợi
Thí dụ
Thực hiện ngăn xếp
Thực hiện xếp hàng
Hoạt động trên Stack
Hoạt động trên hàng đợi
Các ứng dụng của Stack
Ứng dụng của hàng đợi
Phần kết luận

Stack và Queue đều là các cấu trúc dữ liệu không nguyên thủy. Sự khác biệt chính giữa ngăn xếp và hàng đợi là ngăn xếp sử dụng phương thức LIFO (lần cuối ra trước) để truy cập và thêm các phần tử dữ liệu trong khi Queue sử dụng phương thức FIFO (First in First out) để truy cập và thêm các phần tử dữ liệu.

Stack chỉ có một đầu mở để đẩy và bật các phần tử dữ liệu, mặt khác Queue có cả hai đầu mở để thu hút và loại bỏ các phần tử dữ liệu.

Ngăn xếp và hàng đợi là các cấu trúc dữ liệu được sử dụng để lưu trữ các yếu tố dữ liệu và thực sự dựa trên một số tương đương trong thế giới thực. Ví dụ, ngăn xếp là một chồng đĩa CD, nơi bạn có thể lấy ra và đưa vào đĩa CD thông qua đỉnh của ngăn xếp đĩa CD. Tương tự, Hàng đợi là hàng đợi cho các vé của Nhà hát nơi người đứng ở vị trí đầu tiên, tức là, phía trước hàng đợi sẽ được phục vụ trước và người mới đến sẽ xuất hiện ở phía sau hàng đợi (phía sau hàng đợi).

Biểu đồ so sánh
Định nghĩa
Sự khác biệt chính
Thực hiện
Hoạt động
Các ứng dụng
Phần kết luận

Biểu đồ so sánh


Cơ sở để so sánh	Cây rơm	Xếp hàng
Nguyên tắc làm việc	LIFO (Lần cuối ra mắt trước)	FIFO (First in First out)
Kết cấu	Cùng một kết thúc được sử dụng để chèn và xóa các yếu tố.	Một đầu được sử dụng để chèn, tức là, phía sau và một đầu khác được sử dụng để xóa các yếu tố, tức là, mặt trước.
Số con trỏ được sử dụng	Một	Hai (Trong trường hợp xếp hàng đơn giản)
Hoạt động được thực hiện	Đẩy và bật	Enqueue và dequeue
Kiểm tra tình trạng trống	Đầu == -1	Mặt trận == -1 \|\| Mặt trước == Phía sau + 1
Kiểm tra tình trạng đầy đủ	Hàng đầu == Tối đa - 1	Phía sau == Tối đa - 1
Biến thể	Nó không có các biến thể.	Nó có các biến thể như hàng đợi tròn, hàng đợi ưu tiên, hàng đợi gấp đôi kết thúc.
Thực hiện	Đơn giản hơn	Tương đối phức tạp

Định nghĩa về ngăn xếp

Một Stack là một cấu trúc dữ liệu tuyến tính không nguyên thủy. Đó là một danh sách được sắp xếp trong đó mục mới được thêm vào và phần tử hiện có bị xóa khỏi chỉ một đầu, được gọi là đỉnh của ngăn xếp (TOS). Vì tất cả việc xóa và chèn trong ngăn xếp được thực hiện từ đỉnh ngăn xếp, phần tử cuối cùng được thêm vào sẽ là phần tử đầu tiên được xóa khỏi ngăn xếp. Đó là lý do tại sao stack được gọi là loại danh sách Last-in-First-out (LIFO).

Lưu ý rằng phần tử thường được truy cập trong ngăn xếp là phần tử trên cùng, trong khi phần tử có sẵn cuối cùng nằm ở dưới cùng của ngăn xếp.

Thí dụ

Một số bạn có thể ăn bánh quy (hoặc Poppin). Nếu bạn giả sử, chỉ có một mặt của vỏ bị rách, và bánh quy được lấy ra từng cái một. Đây là cái được gọi là popping, và tương tự, nếu bạn muốn bảo quản một số bánh quy trong một thời gian sau đó, bạn sẽ đặt chúng trở lại vào gói thông qua cùng một đầu bị rách được gọi là đẩy.

Định nghĩa hàng đợi

Hàng đợi là một cấu trúc dữ liệu tuyến tính thuộc loại không nguyên thủy. Nó là một tập hợp các loại yếu tố tương tự. Việc bổ sung các yếu tố mới diễn ra ở một đầu được gọi là phía sau. Tương tự như vậy, việc xóa các phần tử hiện có diễn ra ở đầu kia được gọi là Front-end và nó là loại danh sách đầu tiên trong danh sách đầu tiên (FIFO).

Thí dụ

Trong cuộc sống hàng ngày của chúng tôi, chúng tôi gặp rất nhiều tình huống để chờ đợi dịch vụ mong muốn, ở đó chúng tôi phải xếp hàng chờ đến lượt để được phục vụ. Hàng đợi này có thể được coi là một hàng đợi.

Mặt khác, ngăn xếp theo cơ chế LIFO Hàng đợi theo cơ chế FIFO để thêm và xóa các phần tử.
Trong một ngăn xếp, cùng một kết thúc được sử dụng để chèn và xóa các phần tử. Ngược lại, hai đầu khác nhau được sử dụng trong hàng đợi để chèn và xóa các phần tử.
Vì Stack chỉ có một kết thúc mở, đó là lý do chỉ sử dụng một con trỏ để chỉ đỉnh của ngăn xếp. Nhưng hàng đợi sử dụng hai con trỏ để chỉ phía trước và phía sau của hàng đợi.
Stack thực hiện hai thao tác được gọi là đẩy và bật trong khi ở Queue, nó được gọi là enqueue và dequeue.
Việc thực hiện ngăn xếp dễ dàng hơn trong khi thực hiện xếp hàng là khó khăn.
Hàng đợi có các biến thể như hàng đợi tròn, hàng đợi ưu tiên, hàng đợi kết thúc gấp đôi, v.v ... Ngược lại, ngăn xếp không có các biến thể.

Thực hiện ngăn xếp

Ngăn xếp có thể được áp dụng theo hai cách:

Triển khai tĩnh sử dụng mảng để tạo một ngăn xếp. Triển khai tĩnh mặc dù là một kỹ thuật dễ dàng nhưng không phải là cách tạo linh hoạt, vì việc khai báo kích thước của ngăn xếp phải được thực hiện trong quá trình thiết kế chương trình, sau đó kích thước không thể thay đổi. Ngoài ra, triển khai tĩnh không hiệu quả lắm đối với việc sử dụng bộ nhớ. Vì một mảng (để thực hiện ngăn xếp) được khai báo trước khi bắt đầu hoạt động (tại thời điểm thiết kế chương trình). Bây giờ nếu số lượng phần tử được sắp xếp rất ít trong ngăn xếp, bộ nhớ được phân bổ tĩnh sẽ bị lãng phí. Mặt khác, nếu có nhiều số phần tử được lưu trữ trong ngăn xếp thì chúng ta có thể thay đổi kích thước của mảng để tăng dung lượng của nó, để nó có thể chứa các phần tử mới.
Triển khai động cũng được gọi là biểu diễn danh sách được liên kết và sử dụng các con trỏ để thực hiện kiểu ngăn xếp của cấu trúc dữ liệu.

Thực hiện xếp hàng

Hàng đợi có thể được thực hiện theo hai cách:

Triển khai tĩnh: Nếu hàng đợi được triển khai bằng cách sử dụng mảng, số lượng phần tử chính xác mà chúng tôi muốn lưu trữ trong hàng đợi phải được đảm bảo trước, bởi vì kích thước của mảng phải được khai báo tại thời điểm thiết kế hoặc trước khi quá trình xử lý bắt đầu. Trong trường hợp này, phần đầu của mảng sẽ trở thành mặt trước của hàng đợi và vị trí cuối cùng của mảng sẽ đóng vai trò là mặt sau của hàng đợi. Mối quan hệ sau đây cung cấp cho toàn bộ các phần tử tồn tại trong hàng đợi khi được triển khai bằng cách sử dụng mảng:
trước - sau + 1
Nếu phía sau phía trước <phía trước thì sẽ không có phần tử nào trong hàng đợi hoặc hàng đợi sẽ luôn trống.
Triển khai động: Thực hiện hàng đợi bằng cách sử dụng các con trỏ, nhược điểm chính là một nút trong biểu diễn được liên kết sẽ tiêu tốn nhiều dung lượng bộ nhớ hơn một phần tử tương ứng trong biểu diễn mảng. Vì có ít nhất hai trường trong mỗi nút một cho trường dữ liệu và trường khác để lưu địa chỉ của nút tiếp theo trong khi trong trường đại diện được liên kết chỉ có trường dữ liệu ở đó. Ưu điểm của việc sử dụng biểu diễn được liên kết trở nên rõ ràng khi được yêu cầu chèn hoặc xóa một phần tử ở giữa một nhóm các phần tử khác.

Hoạt động trên Stack

Các hoạt động cơ bản có thể được vận hành trên ngăn xếp như sau:

ĐẨY: khi một phần tử mới được thêm vào đầu ngăn xếp được gọi là hoạt động PUSH. Đẩy một phần tử trong ngăn xếp gọi thêm phần tử, vì phần tử mới sẽ được chèn ở trên cùng. Sau mỗi hoạt động đẩy, đỉnh được tăng thêm một. Nếu mảng đầy, và không có phần tử mới nào có thể được thêm vào, nó được gọi là điều kiện STACK-FULL hoặc STACK OVERFLOW. HOẠT ĐỘNG PUSH - chức năng trong C:
Xem xét ngăn xếp được tuyên bố là
int stack, top = -1;
khoảng trống đẩy ()
{
mục int;
nếu (trên <4)
{
f ("Nhập số");
quét ("% d", & mục);
đầu = đỉnh + 1;
ngăn xếp = vật phẩm;
}
khác
{
f ("Ngăn xếp đã đầy");
}
}
POP: Khi một phần tử bị xóa khỏi đỉnh ngăn xếp, nó được gọi là hoạt động POP. Ngăn xếp được giảm đi một, sau mỗi hoạt động pop. Nếu không còn phần tử nào trên ngăn xếp và pop được thực hiện, thì điều này sẽ dẫn đến điều kiện STACK UNDERFLOW có nghĩa là ngăn xếp của bạn trống. HOẠT ĐỘNG POP - các chức năng trong C:
Xem xét ngăn xếp được tuyên bố là
int stack, top = -1;
khoảng trống pop ()
{
mục int;
nếu (đầu> = 4)
{
mục = ngăn xếp;
đầu = đỉnh - 1;
f ("Số đã xóa là =% d", mục);
}
khác
{
f ("Ngăn xếp trống");
}
}

Hoạt động trên hàng đợi

Các hoạt động cơ bản có thể được thực hiện trên hàng đợi là:

Enqueue: Để chèn một phần tử trong hàng đợi. Hàm hoạt động hấp dẫn trong C:
Hàng đợi được khai báo là
int queue, Front = -1 và phía sau = -1;
khoảng trống thêm ()
{
mục int;
nếu (phía sau <4)
{
f ("Nhập số");
quét ("% d", & mục);
nếu (phía trước == -1)
{
phía trước = 0;
phía sau = 0;
}
khác
{
phía sau = phía sau + 1;
}
hàng đợi = vật phẩm;
}
khác
{
f ("Hàng đợi đã đầy");
}
}
Dequeue: Để xóa một phần tử khỏi hàng đợi. Hàm hoạt động hấp dẫn trong C:
Hàng đợi được khai báo là
int queue, Front = -1 và phía sau = -1;
khoảng trống xóa ()
{
mục int;
nếu (phía trước! = -1)
{
mục = xếp hàng;
if (phía trước == phía sau)
{
phía trước = -1;
phía sau = -1;
}
khác
{
phía trước = phía trước + 1;
f ("Số đã xóa là =% d", mục);
}
}
khác
{
f ("Hàng đợi trống");
}
}

Các ứng dụng của Stack

Phân tích cú pháp trong một trình biên dịch.
Máy ảo Java.
Hoàn tác trong một trình xử lý văn bản.
Nút quay lại trong trình duyệt Web.
Ngôn ngữ PostScript cho ers.
Thực hiện các cuộc gọi chức năng trong một trình biên dịch.

Ứng dụng của hàng đợi

Bộ đệm dữ liệu
Truyền dữ liệu không đồng bộ (tệp IO, đường ống, ổ cắm).
Phân bổ các yêu cầu trên một tài nguyên được chia sẻ (er, bộ xử lý).
Phân tích giao thông.
Xác định số lượng nhân viên thu ngân tại siêu thị.

Phần kết luận

Stack và Queue là các cấu trúc dữ liệu tuyến tính khác nhau theo các cách nhất định như cơ chế làm việc, cấu trúc, cách thực hiện, các biến thể nhưng cả hai đều được sử dụng để lưu trữ các phần tử trong danh sách và thực hiện các hoạt động trong danh sách như thêm và xóa các phần tử. Mặc dù có một số hạn chế của hàng đợi đơn giản được thu lại bằng cách sử dụng các loại hàng đợi khác.