Queue

Queue

• Các phần tử cùng kiểu
• Số phần tử không cố định
• Các phần tử được đưa vào ở đuôi hàng đợi và lấy ra ở đầu hàng đợi
• Hàng đợi hoạt động theo cơ chế FIFO (First In First Out)
Ví dụ:
- Xếp hàng vô thang máy
- Máy in trong mạng
class Queue {
  struct Node {
    int data;
    Node * next;
  };
  Node * head, * tail;
  public:
    void CreateQ() {
      head = tail = NULL;
    }
  bool EmptyQ() {
    if (head == NULL) return true;
    else return false;
  }
  void AddQ(int x) {
    Node * t = new Node;
    t -> data = x;
    t -> next = NULL;
    if (head == NULL) head = tail = t;
    else {
      tail -> next = t;
      tail = t;
    }
  }
  int RemoveQ() {
    int x = 0;
    if (head == NULL) cout << "\n Hang doi rong!!!";
    else {
      x = head -> data;
      Node * t = head;
      if (head -> next == NULL) head = tail = NULL;
      else head = head -> next;
      delete t;
    }
    return x;
  }

  void in () {
    Queue t;
    t.CreateQ();
    cout << "\n Noi dung hang doi: ";
    while (!EmptyQ()) {
      int x = RemoveQ();
      cout << x << " ";
      t.AddQ(x);
    }
    while (!t.EmptyQ()) AddQ(t.RemoveQ());
  }
  
public class MyPriorityQueue {
  void AddQ(int x) {
    Node t = new Node(x);
    if (head == null) head = t;
    else if (x >= head.data) {
      t.next = head;
      head = t;
    } else {
      Node y = head, p = head;
      while (p != null && p.data > x) {
        y = p;
        p = p.next;
      }
      y.next = t;
      t.next = p;
    }
  }
}

int n = kb.nextInt();
for (int i = 1; i <= n; i++) {
  String t = kb.next();
  if (t.charAt(0) == '-’) {
      int x = Q.RemoveQ();
      System.out.print("\n Lay phan tu max: " + x);
    } else {
      int p = Integer.parseInt(t);
      System.out.print("\n Them phan tu " + p + " vao hang doi");
      Q.AddQ(p);
    }
  }
  System.out.print("\n CAC SO CON LAI TRONG HANG DOI LA:\n");
  while (!Q.EmptyQ()) System.out.print(" " + Q.RemoveQ());