Tại sao và khi nào tôi nên sử dụng cấu trúc dữ liệu xếp chồng hoặc xếp hàng thay vì mảng/danh sách? Bạn có thể vui lòng hiển thị một ví dụ cho một trạng thái thats nó sẽ được tốt hơn nếu bạn sẽ sử dụng stack hoặc hàng đợi?Ngăn xếp và Hàng đợi, Tại sao?
Vì chúng giúp quản lý dữ liệu của bạn theo cách cụ thể hơn so với mảng và danh sách.
Queue là lần đầu tiên trong, đầu tiên ra (FIFO)
Stack là cuối cùng trong, đầu tiên ra (LIFO)
Mảng và danh sách đang truy cập ngẫu nhiên. Chúng rất linh hoạt và dễ bị hỏng. NẾU bạn muốn quản lý dữ liệu của bạn như FIFO hoặc LIFO, tốt nhất là sử dụng dữ liệu đó, đã được triển khai, các bộ sưu tập.
"Danh sách" khi phân biệt với "mảng" thường ngụ ý một danh sách được liên kết, vì vậy không chính xác truy cập ngẫu nhiên. – Porculus
@Porculus: Tùy thuộc vào môi trường. .Net có một danh sách chung <> collection và một lớp ArrayList từ 1.0 cho phép truy cập ngẫu nhiên thông qua toán tử []. Việc triển khai danh sách được liên kết được đặt tên cụ thể là LinkedList –
Tôi muốn nói rằng các giao diện đơn giản hơn cho phép triển khai thêm vĩ độ của chúng. Và luôn luôn có ví dụ tìm kiếm cổ điển, nơi chiều sâu đầu tiên trở thành bề rộng đầu tiên bằng cách thay thế một hàng đợi cho một chồng và khác với hàng đợi ưu tiên. – wowest
Khi bạn muốn thực thi một mẫu sử dụng nhất định trên cấu trúc dữ liệu của mình. Nó có nghĩa là khi bạn đang gỡ lỗi một vấn đề, bạn sẽ không phải tự hỏi nếu ai đó chèn ngẫu nhiên một phần tử vào giữa danh sách của bạn, làm rối tung lên một số bất biến.
Đó là vấn đề. Ngăn xếp và hàng đợi thường được thực hiện bằng cách sử dụng mảng và danh sách, nhưng việc thêm và xóa các phần tử được xác định chặt chẽ hơn.
Ngăn xếp hoặc hàng đợi là cấu trúc dữ liệu lôgic; nó sẽ được triển khai dưới bìa với cấu trúc vật lý (ví dụ: danh sách, mảng, cây, v.v.)
Bạn có thể tận dụng sự trừu tượng đã được triển khai.
Ngoài việc thực thi sử dụng mà những người khác đã đề cập, đó cũng là vấn đề về hiệu suất. Khi bạn muốn loại bỏ một cái gì đó từ đầu của một mảng hoặc một danh sách (ArrayList) nó thường mất O (n) thời gian, nhưng đối với một hàng đợi phải mất O (1) thời gian. Điều đó có thể tạo nên sự khác biệt lớn nếu có nhiều yếu tố.
Câu hỏi không rõ ràng, vì bạn có thể thể hiện kiểu dữ liệu trừu tượng của một chồng hoặc hàng đợi bằng cách sử dụng một mảng hoặc cấu trúc dữ liệu được liên kết.
Sự khác biệt giữa việc triển khai danh sách liên kết của một chồng hoặc hàng đợi và triển khai mảng có cùng sự cân bằng cơ bản như bất kỳ mảng so với cấu trúc dữ liệu động nào.
Ngăn xếp được liên kết/ngăn xếp được liên kết có chèn/xóa tốc độ linh hoạt, tốc độ cao với việc triển khai hợp lý, nhưng yêu cầu nhiều bộ nhớ hơn một mảng. Chèn/xóa không tốn kém ở đầu của mảng cho đến khi bạn hết dung lượng; một mảng thực hiện của một hàng đợi hoặc ngăn xếp sẽ đòi hỏi nhiều công việc để thay đổi kích cỡ, vì bạn cần phải sao chép bản gốc vào một cấu trúc lớn hơn (hoặc thất bại với một lỗi tràn).
Mảng/danh sách và ngăn xếp/hàng đợi không phải là khái niệm loại trừ lẫn nhau. Infact bất kỳ ngăn xếp hoặc triển khai hàng đợi bạn tìm thấy gần như chắc chắn bằng cách sử dụng hoặc mảng hoặc danh sách dưới mui xe.
Cấu trúc mảng và danh sách cung cấp mô tả về cách dữ liệu được lưu trữ, lâu với sự đảm bảo về độ phức tạp của các hoạt động cơ bản trên cấu trúc.
Ngăn xếp và hàng đợi cung cấp mô tả cấp cao về cách chèn hoặc xóa các phần tử. FIFO cho hàng đợi, FILO cho ngăn xếp.
Ví dụ: nếu bạn đang thực hiện một hàng đợi tin nhắn, bạn sẽ sử dụng một hàng đợi. Nhưng hàng đợi chính nó có thể lưu trữ mỗi tin nhắn trong một danh sách. "Đẩy" một tin nhắn thêm vào mặt trước của danh sách, "popping" một tin nhắn lấy từ cuối danh sách.
Ngăn xếp và Hàng đợi là các cách nâng cao hơn để xử lý một bộ sưu tập mà chính mảng đó không thiết lập bất kỳ thứ tự nào theo cách các phần tử hoạt động bên trong bộ sưu tập.
Ngăn xếp (LIFO - Cuối cùng trong lần đầu tiên) và một hàng đợi (FIFO - Đầu tiên trong lần đầu tiên) thiết lập và thứ tự các thành phần của bạn được chèn vào và xóa khỏi bộ sưu tập.
Bạn có thể sử dụng một mảng hoặc danh sách liên kết làm cấu trúc lưu trữ để triển khai ngăn xếp hoặc mẫu hàng đợi. Hoặc thậm chí tạo ra với những cấu trúc cơ bản các mẫu phức tạp hơn như Cây nhị phân hoặc hàng đợi ưu tiên, mà cũng có thể mang lại không chỉ một thứ tự trong việc chèn và loại bỏ các phần tử mà còn sắp xếp chúng bên trong bộ sưu tập.
Bạn đã đến một quán ăn tự phục vụ, phải không? và thấy một chồng đĩa? Khi một tấm sạch được thêm vào ngăn xếp, nó được đặt lên trên. Khi một tấm được lấy ra, nó được lấy ra khỏi đỉnh. Vì vậy, nó được gọi là Last-In-First-Out (LIFO). Một ngăn xếp máy tính là như vậy, ngoại trừ nó giữ số, và bạn có thể làm cho một trong một mảng hoặc một danh sách, nếu bạn thích. (Nếu ngăn xếp các tấm có một lò xo bên dưới, họ nói bạn "đẩy" một cái lên trên, và khi bạn loại bỏ một cái bạn "bật" nó ra. Đó là nơi những lời đó đến từ.)
Trong quán ăn tự phục vụ, quay trở lại, nơi họ rửa bát đĩa. Họ có một băng tải, nơi họ đặt các tấm được rửa sạch ở một đầu, và họ đi ra đầu kia, theo cùng thứ tự. Đó là một hàng đợi hoặc First-In-First-Out (FIFO). Bạn cũng có thể tạo một trong số đó ra khỏi một mảng hoặc danh sách nếu bạn muốn.
Chúng phù hợp với điều gì? Vâng, giả sử bạn có một cấu trúc dữ liệu cây (giống như một cây thực sự làm bằng gỗ ngoại trừ nó lộn ngược), và bạn muốn viết một chương trình để đi bộ hoàn toàn qua nó, để in ra tất cả các lá.
Một cách là thực hiện chiều sâu đầu tiên đi bộ. Bạn bắt đầu ở thân cây và đi đến nhánh đầu tiên, và sau đó đi đến chi nhánh đầu tiên của nhánh đó, và cứ thế, cho đến khi bạn tới lá, và in nó. Nhưng làm thế nào để bạn sao lưu để đến chi nhánh tiếp theo? Vâng, mỗi khi bạn đi xuống một chi nhánh, bạn "đẩy" một số thông tin trong ngăn xếp của bạn, và khi bạn sao lưu bạn "bật" nó trở lại, và điều đó cho bạn biết nhánh nào cần thực hiện tiếp theo. Đó là cách bạn theo dõi nhánh nào cần làm tiếp theo tại mỗi điểm.
Một cách khác là chiều rộng đầu tiên đi bộ. Bắt đầu từ thân cây, bạn đánh số tất cả các nhánh ra khỏi thân cây và đặt các số đó vào hàng đợi. Sau đó, bạn lấy một số ra đầu kia, đi đến chi nhánh đó, và cho mỗi chi nhánh sắp tắt của nó, bạn lại đánh số chúng (liên tiếp với lần đầu tiên) và đặt chúng vào hàng đợi. Khi bạn tiếp tục làm điều này, bạn sẽ ghé thăm đầu tiên các chi nhánh mà là 1 chi nhánh ra khỏi thân cây. Sau đó, bạn sẽ đến thăm tất cả các chi nhánh đó là 2 chi nhánh ra khỏi thân cây, và như vậy. Cuối cùng bạn sẽ đến lá và bạn có thể in chúng.
Đây là hai khái niệm cơ bản trong lập trình.
Tôi cho rằng xếp chồng và hàng đợi là các khái niệm truy cập bộ nhớ được sử dụng theo nhu cầu ứng dụng. Mặt khác, mảng và danh sách là hai kỹ thuật truy cập bộ nhớ và chúng được sử dụng để thực hiện các khái niệm xếp chồng (LIFO) và hàng đợi (FIFO).
ngăn xếp và hàng đợi được triển khai với các mảng và danh sách. – Yada
Bạn có thể muốn tham khảo văn bản trên Cấu trúc dữ liệu. Đây thường là yêu cầu cơ bản cho tất cả học sinh CS và DP. –