Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Очередь на C++

Автор: KIDD 21.10.2004, 13:21

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

Автор: chipset 21.10.2004, 13:22

std::stack

Автор: Vaulter 21.10.2004, 13:27

Standart Template Library queue - The template class describes an object that controls a varying-length sequence of elements. Код #include <queue> Добавлено @ 13:28 упс ;) я про LIFO

Автор: KIDD 21.10.2004, 13:38

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

Автор: Gabryael 21.10.2004, 19:44

Цитата(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> подойдет, или нет? Да, подойдет.

Автор: cardinal 21.10.2004, 19:59

У меня тут одна старая наработка по этому поводу была. Вот погляди... 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

Можно и так... (помимо очереди, есть стек и список...) Код /*Библиотека Структуры данных. библиокека может работать с любыми типами переменных.Для печати списка необходимо(если используется пользовательский тип)перегрузить функции потоков ввода вывода 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

Автор: bel_nikita 23.10.2004, 21:25

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

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)