Triển khai hàng đợi bằng cách sử dụng mảng trong Python
|
Hàng đợi tròn là hàng đợi trong đó tất cả các phần tử được nối với nhau để tạo thành một hình tròn. Hàng đợi tròn có thể được thực hiện với mảng và danh sách được liên kết. Trong triển khai mảng, phía trước và phía sau bao quanh (hoạt động modulo) đến đầu mảng. Trong thực hiện danh sách được liên kết, nút cuối cùng liên kết trở lại nút phía trước. Trong bài đăng này, triển khai hàng đợi vòng tròn đang sử dụng mảng Show
Mục lụcBản đồ triển khai hàng đợiPhần 1 – Triển khai hàng đợi với danh sách liên kết Phần 2 – Triển khai hàng đợi vòng với mảng Enqueue trong việc thực hiện hàng đợi vòng trònĐầu tiên chúng ta khai báo một mảng. Trong Java, nếu bạn sử dụng mảng (không phải ArrayList), bạn phải chỉ định maxSize. Nếu mảng đạt đến kích thước tối đa, bạn không thể thêm phần tử nữa. front Index và rear Index là chỉ số của phần tử phía trước và phần tử phía sau. Khi hàng đợi trống, chúng là -1. Độ dài là để theo dõi số lượng phần tử trong hàng đợi Để enqueue là thêm phần tử ở phía sau. rearIndex được tăng thêm 1. Nếu rearIndex vượt quá maxSize, chúng tôi sử dụng thao tác modulo (hoặc “mod”, “%”) để có được rearIndex mới với phạm vi maxSize Java1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 lớp công khai CircularQueueArray<T> { riêng tư T[] queueArray; private int maxSize; // Kích thước của Thông tư riêng tư int frontIndex, rearIndex; riêng tư int độ dài = 0;
// hàm tạo, Thời gian O(1), Không gian O(1) @SuppressWarnings("unchecked") công khai CircularQueueArray(int kích thước) { Kích thước tối đa = kích thước; frontIndex = - 1; rearIndex = - 1; queueArray = (T[])new Object[maxSize]; } //Thêm vào phía sau, Thời gian O(1), Khoảng cách O(1) công khai vô hiệu hàng đợi(T value) { nếu (là Đầy đủ()) { Hệ thống. ra. println("Hàng đợi đã đầy, không thể đưa vào hàng đợi " + value); return; } if (frontIndex == -1) //empty frontIndex = 0; rearIndex = (rearIndex + 1) % maxSize; queueArray[rearIndex] = value; độ dài ++ ; } Javascript1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 lớp CircularQueueArray {
// hàm tạo, Thời gian O(1), Không gian O(1) hàm tạo(kích thước) { này. Kích thước tối đa = kích thước; cái này. frontIndex = - 1; cái này. rearIndex = - 1; cái này. queueArray = []; cái này. độ dài = 0; < }
//Thêm vào phía sau, Thời gian O(1), Khoảng cách O(1) enqueue(giá trị) { nếu (điều này. isFull()) { bảng điều khiển. log("Hàng đợi đã đầy, không thể đưa vào hàng đợi " + value); return; } nếu (điều này. frontIndex == - 1) này. frontIndex = 0; cái này. rearIndex = (this. rearIndex + 1) % . this.Kích thước tối đa; cái này. queueArray[này. rearIndex] = giá trị; cái này. độ dài ++ ; } con trăn1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 lớp CircularQueueArray. #hàm tạo, Thời gian O(1), Không gian O(1) def __init__(self, size): bản thân. Kích thước tối đa = kích thước bản thân. queueArray = [Không có] * size bản thân. frontIndex = self. rearIndex = - 1 bản thân. độ dài = 0
#Thêm ở phía sau, Thời gian O(1), Khoảng cách O(1) def enqueue(self, value): nếu chính mình. isFull(). #full in("Hàng đợi tròn đã đầy, không thể xếp hàng" + str(value)) return nếu (bản thân. frontIndex == - 1 . : #empty bản thân. frontIndex = 0 bản thân. rearIndex = (self. rearIndex + 1) % . self.Kích thước tối đa bản thân. queueArray[self. rearIndex] = giá trị bản thân. độ dài += 1 nguệch ngoạcDequeue trong việc thực hiện hàng đợi vòng trònHoạt động dequeue là loại bỏ nút phía trước khỏi hàng đợi. Trước tiên, chúng tôi kiểm tra xem hàng đợi có trống không. Nếu nó trống, phương thức sẽ trả về. Chúng tôi cũng kiểm tra xem chỉ có một phần tử trong hàng đợi. Nếu đúng như vậy, chúng ta nên đặt lại front Index và rear Index thành -1 sau khi xóa phần tử cuối cùng Để dequeue, chúng ta tăng frontIndex lên 1. Giống như enqueue, nếu frontIndex vượt maxSize thì ta phải đưa phần tử về index 0. Chúng tôi sử dụng thao tác modulo (hoặc “mod”, “%”) để lấy frontIndex mới. Xin lưu ý đối với phần tử dequeue, chúng tôi chỉ cập nhật frontIndex. Giá trị ban đầu vẫn ở nguyên vị trí cho đến khi nó được thay thế bằng giá trị mới Java1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 //Xoá từ phía trước, Thời gian O(1), Khoảng cách O(1) công khai T dequeue() { if (isEmpty()) { Hệ thống. ra. println("Hàng trống"); return null; } T mục = queueArray[frontIndex]; if (frontIndex == rearIndex) { //last one, reset frontIndex = - 1; rearIndex = - 1; } khác { frontIndex = (frontIndex + 1) % maxSize; } độ dài -- ; return (item); } Javascript1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 //Xoá từ phía trước, Thời gian O(1), Khoảng cách O(1) dequeue() { nếu (điều này. isEmpty()) { bảng điều khiển. log("Hàng trống"); return null; } var item = this.queueArray[này. frontIndex]; nếu (điều này. frontIndex == this. rearIndex) { //còn một phần tử cái này. frontIndex = - 1; cái này. rearIndex = - 1; } khác { cái này. frontIndex = (this. frontIndex + 1) % . this.Kích thước tối đa; } cái này. độ dài -- ; return (item); } con trăn1 2 3 4 5 6 7 8 9 10 11 12 13 14 # Xóa từ phía trước, Thời gian O(1), Khoảng cách O(1) def dequeue(self): nếu chính mình. isEmpty(). in("Hàng đợi vòng tròn trống, không thể xếp hàng") return mục = bản thân. queueArray[self. frontIndex] nếu (bản thân. frontIndex == self. rearIndex). Còn #một mục bản thân. frontIndex = - 1 bản thân. rearIndex = - 1 trả lại mục khác. bản thân. frontIndex = (self. frontIndex + 1) % . self.Kích thước tối đa bản thân. độ dài -= 1 trả lại mặt hàng nguệch ngoạc
|
