Queue-н тухай өмнө нь бичсэн билээ. Энэ удаа үүнийг хэрхэн анхнаас нь бичих вэ? гэдэг талаар бичье. Үүний тулд заагч болон санах ойн тухай энгийн ойлголттой байхад хангалттай. Queue-д гол 4 үйлдэл байдаг ба

  • size() - хэмжээг нь буцаадаг
  • top() - эхний элемэнтийг буцаах
  • pop() - эхний элемэнтийг устгах
  • push(element) - хамгийн ард элемэнт нэмэх

Мэдээж тийм ч хэцүү биш байлгүүдээ? Зүгээр array ашиглаад хийж болох уу? Болох бол яаж вэ?

Үүсэх асуудлууд

Array ашиглаад хийцгээе. Эхлээд хоосон array байх ба элемент нэмэх үед шинэ нэг элементээр илүү array үүсгээд өмнөхийг хуулахад болно. Харин эхний элементийг мэдэхэд зүгээр л array-н эхний элементийг буцаахад болно. Гэхдээ шинээр элемент нэмэх үед шинэ массив үүсгээд өмнөхийг хуулахад O(N) үйлдэл хийх ба энэ нь хэтэрхий удаан ба Queue дээр энэ бүх үйлдэл O(1) байдаг. Тэгэхээр array ашиглах нь тийм ч сайн санаа биш бололтой. Pop үйлдэл дээр мөн array-г хуулах ба энэ нь мөн O(N) байна. Арай өөрөөр гэвэл бид хуулахгүйгээр index-ээ ахиулаад байх боломжтой гэхдээ бид хэдэн элементтэй болохоо мэдэхгүй ба мөн илүү санах ой зарах тул ашиггүй бүтэц юм.

Гол санаа

Бид шаардлагаа харвал аль ч элемент рүү хандах шаардлагагүй гэдэг нь чухал ба зөвхөн эхний элементийг шууд мэдэх нь чухал. Тэгэхээр гинжин хэлбэртэй бүтэцшиг санаа ашиглаж болно. Гинжин хэлбэртэй тул эхний болон сүүлийн хэсгийг хянаад явахад болно. Жишээ нь элемент нэмнэ гэвэл хамгийн сүүлийн гинжийг шинэ гинжтэй холбоход л болно. Хамгийн урд талыг устгана гэвэл гинжний урт талыг таслаад устгахад болно. Үүнийг бид санах ойгоо өөрсдөө удирдан хялбар шийдэж болно.

Эхлээд элементийн бүтцийг тодорхойлъё.

struct Node {
	int value; // элемэнтийн утга
	Node *next; // дараагийн элемэнтийг заасан заагч, хоосон байж болно
};

Push буюу нэмэх үйлдэл

void push(int v) {
	Node *newNode = new Node(v); // шинээр элемэнт үүсгэнэ
	if(last == nullptr) { // хэрвээ last буюу сүүлийн элемэнт байхгүй бол queue хоосон 
		front = last = newNode; // хоосон учир ганц байгаа элемэнт нь болно
	} else {
		last->next = newNode; // одоогийн хамгийн сүүлийн элемэнт шинэ элемэнтийг заана
		last = newNode; // хамгйин сүүлийн элемэнтийг шинэчлэнэ
	}
	s++; // элемэнтийн тоог нэгээр нэмнэ
}

pop буюу хасах үйлдэл

void pop() {
	if(front == nullptr) { // хоосон тул юу ч хийхгүй
		return;
	}
	Node *newFront = front->next; // 2-дахь элемэнтийг авна
	delete front; // хамгийн эхний элемэнтийг санах ойгоос устгана

	front = newFront; // хамгийн эхний элемэнтийг солнино
	s--; // элемэнтийн тоог нэгээр хасна
}

Full implementation

Энд бүтэн код нь байгаа ба бид array, vector-шиг хүссэн элемент рүүгээ ханддагаар хийж болно. Гэхдээ мэдээж гинжээр гүйх тул O(1) биш O(N) байх нь тодорхой

#include <iostream>
using namespace std;

struct Node {
    int value;
    Node *next;
    Node(int v) { value = v; next = nullptr; }
};

class Queue {
    private:
        Node *front;
        Node *last;
        int s;
    public:
        Queue() {
            front = last = nullptr;
            s = 0;
        }
        int size() { return s; }
        int top() {
            if(front == nullptr) return 0;
            return front->value;
        }
        bool isEmpty() {
            if(s == 0) return true;
            return false;
        }
        void push(int v) {
            Node *newNode = new Node(v);
            if(last == nullptr) {
                front = last = newNode;
            } else {
                last->next = newNode;
                last = newNode;
            }
            s++;
        }
        void pop() {
            if(front == nullptr) {
                return;
            }
            Node *newFront = front->next;
            delete front;

            front = newFront;
            s--;
        }
        int operator[](int index) {
            if(s <= index) return 0;
            Node *current = front;
            while(index > 0) {
                current = current->next;
                index--;
            }
            return current->value;
        }
};

int main() {
    Queue q;

    q.pop();

    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    cout << q[3] << endl;

    cout << q.top() << endl;

    q.pop();

    cout << q.top() << endl;
}

Дүгнэлт

Үүнийг бичихэд энгийн боловч бид олон зүйлийг харж болно. Жишээ нь яагаад өөрсдөө санах ойг удирдаж байгаа вэ? Учир нь хэмжээгээ мэдэхгүй ба dynamic байх боломжтой. Өөрөөр хэлбэл array-шиг томоор санах ойг дараалан авах шаардлагагүй. Мөн тухайн асуудлын шаардлагаас хамаараад бид илүү энгийн тохиромжтой бүтэц бичиж байгааг анзаарч болно. Тиймээс ямар ч элемент рүү хандах шаардлагагүй болсноор энэхүү зүйлс ашигтай болж байна. Олон төрлийн өгөгдлийн бүтэц байдаг ба асуудал бүрээс шалтгаалаад давуу болон сул тал үүсдэг.