Реализация неупорядоченной очереди
Также интересует наиболее хороший вариант реализации неуп. очереди на базе связного списка.
очередь на то и очередь, что у нее метод доступа FIFO. в ней нельзя удалять случайные элементы.
Это цитата из книги, о которой я говорю. Концепция очередей FIFO мне ясна, меня интересует реализация неупорядоченной очереди.
ты пропустил то место, где Седжвик говорил, что очередь - это абстракция? очередь отличается от списка методом доступа(в списке он произвольный). а вот реализовывать ее в массиве или с дин. памятью - это к структуре данных не относится. к тому же, список тоже можно сделать в массиве.
отчего? в первый массив пишем где реально находится элемент. индекс массива - номер элемента по счету. ну а во втором массиве записываем элементы. как раз постоянное время удаления тут гарантировать можно. вот с добавлением - да, загвоздка. но я не увидел ту часть, где говорилось о постоянном времени операций.
5 |0| |4|
4 |0| |0|
3 |5| |0|
2 |2| |3|
1 |1| |2|
другой вариант мне неизвестен.
со структурами - практически то же самое. поля структуры включают индекс след. элемента в массиве, индекс пред. элемента в массиве, ну и само значение. еще нужены переменные под последний свободный элемент массива и под последний добавленный. при удалении какого-то элемента, обращаемя к последнему свободному, переписываем его "указатель на следующий" номером только что удаленного, переписываем значение переменой, которая хранит номер последнего свободного элемента. добавление: берем номер последнего добавленного, смотрим в поле структуры "следующий элемент", добавляем туда новый, переписываем переменную, которая хранит индекс последнего добавленного. тут можно гарантировать постоянное время, как мне кажется. хотя такой же алгоритм можно организовать без структур, но добавив третий массив к моему предыдущему алгоритму.
...
Также интересует наиболее хороший вариант реализации неуп. очереди на базе связного списка.
В этой теме есть
Но в std::queue реализация получше :)
Меня интересует вариант реализации непорядоченной очредеи, а не FIFO
2 Alm3n
Мы в данный момент говорим не об абстракциях, а о реализации очереди с помощью массива.
Удаление/добавление элементов идут рука об руку и вариант реализации с чем-то одним не подходит.
Второй вариант может привести к моменту, когда добавление элемента невозможно:
мы добавляем несколько элементов, удаляем не последний, после чего добавляем один и не можем добавить еще, т.к. не знаем, где есть еще свободные места в массиве.
он вроде бы не конкретизировал. там всего два предложения о ней. или все же конкретизировал?
Ну а то что хотел афтор можно реализовать и так например(говнокодец :)):
#include <stdlib.h>
#include <cstring>
#include <time.h>
using namespace std;
template <class T> class myqueue
{
private:
T ** mqueue;
int length;
public:
myqueue()
{
mqueue=NULL;
length=0;
srand ( time(NULL) );
};
bool isEmpty()//проверка на пустоту
{
return !length;
};
void push(T element)//добавление в конец списка
{
T * newelement=new T(element);
T ** newqueue=new T*[length+1];
if(length)
{
memcpy(newqueue,mqueue,sizeof(T*)*length);
delete [] mqueue;
}
mqueue=newqueue;
mqueue[length]=newelement;
length++;
};
T pop()//выборка случайного значения
{
T ret=T();
if(length)
{
int rnd=rand()%length;
ret=*mqueue[rnd];
delete mqueue[rnd];
T ** newqueue=new T*[length-1];
memcpy(newqueue,mqueue,sizeof(T*)*rnd);
memcpy(newqueue+rnd,mqueue+rnd+1,sizeof(T*)*(length-rnd-1));
delete [] mqueue;
mqueue=newqueue;
length--;
}
return ret;
};
};
int main()
{
myqueue<int> a;
int b=5;
a.push(b);
a.push(24);
a.push(36);
a.push(48);
a.push(60);
cout<<a.pop()<<endl;
cout<<a.pop()<<endl;
cout<<a.pop()<<endl;
cout<<a.pop()<<endl;
cout<<a.pop()<<endl;
cout<<a.pop()<<endl;//0 (елементы закончились, выводим новый елемент с конструктором по умолчанию)
cout<<a.isEmpty()<<endl;//1 (1-пустой, 0-непустой)
myqueue<char> c;
char d='A';
c.push(d);
c.push('B');
c.push('C');
cout<<c.pop()<<endl;
cout<<c.pop()<<endl;
cout<<c.pop()<<endl;
cout<<c.pop()<<endl;// (елементы закончились, выводим новый елемент с конструктором по умолчанию)
cout<<c.isEmpty()<<endl;//1 (1-пустой, 0-непустой)
return 0;
}
В книге же предложено реализовать на массиве с конечным количеством элементов (какойто прям random bounded queue получается :))