Очередь через массив

270

24 февраля 2017, 01:16

Доброго времени суток! Нужно создать очередь на основе массива. Поняла это буквально и написала так

setlocale(LC_ALL, "rus");
int n = 0, k;
int mas[256];
 do
{
    k = 0;
    cin>> mas[n];
    int check = mas[n];
    for (int i = 0; i < 256; i++)
    {
        if (mas[i] == check)
            k++;
    }
    n++;
} 
   while (k <= 1);
 cout << "Колличество элементов, которые не повторяются =" <<n-1<< "\n";
 int*ptrmas = mas;
int* head = ptrmas;
int*tail = ptrmas + n - 2;
if (*head == *tail)
{
   cout << "Очередь пуста." << "\n";
   }
 else
   {
   if (*tail == 256)
       cout << "Очередь переполнена." << "\n";}

Можно ли так делать, и если нет, то как исправить и переделать?

Answer 1

Я думаю, что имелось в виду - не просто так, как у вас - разовая очередь, а кольцевой буфер на основе массива. Держите индексы начала и конца, операции тривиальны. Вы для очереди обязаны предоставить две операции - вставка в очередь, и снятие из очереди.
Вот, что-то типа такого наброска:

#include <iostream>
#include <iomanip>
using namespace std;
class Queue
{
public:
    Queue(size_t size);
    ~Queue() { delete[] data; }
    Queue(const Queue&)            = delete;
    Queue& operator=(const Queue&) = delete;
    bool empty() const { return f_ == l_; }
    bool full()  const { return (l_+1)%size == f_; }
    int  first() const { return data[f_]; } // При пустом вообще-то нужно исключение
    int  last()  const { return data[l_]; } // При пустом вообще-то нужно исключение
    int  pop();                             // При пустом вообще-то нужно исключение
    bool enqueue(int value);
private:
    int * data;
    size_t size;
    size_t f_, l_;
};

Queue::Queue(size_t size):size(size)
{
    data = new int[size];
    f_ = l_ = 0;
}
int Queue::pop()
{
    int x = data[f_];
    f_ = (f_+1)%size;
    return x;
}
bool Queue::enqueue(int value)
{
    if (full()) return false;
    data[l_] = value;
    l_ = (l_+1)%size;
    return true;
}
int main(int argc, const char * argv[])
{
    int n = 0;
    Queue q(10);
    while(q.enqueue(n)) n++;
    for(;n <= 30; ++n)
    {
        cout << q.pop() << " ";
        q.enqueue(n);
    }
    while(!q.empty()) cout << q.pop() << " ";
}

Можно, конечно, совсем тупо - при каждом изъятии из очереди сдвигать весь массив, но это уже полное издевательство...

Answer 2

Очередь можно делать на массиве, если количество элементов можно ограничить каким-то заранее известным числом и перерасход памяти не беспокоит.

Я думаю, что ваше решение немного не соответствует ожиданиям, потому что ожидал увидеть класс, реализующий очередь или его шаблон.

Однако, если задача вполне конкретна и не требует что-то кроме ответа, то вполне пойдет и ваша реализация.