шаблон класса очередь на С++, может у кого есть? Опции

[lays]

Нужен очень шаблон класса "очередь" на С++, с простыми операциями, такими как вставить новый элемент в очередь, взять вершину очереди, проверка на пустоту очереди, размер очереди, вывод элементов и т.п. Может у кого есть что-нить подобное?

[мисс_граффити]

в FAQ есть это все на паскале.
Ну и поиском пользуйся...

[volvo]

Здесь выкладывался шаблонный class TQueue: моделирование работы банка

(реализация - в присоединенном файле, на расширение не смотри, это именно C++, просто тогда еще нельзя было присоединять СРР файлы)

[w@rlock]

С шаблонами и классами работаю первый раз. Попытался написать очередь через массив.
Не понимаю, почему функции showHead () и showTail () работают не так…
И вообще, если кто может проверьте правильность реализации…
Компилятор Dev-C++.

/* 

Шаблон очереди и модуль тест.
Язык реализации: С++

*/

#include <iostream>

// размер массива (по умолчанию) под очередь
#define N 10 

using namespace std;

//////////////////////////////////////////////////////////
// Начало шаблона
//////////////////////////////////////////////////////////


template <class T>
class queue {
    
    private :
	        
           T *q;  	      // указатель на массив
	       int begin;     // первый элемент очереди
	       int end;       // последний элемент очереди
	           
    public :
	       
	       queue (void);       // конструктор
	       ~queue ();	       // деструктор	
	       bool isEmpty ();    // проверка на пустоту
	       T size ();          // количество элементов в очереди
	       T pop (void);       // взятие элемента
	       void push (T i);    // добавление элемента
           T showHead ();     // посмотреть первый элемент
	       T showTail ();  // посмотреть последний элемент
	       T makeEmpty ();     // очистить очередь
};


// конструктор
template <class T>
queue <T> :: queue (void) {
    if (!(q = new T[N])) {
            cout << "Can't create array, because hav't free memory!\n";
            return;
    }
    begin = end = 0;
    cout << "Initialization ok.\n";
}

// дестуктор
template <class T>
queue <T> :: ~queue () {
    delete q;
    cout << "\nDestroyed.";
}

// проверка на пустоту
template <class T>
bool queue <T> :: isEmpty () {
    return begin;
} 
 
// размер очереди
template <class T>
T queue <T> :: size () {
    return (begin-end);
} 
    
//  заполнение очереди
template <class T>
void queue <T> :: push (T i) {
    if (begin == N) {
	   cout << "Full.\n";
	   return;
    }
    q[begin++] = i;
}

// вынимает элемент
template <class T>
T queue <T> :: pop (void) {
     if (begin == end) {
        cout << "Empty.\n";
        return 0;
     }
     return q[end++];   
}
    
//////////////////////////////////////////
//   НЕ РАБОТАЕТ!!!
/////////////////////////////////////////
    
// посмотреть первый элемент
template <class T>
T queue <T> :: showHead () {
    cout << "\nHead - " << q[end];
}

// посмотреть хвост
template <class T>
T queue <T> :: showTail () {
  if (begin == end) {
      cout << "\nTail - " << q[begin];
  }
  else cout << "\nTail - " << q[begin-1];
}

// очистка очереди
template <class T>
T queue <T> :: makeEmpty () {
    begin = 0;
    end = 0;
}    


//////////////////////////////////////////////////////////
// Конец шаблона
//////////////////////////////////////////////////////////


//////////////////////////////////////////////////////////
// Начало модуль теста
//////////////////////////////////////////////////////////


int main(int argc, char *argv[])
{
    
    // создаем объекты
    queue <int> a;
    queue <double> b;
    queue <long int> c;
    
    // начинаем тестировать работу
    cout << "Now queue is empty (return 0):";
    cout <<"\n" << a.isEmpty();  
    
    for (int i = 0; i < N; i++) {
        a.push(i);
    }
    
    a.showHead();
    cout << "\n" <<a.size();
    cout <<"\n"  << a.isEmpty();  
    a.showTail();
    
    // вынимаем элементы очереди
    cout << endl;
    for (int i = 0; i < N; i++) {
        cout <<  a.pop() << " ";   
    }
    
    // функции не правильно работают
    a.showHead();    
    
    b.showHead();
    b.showTail();  
    
    b.push(2.5);
    b.push(3.5);
    b.push(6.89);
    
    cout << "\n" << b.size();
    
    b.showHead();
    b.showTail();
    cout << "\n" <<b.pop() << " ";   
    cout << "\n" <<b.pop() << " ";   
    cout << "\n" <<b.pop() << " ";   
    cout << "\n" << b.size();
    // явный вызов деструктора
    a.~queue();
    b.~queue();
    
    system("PAUSE");
    return EXIT_SUCCESS;
}

//////////////////////////////////////////////////////////
// Конец модуль теста и программы
//////////////////////////////////////////////////////////

[volvo]

Не понимаю, почему функции showHead () и showTail () работают не так…

Измени showHead вот так, и посмотри, ЧТО ты пытаешься выводить:

template <class T>
T queue <T> :: showHead () {
    cout << "\nend = " << end << " ";
    cout << "Head - " << q[end];
}

(допустимые индексы - от 0 до 9, чтобы было понятно, о чем я)

[w@rlock]

volvo
Да и правда…
Но теперь вообще запутался…Как написать тогда функции просмотра головы и хвоста, подсказать можешь?
И если я вынимаю один элемент их очереди, то место освобождается, а всунуть я получается ничего уже не могу туда

[Алена]

Значит, так...

Проблема - в том, что такой способ не очень подходит для реализации очереди, это вообще-то для реализации Стека было придумано - с очередью надо будет поизвращаться... Я вот тут кое-что набросала - в MinGW вроде работает:

Что еще хотелось бы отметить: половину из этих методов можно внести прямо в определение класса, кроме этого -

// посмотреть первый элемент
template <class T>
T queue <T> :: showHead () {
    cout << "\nHead - " << q[end];
}

Метод ничего не возвращает - я сделала его void-ом...

[w@rlock]

Большое спасибо
Вот эту функцию можно пояснить еще:

template <class T>
T queue <T> :: pop (void) {
	if (end < 0) {
		cout << "Empty.\n";
        return 0;
	}
	T value = q[begin];
    	for(int i = 0; i < end; ++i) q[i] = q[i + 1];
	end -= 1;
	return value;
}

Что такое: T value = q[begin]; ?
И что делается в цикле и почему i++ и end -= 1?

[lays]

Алена, volvo, w@rlock
здорово
правда функцию pop тоже не до конца понял... комментарии мона?

[volvo]

Что такое:

T value = q[begin];

?

Запоминание первого (головного) элемента для того, чтобы вернуть его значение из функции...

И что делается в цикле и почему i++ и end -= 1?

В цикле происходит последовательный сдвиг всех элементов до "хвостового" включительно на 1 позицию влево - т.е., ближе к "голове", ибо произошло выталкивание одного элемента из очереди, остальные должны занять его место... Обойму пистолетную в руках держал? Когда вытаскиваешь верхний патрон, все остальные сдвигаются, правда? Здесь то же самое (несмотря на то, что что к обойме более применимо понятие стека)...

А end -= 1 это уменьшаем номер "хвостового" элемента на 1, один элемент из очереди ушел...

[lays]

volvo
спасибо.
но почему ++i, а не i++ ? вроде бы менял, изменений не заметил...

[volvo]

но почему ++i, а не i++

А для отдельно стоящего оператора это не играет роли... Обе версии выполняют одинаковые действия (увеличение значения переменной на 1)...

[lays]

да. но ведь в данном примере в цикле pop при ++i значение i[1] присвоется i[2]. а при i++ i[0] присвоется i[1] ?

[volvo]

for(int i = 0; i < end; ++i) q[i] = q[i + 1];

аналогично

int i = 0;
while(i < end) {
  q[i] = q[i + 1];
  ++i;
}

какая разница, будет последним оператором ++i или i++, объясни мне!!! Он же здесь НЕ в выражении, а отдельный оператор! А НЕ в выражении разницы между префиксным/постфиксным инкрементом НЕТ.

[w@rlock]

а вот если ещё конструктор копирования написать свой? как это сделать?

[w@rlock]

Писал-писал этот шаблон, а так и не сдал
Сказали сменить реализацию Аргументы примерно такие, что неприлично делать очередь с линейным временем доступа... Кто что может подсказать? Как написать правильно? Очень срочно нужно...

[volvo]

Ссылка на то, как правильно - в третьем сообщении темы... Однако, тебе это не понравилось, ты стал делать по-своему... Тогда извини, но я не понимаю, что ты хочешь... Делай по-своему дальше...

[w@rlock]

он у меня не компилится просто... тем более как просто от туда очередь то выдрать?

[lays]

Я тут тоже очередь пытаюсь всё сделать (некоторые вещи уже из выше написаного взял) У volvo не беру по причине, что ещё не такого уровня, многие вещи не понимаю, поэтому пытаюсь свою.

Внизу то, что пока получилось...Только говорят, что у меня некорректная работа с памятью...смотрите мол конструктор и деструктор и думайте...
Что не так и как исправить?

#include <iostream>

#define N 20

using namespace std;

template <class T>
class queue{
  
   private:
  
      T q[N];
      T *begin;
      T *end;
  
   public:
  
      queue();
      ~queue();
      void push(T);
      T pop();
      T showHead();
      bool isEmpty();
      void makeEmpty();
};

template <class T>
queue<T> :: queue(){
   begin = end = q;
   cout << "\n:: Initialization ok."; 
}

template <class T>
queue <T> :: ~queue() {
    cout << "\n:: Destroyed.";
}

template <class T>
bool queue <T> :: isEmpty(){
   return (begin == end);
}

template <class T>
void queue <T> :: push(T i){
   *end = i;
   if(end ==(q + N-1)){
      end = q;
   }
   else{end++;}
}

template <class T>
void queue <T> :: makeEmpty() {
   begin = end = q;
   cout << "\n:: Queue is cleaned.";
}

template <class T>
T queue <T> :: showHead(){
   if(this->isEmpty()){
      cout << "\n:: Queue is empty."; 
      return 0;
   }
   else { return (*begin);}
}

T queue <T> :: pop(){
   if(this->isEmpty()){
      cout << "\n:: Queue is empty."; 
      return 0;
   }
   else{
      T first = this->showHead();
      if (begin == q + N - 1) {
            begin = q;
      }
      else { begin++; } 
      return first;
   }
}

main() {
   
  cout << "::::::: Module test ::::::::";
  cout << "\n:: Creating new queue.";
  
  queue <int> a;
  
  cout << "\n:: Elements pushing in <int> queue...";
  a.push(14);
  a.push(12);
  a.push(16);
  a.push(17);
    
  for (int i = 0; i < 9; i++) {
        a.push(i);
  } 

  cout << "\n:: Head - " << a.showHead() << endl;
  cout << "\n:: Poped head - " <<  a.pop();
  cout << "\n:: Head - " << a.showHead() << endl;
   
  cout << "\n:: All elements: ";
  cout << "\n:: ";
  for (int i = 0; i < 12; i++) {
        cout <<  a.pop() << " ";
  } 
  
  // явный вызов деструктора
  a.~queue();
  
  // return 0 
  system("PAUSE");
  return EXIT_SUCCESS;
  
}

Сообщение отредактировано: lays - 11.01.2007 23:41

[volvo]

он у меня не компилится просто...

Не знаю, что там может НЕ компилиться... Вот выдранная из той программы очередь:

(проверено под Turbo C++)
 Q01.CPP ( 1.67 килобайт ) Кол-во скачиваний: 463


(проверено под GCC/MinGW)
 test.cpp ( 1.44 килобайт ) Кол-во скачиваний: 407


Других компиляторов не держу...

lays, у тебя будет то же самое, что и в предыдущем варианте - опять не понравится преподавателю... Ну не делается так очередь, это же ДСД - Динамическая Структура Данных, нельзя ее ограничивать сразу же массивом...