VPF::Очередь на C++ - Форум программистов

KIDD

Дата 21.10.2004, 13:21 (ссылка)

(голосов:1)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 69
Регистрация: 19.3.2004

Репутация: 1
Всего: 1

Товарищи, подскажите.

Как сделать очередь(FIFO) на С++ наилучшим способом. Тип данных, например какой нибудь шаблон или структура содержащая переменные.

Спасибо

chipset

Дата 21.10.2004, 13:22 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 4071
Регистрация: 11.1.2003
Где: Seattle, US

Репутация: 27
Всего: 165

std::stack

--------------------

Цитата(Jimi Hendrix)

Well, I stand up next to a mountain
And I chop it down with the edge of my hand

Vaulter

Дата 21.10.2004, 13:27 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 1724
Регистрация: 30.12.2002
Где: бункер

Репутация: 2
Всего: 22

Standart Template Library
queue - The template class describes an object that controls a varying-length sequence of elements.

Код


#include <queue>

Добавлено @ 13:28
упс ;)
я про LIFO :hehe

--------------------

KIDD

Дата 21.10.2004, 13:38 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 69
Регистрация: 19.3.2004

Репутация: 1
Всего: 1

Vaulter я тебя не понял, # include <queue> подойдет, или нет?

Gabryael

Дата 21.10.2004, 19:44 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 8
Регистрация: 11.9.2004

Репутация: 1
Всего: 1

Цитата(chipset)

std::stack

это LIFO.
А вот std::queue - это FIFO.
from MSDN:
The queue class supports a first-in, first-out (FIFO) data structure. A good analogue to keep in mind would be people lining up for a bank teller. Elements (people) may be added to the back of the line and are removed from the front of the line. Both the front and the back of a line may be inspected. The restriction to accessing only the front and back elements in this way is the reason fur using the queue class.

Цитата(KIDD)

# include <queue> подойдет, или нет?

Да, подойдет.

Это сообщение отредактировал(а) Gabryael - 21.10.2004, 19:45

cardinal

Дата 21.10.2004, 19:59 (ссылка)

(нет голосов)

Загрузка ...

Инженер

Профиль
Группа: Экс. модератор
Сообщений: 6003
Регистрация: 26.3.2002
Где: Германия

Репутация: 2
Всего: 99

У меня тут одна старая наработка по этому поводу была. Вот погляди...

fifo.h

Код

#include "list.h"

#ifndef FIFO_H
#define FIFO_H

class item;

template <class T>
class FIFO
{
public:
	// remove the last item from the fifo
	void popFront() { fifolist.popFront();}
	// add an element to the end of the fifo
	void pushBack(T data) { fifolist.pushBack(data); }
	// get the first item from the fifo
	T first() { return fifolist.first();}
private:
	list<T> fifolist;
};

#endif // FIFO_H

list.h

Код

// simple linked list data structure
// (c) 2003 by cardinal
// Warning: this code has not been well tested
// we do not make any bets whether it works


#ifndef LIST_H
#define LIST_H

#include <assert.h>

template <class T>
class list
{
public:
	list(){ size = 0;};

	void pushBack(T data)
	{
  if (size)
  {
  	listEnd = listEnd->next = AddItem(data);
  }
  else
  	listHead = listEnd = AddItem(data);
	}

	// remove the last item from the list
	void popFront() { assert (size); remove(listHead);}

	// get the first item from the list
	T first() { assert (size); return listHead->data;}

	virtual ~list()	{while (size){popFront();}}

private:
	class item;
	typedef item* Handle;
	Handle listHead;
	Handle listEnd;

	void remove (Handle b)
	{
  if (listHead != b->next)
  	listHead = b->next;
  size--;
  delete b;
	}

	Handle AddItem (T data)
	{
  Handle i = new item(data);
  size++;
  return i;
	}

	class item 
	{
    public:
  item(T val) { data = val; next = this; };
  T data;
  Handle next;
  friend class list;
	};

private:
	int size;
};

#endif /* LIST_H */

Вот тебе пример:

Код

#include "stdafx.h"
#include "fifo.h"

int main(int argc, char* argv[])
{
	FIFO<int> fifo;
	fifo.pushBack(5);
	fifo.pushBack(6);
	fifo.pushBack(1);
	int x = fifo.first();
	fifo.popFront();
	int y = fifo.first();
	fifo.popFront();
	int z = fifo.first();
	fifo.popFront();

	return 0;
}

Если получится откомпилировать, то считай и делать ничего не надо

--------------------

Немецкая оппозиция потребовала упростить натурализацию иммигрантов
В моем блоге: Разные истории из жизни в Германии

"Познание бесконечности требует бесконечного времени, а потому работай не работай - все едино". А. и Б. Стругацкие

np9mi7

Дата 22.10.2004, 10:49 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 553
Регистрация: 17.8.2003
Где: Volgograd, Russia

Репутация: 5
Всего: 10

Можно и так...
(помимо очереди, есть стек и список...)

Код


/*Библиотека Структуры данных.
библиокека может работать с любыми типами переменных.Для печати списка необходимо(если используется пользовательский тип)перегрузить функции потоков ввода вывода cout. Интерфейс к классу определен в объявлении класса Spisok, Stack,Queue.Класс SpisokEl используется внутри библиотеки и не нужен пользователю.*/
/////////////////////////////////////////////////
#include <iostream.h>
#include <assert.h>
/////////////////////////////////////////////////
template<class ELEMTYPE>
class SpisokEl;
template<class ELEMTYPE>
class Spisok;
template<class ELEMTYPE>
class Stack;
template<class ELEMTYPE>
class Queue;
/////////////////////////////////////////////////
//очередь
#ifndef	QUEUE_H
#define QUEUE_H
template<class ELEMTYPE>
class Queue

	public:
  Queue();          	//конструктор
  ~Queue();          	//деструктор
  void Enqueue(const ELEMTYPE&);      //добавим в конец очереди
  bool Dequeue(ELEMTYPE&);      	//вытащим из начала очереди
  const bool IsEmpty();        //проверка на пустоту
  void Print();          //печать элементов очереди
	protected:
  Spisok<ELEMTYPE> S;        	//тут храним саму очередь
;
//методы класса
//конструктор
template<class ELEMTYPE>
Queue<ELEMTYPE>::Queue()

;

//деструктор
template<class ELEMTYPE>
Queue<ELEMTYPE>::~Queue()

;

//элемент в конец очереди
template<class ELEMTYPE>
void Queue<ELEMTYPE>::Enqueue(const ELEMTYPE& pNew)

	S.InsertAtBack(pNew);

//вытаскиваем элемент из очереди
template<class ELEMTYPE>
bool Queue<ELEMTYPE>::Dequeue(ELEMTYPE& value)

	return (bool)S.RemoveFromFront(value);

//печать очереди
template<class ELEMTYPE>
void Queue<ELEMTYPE>::Print()

	S.Print();

//проверка на пустоту
template<class ELEMTYPE>
const bool Queue<ELEMTYPE>::IsEmpty()

	return S.IsEmpty();

#endif
//стек
#ifndef STACK_H
#define STACK_H
template<class ELEMTYPE>
class Stack

	public:
  Stack();          	//конструктор
  ~Stack();          	//деструктор
  void Push(const ELEMTYPE&);      	//добавляем эдемент
  bool Pop(ELEMTYPE&);        //берем элемент
  const bool IsEmpty();        //проверка на пустоту
  void Print();          //печать стека
	protected:
  Spisok<ELEMTYPE> S;        	//связанный список
;
//описываем все методы класса
//конструктор
template<class ELEMTYPE>
Stack<ELEMTYPE>::Stack()

;

//деструктор
template<class ELEMTYPE>
Stack<ELEMTYPE>::~Stack()

;

//операция добавления в стек
template<class ELEMTYPE>
void Stack<ELEMTYPE>::Push(const ELEMTYPE& pNew)

	S.InsertAtFront(pNew);

//операция извлечения из стека
template<class ELEMTYPE>
bool Stack<ELEMTYPE>::Pop(ELEMTYPE& value)

	return (bool)S.RemoveFromFront(value);

//печать стека
template<class ELEMTYPE>
void Stack<ELEMTYPE>::Print()

	S.Print();

//проверка на пустоту стека
template<class ELEMTYPE>
const bool Stack<ELEMTYPE>::IsEmpty()

	return S.IsEmpty();

#endif
//елемент списка
#ifndef SPISOKEL_H
#define SPISOKEL_H
//-----------------------------------------------
template<class ELEMTYPE>
class SpisokEl

	friend class Spisok<ELEMTYPE>;      	//друг сам класс список
	public:
  SpisokEl(const ELEMTYPE&);      	//конструктор
  const ELEMTYPE GetElem();      	//возвращаем данные из елемента
	private:
  ELEMTYPE Element;        	//сами данные
  SpisokEl *pNext;        	//указатель на следующий
;
//-----------------------------------------------
//конструктор
template<class ELEMTYPE>
SpisokEl<ELEMTYPE>::SpisokEl(const ELEMTYPE &pNew)

	Element=pNew;          	//присваиваем новое значение  pNext=0;            //зануляем указатель на следующий

//возвращаем копию элемента
template<class ELEMTYPE>
const ELEMTYPE SpisokEl<ELEMTYPE>::GetElem()

	return Element;          	//возвращаем данные из элемента списка 
//-----------------------------------------------
#endif
//список
#ifndef SPISOK_H
#define SPISOK_H
//-----------------------------------------------
template<class ELEMTYPE>
class Spisok

	public:
  Spisok();          	//конструктор
  ~Spisok();          	//деструктор
  void	InsertAtFront(const ELEMTYPE&);    //вставка в начало списка
  void	InsertAtBack(const ELEMTYPE&);    	//вставка в конец списка
  bool	RemoveFromFront(ELEMTYPE&);    	//удалить с начала
  bool	RemoveFromBack(ELEMTYPE&);      //удалить с конца
  bool	Get(bool (*)(const ELEMTYPE&),ELEMTYPE&);  //вытаскиваем елемент по указанному свойству
  const bool IsEmpty();        //проверка на пустоту
  void Print();          //печать всего списка
	private:
  SpisokEl<ELEMTYPE> *pFirst;      	//указатель на первый элемент
  SpisokEl<ELEMTYPE> *pLast;      	//указатель на последний элемент
  SpisokEl<ELEMTYPE> *GetNewElem(const ELEMTYPE&);	//утилита
;
//-----------------------------------------------
//конструктор по умалчанию
template<class ELEMTYPE>
Spisok<ELEMTYPE>::Spisok()

	pFirst=0;pLast=0;

//деструктор
template<class ELEMTYPE>
Spisok<ELEMTYPE>::~Spisok()

	if(!IsEmpty())
	
  //список не пуст
  cout<<"Удаляем все элементы из списка\n"<<flush;
  //создаем элемент нужный внутри функции
  SpisokEl<ELEMTYPE> *pTemp1,*pTemp2;pTemp1=pFirst;  	while(pTemp1=!0)
  
  	pTemp2=pTemp1;    cout<<pTemp2->Element<<"\n"<<flush;    pTemp1=pTemp1->pNext;    delete pTemp2;
  
	
	cout<<"Все элементы удалены...\n"<<flush; 
//вытаскиваем элемент по указанному свойству
template<class ELEMTYPE>
bool Spisok<ELEMTYPE>::Get(bool (*funk)(const ELEMTYPE&),ELEMTYPE& value)

	SpisokEl<ELEMTYPE> *pTemp1,*pTemp2;
	if(IsEmpty())          	//проверка на пустоту списка
	
  return false;
	
	pTemp1=pFirst;pTemp2=0;        	//устанавливаем указатель на начало списка
	while(!(funk(pTemp1->Element)))      	//пока не найдем нужный элемент
	
  pTemp2=pTemp1;          //сохраняем предыдущий элемент
  pTemp1=pTemp1->pNext;        //сдвиг на следующий элемент
  if(pTemp1==0)          //тут мы просто не нашли нужный элемент и достигли конца
  
  	return false;
  
	
	if(!pTemp2)            //проверка на то что в списке один элемент
	
  pFirst=pLast=0;          //нулим указатели на начала списков
	
	else
	
  pTemp2->pNext=pTemp1->pNext;      //устанавливаем новый указатель на следующий элемент(делаем "перескок")  
	value=pTemp1->Element;        	//сохраняем переменную
	delete pTemp1;          	//удаляем элемент из списка
	return true;

//вставка элемента в начало списка
template<class ELEMTYPE>
void Spisok<ELEMTYPE>::InsertAtFront(const ELEMTYPE &value)

	SpisokEl<ELEMTYPE> *pNew=GetNewElem(value);    //создаем новый элемент списка  if(IsEmpty())
	
  pFirst=pLast=pNew;        	//проверка на пустоту
	
	else
	
  pNew->pNext=pFirst;        	//устанавливаем указатель на первый
  pFirst=pNew;          //первый есть новый
	

//вставка елемента в конец списка
template<class ELEMTYPE>
void Spisok<ELEMTYPE>::InsertAtBack(const ELEMTYPE &value)

	SpisokEl<ELEMTYPE> *pNew=GetNewElem(value);    //создаем новый элемент списка  if(IsEmpty())
	
  pFirst=pLast=pNew;        	//проверка на пустоту
	
	else
	
  pLast->pNext=pNew;        	//устанавливаем указатель на последний  	pLast=pNew;          	//последний есть новый
	

//удаление с начала списка
template<class ELEMTYPE>
bool Spisok<ELEMTYPE>::RemoveFromFront(ELEMTYPE &value)

	if(IsEmpty())          	//проверка на пустоту
	
  return false;
	
	SpisokEl<ELEMTYPE> *pTemp=pFirst;      //сохраняем указетель на первый элемент  if(pFirst==pLast)
	
  pLast=pFirst=0;          //проверка на то что в списке один элемент
	
	else
	
  pFirst=pFirst->pNext;        //смещаем указатель на первый элемент
	
	value=pTemp->Element;        	//сохраняем данные
	delete pTemp;          	//удаляем узел
	return true;

//удаление элемента с конца списка
template<class ELEMTYPE>
bool Spisok<ELEMTYPE>::RemoveFromBack(ELEMTYPE &value)

	if(IsEmpty())          	//проверка на пустоту
	
  return false;
	
	else
	
  SpisokEl<ELEMTYPE> *pTemp1=pLast;    	//сохраняем указатель на последний элемент  	if(pFirst==pLast)
  
  	pLast=pFirst=0;        	//проверка на то что в списке один элемент
  
  else
  
  	SpisokEl<ELEMTYPE> *pTemp2=pFirst;    //указатель для пробежки по всему списку    while(pTemp2->pNext!=pLast)
  	
    pTemp2=pTemp2->pNext;      //ищем конец списка
  	
  	pLast=pTemp2;        	//смещаем указетель на последний элемент
  	pTemp2->pNext=0;
  
  value=pTemp1->Element;        //выдергмваем элемент
  delete pTemp1;          //удаляем узел из списка
  return true;
	

//проверка на пустоту
template<class ELEMTYPE>
const bool Spisok<ELEMTYPE>::IsEmpty()

	if(pFirst==0)
	
  return true;
	
	return false;

//возвращаем указатель на ближайший узел
template<class ELEMTYPE>
SpisokEl<ELEMTYPE>* Spisok<ELEMTYPE>::GetNewElem(const ELEMTYPE& value)

	SpisokEl<ELEMTYPE> *pNew=new SpisokEl<ELEMTYPE>(value);	//выделяем память под новый элемент  assert(pNew!=0);          //проверка на выделение памяти
	return pNew;

template<class ELEMTYPE>
void Spisok<ELEMTYPE>::Print()

	if(IsEmpty())          	//проверка на пустоту списка
	
  cout<<"Список пуст...\n"<<flush;
  return;
	
	SpisokEl<ELEMTYPE> *pTemp=pFirst;      //отпечатываем все элементы  cout<<"Список состоит из: \n"<<flush;
	while(pTemp!=0)
	
  cout<<pTemp->Element<<"\n"<<flush;
  pTemp=pTemp->pNext;
	

//-----------------------------------------------
#endif

--------------------

"Я точно знаю то, что ничего не знаю..." Сократ.
evolution project

bel_nikita

Дата 23.10.2004, 21:25 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Эксперт
Сообщений: 2304
Регистрация: 12.10.2003
Где: Поезд №21/22 ( ст . Прага )

Репутация: 21
Всего: 47

Народ, а про синхронизацию досптупа к очереди при работе 2-х и более потоков забыли.

--------------------

— регистрация доменов от 150 руб.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »