Cấu trúc dữ liệu Deque

Trong hướng dẫn này, bạn sẽ tìm hiểu hàng đợi kết thúc kép (deque) là gì. Ngoài ra, bạn sẽ tìm thấy các ví dụ làm việc của các hoạt động khác nhau trên deque trong C, C ++, Java và Python.

Deque hoặc Double Ended Queue là một loại hàng đợi trong đó việc chèn và loại bỏ các phần tử có thể được thực hiện từ phía trước hoặc phía sau. Do đó, nó không tuân theo quy tắc FIFO (First In First Out).

Đại diện của Deque

Các loại Deque

  • Đầu vào Hạn chế Deque
    Trong deque này, đầu vào bị hạn chế ở một đầu nhưng cho phép xóa ở cả hai đầu.
  • Đầu ra bị hạn chế Deque
    Trong deque này, đầu ra bị hạn chế ở một đầu nhưng cho phép chèn ở cả hai đầu.

Hoạt động trên Deque

Dưới đây là triển khai mảng tròn của deque. Trong mảng tròn, nếu mảng đầy thì ta bắt đầu lại từ đầu.

Nhưng trong triển khai mảng tuyến tính, nếu mảng đã đầy thì không thể chèn thêm phần tử nào nữa. Trong mỗi thao tác dưới đây, nếu mảng đầy, "thông báo tràn" sẽ được đưa ra.

Trước khi thực hiện các thao tác sau, hãy làm theo các bước sau.

  1. Lấy một mảng (deque) có kích thước n.
  2. Đặt hai con trỏ ở vị trí đầu tiên và đặt front = -1và rear = 0.
Khởi tạo một mảng và con trỏ cho deque

1. Chèn ở phía trước

Thao tác này thêm một phần tử ở phía trước.

  1. Kiểm tra vị trí của phía trước. Kiểm tra vị trí phía trước
  2. Nếu front < 1, khởi động lại front = n-1(chỉ mục cuối cùng). Chuyển từ trước đến cuối
  3. Khác, giảm phía trước đi 1.
  4. Thêm khóa mới 5 vào array(front). Chèn phần tử ở phía trước

2. Chèn ở phía sau

Thao tác này thêm một phần tử vào phía sau.

  1. Kiểm tra xem mảng đã đầy chưa. Kiểm tra xem deque đã đầy chưa
  2. Nếu deque đã đầy, hãy khởi động lại rear = 0.
  3. Khác, tăng phía sau thêm 1. Tăng phía sau
  4. Thêm khóa mới 5 vào array(rear). Chèn phần tử ở phía sau

3. Xóa khỏi Mặt trận

Thao tác xóa một phần tử từ phía trước.

  1. Kiểm tra xem deque có trống không. Kiểm tra xem deque có trống không
  2. Nếu deque trống (tức là front = -1), không thể thực hiện xóa ( điều kiện dòng dưới ).
  3. Nếu deque chỉ có một phần tử (tức là front = rear), hãy đặt front = -1và rear = -1.
  4. Khác nếu phía trước ở cuối (tức là front = n - 1), hãy đặt ở phía trước front = 0.
  5. Khác front = front + 1,. Tăng mặt trước

4. Xóa khỏi phía sau

Thao tác này sẽ xóa một phần tử từ phía sau.

  1. Kiểm tra xem deque có trống không. Kiểm tra xem deque có trống không
  2. Nếu deque trống (tức là front = -1), không thể thực hiện xóa ( điều kiện dòng dưới ).
  3. Nếu deque chỉ có một phần tử (tức là front = rear), hãy đặt front = -1và rear = -1, nếu không hãy làm theo các bước bên dưới.
  4. Nếu phía sau ở phía trước (tức là rear = 0), hãy đặt ở phía trước rear = n - 1.
  5. Khác rear = rear - 1,. Giảm phía sau

5. Kiểm tra trống

Thao tác này kiểm tra xem deque có trống không. Nếu front = -1, deque trống.

6. Kiểm tra đầy đủ

Thao tác này kiểm tra xem deque đã đầy chưa. Nếu front = 0và rear = n - 1HOẶC front = rear + 1, deque đầy.

Triển khai Deque bằng Python, Java, C và C ++

Python Java C C ++ 
 # Deque implementaion in python class Deque: def __init__(self): self.items = () def isEmpty(self): return self.items == () def addRear(self, item): self.items.append(item) def addFront(self, item): self.items.insert(0, item) def removeFront(self): return self.items.pop() def removeRear(self): return self.items.pop(0) def size(self): return len(self.items) d = Deque() print(d.isEmpty()) d.addRear(8) d.addRear(5) d.addFront(7) d.addFront(10) print(d.size()) print(d.isEmpty()) d.addRear(11) print(d.removeRear()) print(d.removeFront()) d.addFront(55) d.addRear(45) print(d.items)
 // Deque implementation in Java class Deque ( static final int MAX = 100; int arr(); int front; int rear; int size; public Deque(int size) ( arr = new int(MAX); front = -1; rear = 0; this.size = size; ) boolean isFull() ( return ((front == 0 && rear == size - 1) || front == rear + 1); ) boolean isEmpty() ( return (front == -1); ) void insertfront(int key) ( if (isFull()) ( System.out.println("Overflow"); return; ) if (front == -1) ( front = 0; rear = 0; ) else if (front == 0) front = size - 1; else front = front - 1; arr(front) = key; ) void insertrear(int key) ( if (isFull()) ( System.out.println(" Overflow "); return; ) if (front == -1) ( front = 0; rear = 0; ) else if (rear == size - 1) rear = 0; else rear = rear + 1; arr(rear) = key; ) void deletefront() ( if (isEmpty()) ( System.out.println("Queue Underflow"); return; ) // Deque has only one element if (front == rear) ( front = -1; rear = -1; ) else if (front == size - 1) front = 0; else front = front + 1; ) void deleterear() ( if (isEmpty()) ( System.out.println(" Underflow"); return; ) if (front == rear) ( front = -1; rear = -1; ) else if (rear == 0) rear = size - 1; else rear = rear - 1; ) int getFront() ( if (isEmpty()) ( System.out.println(" Underflow"); return -1; ) return arr(front); ) int getRear() ( if (isEmpty() || rear < 0) ( System.out.println(" Underflow"); return -1; ) return arr(rear); ) public static void main(String() args) ( Deque dq = new Deque(4); System.out.println("Insert element at rear end : 12 "); dq.insertrear(12); System.out.println("insert element at rear end : 14 "); dq.insertrear(14); System.out.println("get rear element : " + dq.getRear()); dq.deleterear(); System.out.println("After delete rear element new rear become : " + dq.getRear()); System.out.println("inserting element at front end"); dq.insertfront(13); System.out.println("get front element: " + dq.getFront()); dq.deletefront(); System.out.println("After delete front element new front become : " + +dq.getFront()); ) )
 // Deque implementation in C #include #define MAX 10 void addFront(int *, int, int *, int *); void addRear(int *, int, int *, int *); int delFront(int *, int *, int *); int delRear(int *, int *, int *); void display(int *); int count(int *); int main() ( int arr(MAX); int front, rear, i, n; front = rear = -1; for (i = 0; i < MAX; i++) arr(i) = 0; addRear(arr, 5, &front, &rear); addFront(arr, 12, &front, &rear); addRear(arr, 11, &front, &rear); addFront(arr, 5, &front, &rear); addRear(arr, 6, &front, &rear); addFront(arr, 8, &front, &rear); printf("Elements in a deque: "); display(arr); i = delFront(arr, &front, &rear); printf("removed item: %d", i); printf("Elements in a deque after deletion: "); display(arr); addRear(arr, 16, &front, &rear); addRear(arr, 7, &front, &rear); printf("Elements in a deque after addition: "); display(arr); i = delRear(arr, &front, &rear); printf("removed item: %d", i); printf("Elements in a deque after deletion: "); display(arr); n = count(arr); printf("Total number of elements in deque: %d", n); ) void addFront(int *arr, int item, int *pfront, int *prear) ( int i, k, c; if (*pfront == 0 && *prear == MAX - 1) ( printf("Deque is full."); return; ) if (*pfront == -1) ( *pfront = *prear = 0; arr(*pfront) = item; return; ) if (*prear != MAX - 1) ( c = count(arr); k = *prear + 1; for (i = 1; i <= c; i++) ( arr(k) = arr(k - 1); k--; ) arr(k) = item; *pfront = k; (*prear)++; ) else ( (*pfront)--; arr(*pfront) = item; ) ) void addRear(int *arr, int item, int *pfront, int *prear) ( int i, k; if (*pfront == 0 && *prear == MAX - 1) ( printf("Deque is full."); return; ) if (*pfront == -1) ( *prear = *pfront = 0; arr(*prear) = item; return; ) if (*prear == MAX - 1) ( k = *pfront - 1; for (i = *pfront - 1; i < *prear; i++) ( k = i; if (k == MAX - 1) arr(k) = 0; else arr(k) = arr(i + 1); ) (*prear)--; (*pfront)--; ) (*prear)++; arr(*prear) = item; ) int delFront(int *arr, int *pfront, int *prear) ( int item; if (*pfront == -1) ( printf("Deque is empty."); return 0; ) item = arr(*pfront); arr(*pfront) = 0; if (*pfront == *prear) *pfront = *prear = -1; else (*pfront)++; return item; ) int delRear(int *arr, int *pfront, int *prear) ( int item; if (*pfront == -1) ( printf("Deque is empty."); return 0; ) item = arr(*prear); arr(*prear) = 0; (*prear)--; if (*prear == -1) *pfront = -1; return item; ) void display(int *arr) ( int i; printf(" front: "); for (i = 0; i < MAX; i++) printf(" %d", arr(i)); printf(" :rear"); ) int count(int *arr) ( int c = 0, i; for (i = 0; i < MAX; i++) ( if (arr(i) != 0) c++; ) return c; )
 // Deque implementation in C++ #include using namespace std; #define MAX 10 class Deque ( int arr(MAX); int front; int rear; int size; public: Deque(int size) ( front = -1; rear = 0; this->size = size; ) void insertfront(int key); void insertrear(int key); void deletefront(); void deleterear(); bool isFull(); bool isEmpty(); int getFront(); int getRear(); ); bool Deque::isFull() ( return ((front == 0 && rear == size - 1) || front == rear + 1); ) bool Deque::isEmpty() ( return (front == -1); ) void Deque::insertfront(int key) ( if (isFull()) ( cout << "Overflow" << endl; return; ) if (front == -1) ( front = 0; rear = 0; ) else if (front == 0) front = size - 1; else front = front - 1; arr(front) = key; ) void Deque ::insertrear(int key) ( if (isFull()) ( cout << " Overflow " << endl; return; ) if (front == -1) ( front = 0; rear = 0; ) else if (rear == size - 1) rear = 0; else rear = rear + 1; arr(rear) = key; ) void Deque ::deletefront() ( if (isEmpty()) ( cout << "Queue Underflow" << endl; return; ) if (front == rear) ( front = -1; rear = -1; ) else if (front == size - 1) front = 0; else front = front + 1; ) void Deque::deleterear() ( if (isEmpty()) ( cout << " Underflow" << endl; return; ) if (front == rear) ( front = -1; rear = -1; ) else if (rear == 0) rear = size - 1; else rear = rear - 1; ) int Deque::getFront() ( if (isEmpty()) ( cout << " Underflow" << endl; return -1; ) return arr(front); ) int Deque::getRear() ( if (isEmpty() || rear < 0) ( cout << " Underflow" << endl; return -1; ) return arr(rear); ) int main() ( Deque dq(4); cout << "insert element at rear end "; dq.insertrear(5); dq.insertrear(11); cout << "rear element: " << dq.getRear() << endl; dq.deleterear(); cout << "after deletion of the rear element, the new rear element: " << dq.getRear() << endl; cout << "insert element at front end "; dq.insertfront(8); cout << "front element: " << dq.getFront() << endl; dq.deletefront(); cout << "after deletion of front element new front element: " << dq.getFront() << endl; )

Thời gian phức tạp

Độ phức tạp về thời gian của tất cả các hoạt động trên là không đổi, tức là O(1).

Các ứng dụng của cấu trúc dữ liệu Deque

  1. Trong các thao tác hoàn tác trên phần mềm.
  2. Để lưu trữ lịch sử trong trình duyệt.
  3. Để triển khai cả ngăn xếp và hàng đợi.

thú vị bài viết...