Чем отличается Очередь на базе списка от Очереди на базе массива?

[TwiX]

В универе дали задачу написать Очередь на базе списка... А представляю, как писать очередь на базе массива - причём это довольно легко. А что изменится в очереди на базе списка?

[Stilet]

Ничего. список это тот же массив.
Единственное что - элементы в списке не обязательно стоят рядом.
Они могут быть разбросаны в памяти безструктурно. Каждый элемент списка знает где лежат его соседи.
Ну а в случае с очередью просто напросто из списка будет выбираться элементы не из его конца а из его головы, таким образом, следующий после первого элемента станет главным

[TwiX]

Т.е. можно запрогать через упорядоченный массив? Или можно через неупорядоченный массив, но его элементы будут хранить не только то, что им нужно хранить, но ещё и номер следующего за ним? Как лучше?) Спасибо

[Гром]

Определяем структуру узла:

struct Node
{
Node* next;
int value;
};

(плюс конструктор желательно). Далее реализуем очередь:

class Queue
{
public:
Queue();
~Queue();
void push(int val);
int pop();
private:
Node* top;
Node* bottom;
};

При помощи push вставляем новый узел с нужными данными следом за bottom, делаем для вставленного

bottom -> next = 0;

При вызове pop возвращаем данные из узла top, попутно удаляя этот узел, top'ом становится next удаленного узла.
Плюс проверки на равенство нулю top и bottom когда надо.
Если у узла будет деструктор

Node::~Node()
{
if (next)
   delete next;
}

то перед удалением top в push присваиваем его next ноль, чтобы не удалить сразу весь список.
Вот так вот можно сделать очередь на базе списка.
P.S. Ну или можно вставлять новый узел перед top, а удалять узел bottom - как вам будет удобней.

[TwiX]

Не совсем то, что мне нужно... Нужно реализовать через шаблон. Ниже выложу, что начал писать, но там почему неправильно работает Push (переменная i создаётся не новая, а используются старая и если попробовать запушить 3 числа, то после выталкивания последнего, получим муть)

template <class T>
struct TItem
{
	TItem* prev;
	T value;
};

template <class T>
class TQueue
{
public:
	TQueue();
	int push(const T&);
	int pop(T&);
	int isEmpty() { return size == 0 ; }
private:
	int size ;  // Number of elements on Stack
	TItem<T>* top;
	TItem<T>* bottom;
};


template <class T>
TQueue<T>::TQueue()
{
	size=0;
	top=0;
	bottom=0;
}

template <class T>
int TQueue<T>::push(const T& item)
{
	TItem<T> i; //вот тут что-то не то
	i.value=item;
	i.prev=0;
	if (size==0)
	{
		top=&i;
		bottom=top;
	}
	else
	{
		top->prev=&i; //*top->prev=i;
		top=&i;
		top->prev=0;
	}
	size++;
}

template <class T>
int TQueue<T>::pop(T& item)
{
	T i;
	i=(*top).value;
	item=i;
	top=top->prev;
	size--;
}

Думал изменить struct на class, но не помогло (вроде в С++ это одно и то же)

[Гром]

Заменяйте тип value в узле с int на шаблонный - и будет то, что надо.
Далее, по вашему коду. Общий совет - в конструкторах лучше использовать списки инициализации. Для встроенных типов это, может быть, и безразлично, а вот для объектов классов (особенно без конструктора по умолчанию), констант и ссылок - это критично. Поэтому желательно всегда использовать подход, основанный на списке инициализации:

template <class T>
TQueue<T>::TQueue():
	size(0),
	top(0),
	bottom(0)
	{
	}

По поводу push и pop - я бы реализовал их так (переделать под шаблон будет легко):

Node::Node(int val):
 value(val), next(0)
 {
 }

void Queue::push(int val)
{
Node* NewNode = new Node(val);   //Кстати, вы объявляете новый элемент статически - потому у вас и получается полный бред
if (bottom) //Если есть последний элемент, т.е. есть хотя бы один
 bottom -> next = NewNode;
else
 {
 top = NewNode;
 bottom = NewNode;
 }
}

int pop()
{
if (top) //Если хоть один элемент есть
 {
 Node* del = top;
 int val = del -> value;
 top = top -> next;
 del -> next = 0;
 delete del;
 return val;
 }
else //Ошибка, к примеру, сообщим о ней и просто вернем ноль
 {
 std::cerr << "Queue is empty!" << std::endl;
 return 0;
 }
}

Вставляем элемент следом за bottom, извлекаем top (а вы как вставляете почему-то перед top, так и извлекаете top, а это уже какой-то стек вообще).
И обычно в односвязных списках все-таки ссылаются на "следующий", а не на "предыдущий" элемент - это насчет названий prev и next.

[TwiX]

Pop я в конце писал... Там и правда надо было bottom писать - тупанул. Сейчас попробую исправить
Спасибо

Добавлено:
По поводу ссылки на следующий - это всё-таки дело вкуса=) Я очередь себе представляю как столбик, где сверху вставляют элементы, а снизу забирают) Поэтому и удобней prev использовать =)

Добавлено:
И не понял, почему у меня не работало и что такое списки инициализации)

Добавлено:
Всё, разобрался. Нужно у меня просто исправить TItem<T> i; на TItem<T>* i = new TItem<T>; (я раньше так и хотел, но думал, что так только массивы создаются - пробовал писать new TItem<T> i xD

[tema93]

Сообщение от TwiX

В универе дали задачу написать Очередь на базе списка... А представляю, как писать очередь на базе массива - причём это довольно легко. А что изменится в очереди на базе списка?

Доброго времени дня! А я не представляю как на базе массива создать двунаправленную очередь (дек) с ограничением по входу и удалить , прибавить элемент, очистить дек и проверить на пустоту.
Если Вы представляете - поделитесь своим предствлением, пожалуйста