C++ int PriorityQueue 使用堆栈

Question

我刚开始学习 C++ 编程，为了练习我找到了这个任务。我必须使用基于数组的动态整数堆栈来编写 PriorityQueue。这是我到目前为止所得到的。

#include <iostream>

using namespace std;


class PrioQueue
{
private:
    int *bottom_;
    int *top_;
    int size_;
public:
    PrioQueue(int n = 20){
        bottom_ = new int[n];
        top_ = bottom_;
        size_ = n;
    }

    int getSize(){ return size_; }

    void push(int c){
        if (!full()){
            *top_ = c;  
            top_++;

        }
        else{
            resize(size_ * 2);
            *top_ = c;  
            top_++;

        }
        SortPrioQueue();
    }

    void resize(int newSize){
        //Allocate new array and copy in data
        int *newArray = new int[newSize];
        memcpy(newArray, bottom_, size_ * sizeof(int));

        // Set the top to the new array
        top_ = newArray + (top_ - bottom_);

        // Delete old array
        delete[] bottom_;

        // Update pointers and size
        bottom_ = newArray;
        size_ = newSize;

        cout << "array has been resized" << endl;
    }

    void SortPrioQueue(){

        int swap = 0; //holding variable

        for (int i = 0; i < (size_ - 1); i++)
        {
            for (int j = (i + 1); j < size_; j++)
            {
                if (bottom_[i] > bottom_[j])
                {
                    swap = bottom_[i];
                    bottom_[i] = bottom_[j];
                    bottom_[j] = swap;
                }
            }
        }

    }


    int num_items() {
        return (top_ - bottom_);
    }
    int pop(){
        top_--;
        return *top_;
    }
    int full() {
        return (num_items() >= size_);
    }
    int empty() {
        return (num_items() <= 0);
    }
    void print(){
        cout << "Stack currently holds " << num_items() << " items: ";
        for (int *element = bottom_; element<top_; element++) {
            cout << " " << *element;
        }
        cout << "\n";
    }
    ~PrioQueue(){ // stacks when exiting functions
        delete[] bottom_;
    }
};
int main(){
    PrioQueue s(5);
    s.print(); cout << "\n";
    s.push(10); s.push(24); s.push(53); s.push(74); s.push(5);
    s.print(); cout << "\n";
    //s.SortPrioQueue();//if i call it here
    s.print(); cout << "\n";

    while (!s.empty()) s.pop();
    if (s.num_items() != 0) {
        cout << "Error: Stack is corrupt!\n";
    }
    s.print(); cout << "\n";
    // destructor for s automatically called
    system("pause"); // execute M$-DOS' pause command
    return 0;
}

SortPrioQueue() 方法似乎有问题。如果我从 main() 方法调用它，它工作正常。但是如果我从 push() 方法调用它，那么我就会得到这个。

在此先感谢您的帮助。

Answer 1

SortPrioQueue() 应该使用 top_ - _bottom（或 num_items()）作为限制而不是 size.

C++ int PriorityQueue 使用堆栈

C++ int PriorityQueue using stack

c++

arrays

stack

priority-queue