12. Implement IQueue (queue + priority queue)

Implement IQueue (queue + priority queue)

Functional requirements

? Here we use pure virtual functions as interfaces to implement IQeue to achieve the following functions:

/********************************************** ***************************
        > File Name: 14.cpp
        > Author:Xiao Yuheng
        > Mail:[email protected]
        > Created Time: Wed Nov 8 15:53:09 2023
 *************************************************** **********************/
#include <iostream>
#include <functional>
#include <cstring>

using namespace std;

namespace xyh {

bool cmp(int a, int b) {
    return a < b;
}

bool cmp1(int a, int b) {
    return a > b;
}
    
class IQueue {
public:
    virtual void push(int x) = 0;
    virtual void pop() = 0;
    virtual int top() const = 0;
    virtual int front() const = 0;
    virtual bool empty() const = 0;
    virtual int size() const = 0;
    virtual ~IQueue() {}
};

class queue : public IQueue {
public:

};
    
class priority_queue : public IQueue {
public:

};

}

int main() {
    using namespace xyh;
    queue que;
    for (int i = 0; i < 100; i + + ) {
        que.push(i + 1);
    }
    while (!que.empty()) {
        cout << que.top() << endl;
        que.pop();
    }
    cout << "******************" << endl;
    priority_queue prque;
    for (int i = 0; i < 100; i + + ) {
        prque.push(i + 1);
    }
    while (!prque.empty()) {
        cout << prque.top() << endl;
        prque.pop();
    }
    cout << "**********************" << endl;
    priority_queue fprque(cmp1);
    for (int i = 0; i < 100; i + + ) {
        fprque.push(i + 1);
    }
    while (!fprque.empty()) {
        cout << fprque.top() << endl;
        fprque.pop();
    }
    return 0;
}

? Briefly explain what this code needs us to do:

Namespace and comparison functions

namespace xyh {
    bool cmp(int a, int b) {
        return a < b;
    }

    bool cmp1(int a, int b) {
        return a > b;
    }
}

• Two comparison functions cmp and cmp1 are defined in the xyh namespace, which are used for ascending and descending order respectively.

Abstract queue interface class

class IQueue {
public:
    virtual void push(int x) = 0;
    virtual void pop() = 0;
    virtual int top() const = 0;
    virtual int front() const = 0;
    virtual bool empty() const = 0;
    virtual int size() const = 0;
    virtual ~IQueue() {}
};

• IQueue is an abstract class that defines the basic interface of the queue, including push, pop, top, front, empty and size functions. This is a pure virtual class with no concrete implementation.

queue class

cppCopy codeclass queue : public IQueue {
public:
    // Specific implementation should be added here
};

• The queue class inherits from the IQueue interface, but no specific implementation is given in the code. The actual functionality of this class is not defined in the program.

priority_queue class

cppCopy codeclass priority_queue : public IQueue {
public:
    // Specific implementation should be added here
};

• The priority_queue class also inherits from the IQueue interface, but no specific implementation is given in the code. Again, the actual functionality of this class needs to be defined in the program.

Main function main

cppCopy codeint main() {
    using namespace xyh;
    queue que;
    // ... (operate on queue que)

    priority_queue prque;
    // ... (operate on the priority queue prque)

    priority_queue fprque(cmp1);
    // ... (operates on priority queue fprque with custom comparison function)

    return 0;
}

• One queue object and two priority_queue objects are created in the main function, and the operations are performed respectively. The specific operations are not given in the code, but the basic operations on the queue and priority queue are simulated through the push, top and pop functions. The custom comparison function cmp1 is used in the third priority_queue object.

Queue implementation

This is a C++ queue implementation that extends the IQueue interface.

int *copy_int(int *now_begin, int *old_begin, int *old_end) {<!-- -->
    memmove(now_begin, old_begin, sizeof(int) * (old_end - old_begin));
    return now_begin + (old_end - old_begin);
}

class queue : public IQueue {<!-- -->
public:
    // Constructor
    queue(int n = 0) : first(new int[n]), now(first), last(first + n) {<!-- -->}
    // Push new elements into the queue
    void push(int x) override {<!-- -->
        if (now == last) {<!-- -->
            Expansion();
        }
        *(now + + ) = x;
    }
    // Pop the previous element from the queue
    void pop() override {<!-- -->
        if (empty()) return;
        *(first + + );
    }
    // Get the value of the previous element
    int top() const override {<!-- --> return *first; }
    // Get the value of the previous element (same as `top`)
    int front() const override {<!-- --> return *first; }
    // Check if the queue is empty
    bool empty() const override {<!-- --> return first == now; }
    // Get the size of the queue
    int size() const override {<!-- --> return now - first; }

private:
    // Helper function to expand the queue when needed
    void Expansion() {<!-- -->
        if (now != last) return;
        int old_size = size();
        int new_size = old_size != 0 ? old_size * 2 : 1;
        int *new_first = new int[new_size];
        int *new_now = new_first;
        new_now = copy_int(new_first, first, last);
        delete[] first;
        first = new_first;
        now = new_now;
        last = new_first + new_size;
    }
    // Member variables
    int *first;
    int *now;
    int *last;
};

Explanation:

• Constructor: Initializes the queue with the given size or a default size of 0.
• push(int x): Adds new element x to the queue. If the queue is full, call the Expansion function to increase its size.
• pop(): Remove the previous element from the queue. If the queue is empty, no action is performed.
• top() and front(): Return the value of the previous element without removing it.
• empty(): Check whether the queue is empty.
• size(): Returns the size of the queue.

? Here we simply implement an interface of the queue. There is still a lot of room for optimization in our code. In the above code, if the element in the queue pop is popped off the stack, this space will no longer be used. To waste memory usage, let’s implement a circular queue for storage:

Circular Queue Implementation

class queue : public IQueue {<!-- -->
public:
    // Constructor
    queue(int n = 10) : data(new int[n]), head(0), tail(-1), count(0), total(n) {<!-- -->}
    // Push new elements into the queue
    void push(int x) override {<!-- -->
        if (full()) {<!-- -->
            Expansion();
        }
        count + = 1, tail = (tail + 1) % total;
        data[tail] = x;
    }
    // Pop the previous element from the queue
    void pop() override {<!-- -->
        if (empty()) return;
        count -= 1, head = (head + 1) % total;
    }
    // Get the value of the previous element
    int top() const override {<!-- --> return data[head]; }
    // Get the value of the previous element (same as `top`)
    int front() const override {<!-- --> return data[head]; }
    // Check if the queue is empty
    bool empty() const override {<!-- --> return count == 0; }
    // Get the size of the queue
    int size() const override {<!-- --> return count; }
    // Check if the queue is full
    int full() const {<!-- --> return count == total; }

private:
    // Helper function to expand the queue when needed
    void Expansion() {<!-- -->
        if (!full()) return;
        int old_size = size();
        int new_size = old_size != 0 ? old_size * 2 : 1;
        int *new_data = new int[new_size];
        int *now_data = new_data;
        int cnt = count;
        now_data = copy_int(now_data, data + head, data + total);
        now_data = copy_int(now_data, data, data + tail);
        delete[] data;
        data = new_data;
        head = 0, tail = count - 1;
        total = new_size;
        cout << total << endl;
    }
    // Member variables
    int *data;
    int head, tail, count, total;
};

Explanation:

• Constructor: Initialize the queue using the given size or the default size of 10.
• push(int x): Adds new element x to the queue. If the queue is full, call the Expansion function to increase its size.
• pop(): Remove the previous element from the queue. If the queue is empty, no action is performed.
• top() and front(): Return the value of the previous element without removing it.
• empty(): Check whether the queue is empty.
• size(): Returns the size of the queue.
• full(): Check if the queue is full.
• Expansion(): Helper function to expand the queue when needed. After expansion, the original data will be copied to the new storage space.

Our extended queue function here is too long, let’s optimize it:

class queue : public IQueue {
public:
    queue(int n = 10) : data(new int[n]), head(0), tail(-1), count(0), total(n) {}
    void push(int x) override {
        if (full()) {
            Expansion();
        }
        count + = 1, tail = (tail + 1) % total;
        data[tail] = x;
    }
    void pop() override {
        if (empty()) return ;
        count -= 1, head = (head + 1) % total;
    }
    int top() const override { return data[head]; }
    int front() const override { return data[head]; }
    bool empty() const override { return count == 0; }
    int size() const override { return count; }
    int full() const { return count == total; }
    ~queue() { delete[] data; }
    void swap(queue & amp;q) {
        std::swap(this->data, q.data);
        std::swap(this->head, q.head);
        std::swap(this->tail, q.tail);
        std::swap(this->count, q.count);
        std::swap(this->total, q.total);
    }
private:
    void Expansion() {
        int old_size = size();
        int len = old_size != 0 ? old_size * 2 : 1;
        queue q(len);
        while (!empty()) {
            q.push(top());
            pop();
        }
        swap(q);
    }
    int *data;
    int head, tail, count, total;
};

? We can directly open an object twice the size of the original object, then insert the elements of the original object into the new object, and finally exchange all member attributes of the two objects. Finally, the q object will call analysis Constructor automatically releases memory. At this point, our queue implementation is complete.

Priority queue

class priority_queue : public IQueue {
public:
    priority_queue(function<bool(int, int)> cmp = less<int>(), int n = 10)
                : first(new int[n]), now(first),
                last(first + n), cmp(cmp) {}
    void push(int x) override {
        if (now == last) {
            Expansion();
        }
        *(now + + ) = x;
        int temp = now - first;
        while (temp >> 1 & amp; & amp; cmp(first[temp / 2 - 1], first[temp - 1])) {
            swap(first[temp - 1], first[temp / 2 - 1]);
            temp >>= 1;
        }
    }
    void pop() override {
        if (empty()) return ;
        *first = *(--now);
        int temp = 1, cnt = now - first;
        while (temp << 1 <= cnt) {
            int ind = temp, l = temp * 2, r = temp * 2 + 1;
            if (cmp(first[temp - 1], first[l - 1])) temp = l;
            if (r <= cnt & amp; & amp; cmp(first[temp - 1], first[r - 1])) temp = r;
            if (temp == ind) break;
            swap(first[ind - 1], first[temp - 1]);
        }
    }
    int top() const override { return *first; }
    int front() const override { return *first; }
    bool empty() const override { return first == now; }
    int size() const override { return now - first; }

private:
    void Expansion() {
        if (now != last) return ;
        int old_size = size();
        int new_size = old_size != 0 ? old_size * 2 : 1;
        int *new_first = new int[new_size];
        int *new_now = new_first;
        new_now = copy_int(new_first, first, last);
        delete[] first;
        first = new_first;
        now = new_now;
        last = new_first + new_size;
    }
    int *first;
    int *now;
    int *last;
    function<bool(int, int)> cmp;
};

Constructor

cppCopy codepriority_queue(function<bool(int, int)> cmp = less<int>(), int n = 10)
    : first(new int[n]), now(first),
      last(first + n), cmp(cmp) {}

• The constructor accepts two parameters, one is the comparison function cmp, the default is less(), and the other is the initial size of the queue n, default is 10.
• The member variables of the class are initialized using an initialization list.
• first points to the beginning of the queue, now points to the position of the current element, last points to the end of the queue, cmp is a function used to compare the sizes of elements.

push function

cppCopy codevoid push(int x) override {
    if (now == last) {
        Expansion();
    }
    *(now + + ) = x;
    int temp = now - first;
    while (temp >> 1 & amp; & amp; cmp(first[temp / 2 - 1], first[temp - 1])) {
        swap(first[temp - 1], first[temp / 2 - 1]);
        temp >>= 1;
    }
}

• The push function is used to push elements into the priority queue.
• If the queue is full, call the Expansion function to expand the queue.
• Put the element x at the end of the queue, and then adjust it to the appropriate position by looping, ensuring that the value of the parent node is greater than or equal to the value of the child node.

pop function

cppCopy codevoid pop() override {
    if (empty()) return ;
    *first = *(--now);
    int temp = 1, cnt = now - first;
    while (temp << 1 <= cnt) {
        int ind = temp, l = temp * 2, r = temp * 2 + 1;
        if (cmp(first[temp - 1], first[l - 1])) temp = l;
        if (r <= cnt & amp; & amp; cmp(first[temp - 1], first[r - 1])) temp = r;
        if (temp == ind) break;
        swap(first[ind - 1], first[temp - 1]);
    }
}

• The pop function is used to remove the largest element from the priority queue.
• If the queue is empty, the function returns directly.
• Replace the first element of the queue with the element at the end of the queue and adjust it to the appropriate position through a loop, ensuring that the value of the parent node is greater than or equal to the value of the child node.

top and front functions

cppCopy codeint top() const override { return *first; }
int front() const override { return *first; }

• The top and front functions return the value of the first element of the queue.

empty and size functions

cppCopy codebool empty() const override { return first == now; }
int size() const override { return now - first; }

• The empty function checks whether the queue is empty.
• The size function returns the number of elements in the queue.

Expansion function

cppCopy codeprivate:
    void Expansion() {
        if (now != last) return ;
        int old_size = size();
        int new_size = old_size != 0 ? old_size * 2 : 1;
        int *new_first = new int[new_size];
        int *new_now = new_first;
        new_now = copy_int(new_first, first, last);
        delete[] first;
        first = new_first;
        now = new_now;
        last = new_first + new_size;
    }

• The Expansion function is used to extend the size of a queue when it is full.
• If the queue is not full, the function returns directly.
• Calculate the size of the new queue, create a new array, and copy the elements of the original array to the new array.
• Finally, the pointer and size of the queue are updated.

Full code:

/********************************************** ***************************
        > File Name: 14.cpp
        > Author:Xiao Yuheng
        > Mail:[email protected]
        > Created Time: Wed Nov 8 15:53:09 2023
 *************************************************** **********************/

#include 
#include 
#include 

using namespace std;

namespace xyh {

bool cmp(int a, int b) {
    return a < b;
}

bool cmp1(int a, int b) {
    return a > b;
}

int *copy_int(int *now_begin, int *old_begin, int *old_end) {
    memmove(now_begin, old_begin, sizeof(int) * (old_end - old_begin));
    return now_begin + (old_end - old_begin);
    }

class IQueue {
public:
    virtual void push(int x) = 0;
    virtual void pop() = 0;
    virtual int top() const = 0;
    virtual int front() const = 0;
    virtual bool empty() const = 0;
    virtual int size() const = 0;
    virtual ~IQueue() {}
};

/*
class queue : public IQueue {
public:
    queue(int n = 0) : first(new int[n]), now(first), last(first + n) {}
    void push(int x) override {
        if (now == last) {
            Expansion();
        }
        *(now + + ) = x;
    }
    void pop() override {
        if (empty()) return ;
        *(first + + );
    }
    int top() const override { return *first; }
    int front() const override { return *first; }
    bool empty() const override { return first == now; }
    int size() const override { return now - first; }
private:
    void Expansion() {
        if (now != last) return ;
        int old_size = size();
        int new_size = old_size != 0 ? old_size * 2 : 1;
        int *new_first = new int[new_size];
        int *new_now = new_first;
        new_now = copy_int(new_first, first, last);
        delete[] first;
        first = new_first;
        now = new_now;
        last = new_first + new_size;
    }
    int *first;
    int *now;
    int *last;
};
*/

class queue : public IQueue {
public:
    queue(int n = 10) : data(new int[n]), head(0), tail(-1), count(0), total(n) {}
    void push(int x) override {
        if (full()) {
            Expansion();
        }
        count + = 1, tail = (tail + 1) % total;
        data[tail] = x;
    }
    void pop() override {
        if (empty()) return ;
        count -= 1, head = (head + 1) % total;
    }
    int top() const override { return data[head]; }
    int front() const override { return data[head]; }
    bool empty() const override { return count == 0; }
    int size() const override { return count; }
    int full() const { return count == total; }
    ~queue() { delete[] data; }
    void swap(queue & amp;q) {
        std::swap(this->data, q.data);
        std::swap(this->head, q.head);
        std::swap(this->tail, q.tail);
        std::swap(this->count, q.count);
        std::swap(this->total, q.total);
    }
private:
    /*
    void Expansion() {
        if (!full()) return ;
        int old_size = size();
        int new_size = old_size != 0 ? old_size * 2 : 1;
        int *new_data = new int[new_size];
        int *now_data = new_data;
        int cnt = count;
        now_data = copy_int(now_data, data + head, data + total);
        now_data = copy_int(now_data, data, data + tail);
        delete[] data;
        data = new_data;
        head = 0, tail = count - 1;
        total = new_size;
        cout << total << endl;
    }
    */
    void Expansion() {
        int old_size = size();
        int len = old_size != 0 ? old_size * 2 : 1;
        queue q(len);
        while (!empty()) {
            q.push(top());
            pop();
        }
        swap(q);
    }
    int *data;
    int head, tail, count, total;
};

class priority_queue : public IQueue {
public:
    priority_queue(function<bool(int, int)> cmp = less<int>(), int n = 10)
                : first(new int[n]), now(first),
                last(first + n), cmp(cmp) {}
    void push(int x) override {
        if (now == last) {
            Expansion();
        }
        *(now + + ) = x;
        int temp = now - first;
        while (temp >> 1 & amp; & amp; cmp(first[temp / 2 - 1], first[temp - 1])) {
            swap(first[temp - 1], first[temp / 2 - 1]);
            temp >>= 1;
        }
    }
    void pop() override {
        if (empty()) return ;
        *first = *(--now);
        int temp = 1, cnt = now - first;
        while (temp << 1 <= cnt) {
            int ind = temp, l = temp * 2, r = temp * 2 + 1;
            if (cmp(first[temp - 1], first[l - 1])) temp = l;
            if (r <= cnt & amp; & amp; cmp(first[temp - 1], first[r - 1])) temp = r;
            if (temp == ind) break;
            swap(first[ind - 1], first[temp - 1]);
        }
    }
    int top() const override { return *first; }
    int front() const override { return *first; }
    bool empty() const override { return first == now; }
    int size() const override { return now - first; }

private:
    void Expansion() {
        if (now != last) return ;
        int old_size = size();
        int new_size = old_size != 0 ? old_size * 2 : 1;
        int *new_first = new int[new_size];
        int *new_now = new_first;
        new_now = copy_int(new_first, first, last);
        delete[] first;
        first = new_first;
        now = new_now;
        last = new_first + new_size;
    }
    int *first;
    int *now;
    int *last;
    function<bool(int, int)> cmp;
};

}

int main() {
    using namespace xyh;
    queue que;
    for (int i = 0; i < 100; i + + ) {
        que.push(i + 1);
    }
    while (!que.empty()) {
        cout << que.top() << endl;
        que.pop();
    }
    cout << "****************" << endl;
    priority_queue prque;
    for (int i = 0; i < 100; i + + ) {
        prque.push(i + 1);
    }
    while (!prque.empty()) {
        cout << prque.top() << endl;
        prque.pop();
    }
    cout << "**********************" << endl;
    priority_queue fprque(cmp1);
    for (int i = 0; i < 100; i + + ) {
        fprque.push(i + 1);
    }
    while (!fprque.empty()) {
        cout << fprque.top() << endl;
        fprque.pop();
    }
    return 0;
}