2015-08-22 23 views
5

Gần đây tôi đã bắt đầu tìm hiểu cấu trúc dữ liệu và chỉ có triển khai danh sách được liên kết của riêng tôi. Bây giờ tôi vấp phải hai cấu trúc dữ liệu mới: stack và queue.
Từ những gì tôi đã học cho đến nay, ngăn xếp là danh sách được liên kết cho phép chèn/xóa chỉ từ đuôi của nó và hàng đợi là danh sách được liên kết chỉ cho phép chèn vào đuôi và chỉ xóa khỏi đầu.Ngăn xếp, hàng đợi và danh sách liên kết

Câu hỏi của tôi là: tại sao tôi nên sử dụng hai cấu trúc dữ liệu này thay vì danh sách được liên kết thông thường cho phép chèn và xóa khỏi mọi nơi? Ngoài ra, tại sao hai cấu trúc dữ liệu này được phân loại là cấu trúc dữ liệu độc lập chứ không phải là "danh sách liên kết truy cập hạn chế"?

+1

ngăn xếp và hàng đợi là trừu tượng cơ bản về DS. chúng không cần thiết phải được triển khai bằng danh sách được liên kết. stack và queue đại diện cho hai thuộc tính chúng ta muốn trong cuộc sống hàng ngày của chúng ta, FILO và FIFO, tương ứng. – HuStmpHrrr

Trả lời

12

Ngăn xếp và hàng đợi có lý do tồn tại riêng. Ngăn xếp là cấu trúc dữ liệu FILO (Đầu tiên cuối cùng) hoặc LIFO (hai cách) có thể được triển khai bằng cách sử dụng mảng, danh sách liên kết hoặc các biểu mẫu khác. Xem xét lịch sử trình duyệt. Bạn điều hướng đến Trang web A -> sau đó B -> sau đó C ->D. Khi người dùng di chuyển về phía trước, trước tiên bạn hãy đẩy (chèn vào đuôi) danh sách trang web. Điều này đảm bảo rằng trang hiện tại luôn ở trên cùng của ngăn xếp. Stack in action

Sau đó, khi người dùng chạm lại nút, bạn pop một ở phía trên (hoặc bỏ ra khỏi đuôi - cuối cùng được sử dụng để chèn) mà cung cấp cho các trang web đã ghé thăm - C. Do đó, khái niệm về Đầu Năm (mà là Site A) và Out cuối (người cuối cùng để đi vào là Site D mà lần lượt trở thành người đầu tiên đi ra ngoài)

tương tự có thể nói cho hàng đợi đó là FIFO (First In First Out). Hãy xem xét ví dụ về hàng đợi công việc. Khi thực hiện một công việc, bạn sẽ (không xem xét bất kỳ thuật toán tối ưu hóa nào) phục vụ người đầu tiên đến. Điều này làm cho hàng đợi một cấu trúc dữ liệu tuyệt vời để xử lý công việc trên cơ sở đầu tiên đến trước được phục vụ trước.

Trong cả hai trường hợp, bạn sẽ không muốn loại bỏ tùy ý hoặc chèn phần tử vào bất kỳ chỉ mục nào. Không, điều đó sẽ dẫn đến một hành vi không mong muốn. Do đó, sự cần thiết cho stack/queue. Tôi một lần nữa nhấn mạnh rằng ngăn xếp/hàng đợi có thể được thực hiện bằng cách thực thi các hạn chế về danh sách được liên kết.

Xin lỗi vì chất lượng hình ảnh kém - tôi vừa vẽ nó bằng sơn.

+2

ẩn dụ gọn gàng bằng trình duyệt web! – ponderingdev

2

Ngăn xếp về cơ bản là cấu trúc dữ liệu theo sau LIFO (LAST IN FIRST OUT). Hàng đợi là một trong đó sau FIFO (FIRST IN FIRST OUT).

Nói chung, StacksQueues thể được thực hiện bằng ArraysLinked Lists.

Lý do bạn sử dụng Linked List để triển khai Stack là khi bạn cần một chức năng liên quan đến biểu mẫu LAST IN FIRST OUT và bạn không chắc chắn có bao nhiêu yếu tố mà chức năng yêu cầu. Vì vậy, bạn sẽ sử dụng LinkedList tạo các nút động tùy thuộc vào yêu cầu.

Cùng đi cho Queues

Lý do cả hai đều độc lập là vì cả hai làm theo nguyên tắc khác nhau tức là LIFO và FIFO tương ứng.

+0

Cảm ơn bạn TFrost – yyk

Các vấn đề liên quan