Помощь - Поиск - Пользователи - Календарь
Полная версия: шаблон класса очередь на С++
Форум «Всё о Паскале» > Современный Паскаль и другие языки > Ада и другие языки
lays
Нужен очень шаблон класса "очередь" на С++, с простыми операциями, такими как вставить новый элемент в очередь, взять вершину очереди, проверка на пустоту очереди, размер очереди, вывод элементов и т.п. Может у кого есть что-нить подобное? smile.gif
мисс_граффити
в FAQ есть это все на паскале.
Ну и поиском пользуйся...
volvo
Здесь выкладывался шаблонный class TQueue: моделирование работы банка

(реализация - в присоединенном файле, на расширение не смотри, это именно C++, просто тогда еще нельзя было присоединять СРР файлы)
w@rlock
С шаблонами и классами работаю первый раз. Попытался написать очередь через массив.
Не понимаю, почему функции showHead () и showTail () работают не так… nea.gif
И вообще, если кто может проверьте правильность реализации…smile.gif
Компилятор 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
Да и правда… smile.gif
Но теперь вообще запутался…Как написать тогда функции просмотра головы и хвоста, подсказать можешь?
И если я вынимаю один элемент их очереди, то место освобождается, а всунуть я получается ничего уже не могу туда sad.gif unsure.gif
Алена
Значит, так...

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

Что еще хотелось бы отметить: половину из этих методов можно внести прямо в определение класса, кроме этого -
// посмотреть первый элемент
template <class T>
T queue <T> :: showHead () {
cout << "\nHead - " << q[end];
}
Метод ничего не возвращает - я сделала его void-ом...
w@rlock
Большое спасибо smile.gif
Вот эту функцию можно пояснить еще:


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
здорово smile.gif good.gif
правда функцию pop тоже не до конца понял... wink.gif комментарии мона? rolleyes.gif
volvo
Цитата(w@rlock @ 8.01.2007 18:28)

Что такое:
T value = q[begin];
?
Запоминание первого (головного) элемента для того, чтобы вернуть его значение из функции...
Цитата(w@rlock @ 8.01.2007 18:28)
И что делается в цикле и почему i++ и end -= 1?

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

А end -= 1 это уменьшаем номер "хвостового" элемента на 1, один элемент из очереди ушел...
lays
volvo
спасибо. cool.gif smile.gif
но почему ++i, а не i++ ? вроде бы менял, изменений не заметил... blink.gif
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
Писал-писал этот шаблон, а так и не сдал sad.gif
Сказали сменить реализацию blink.gif dry.gif mad.gif Аргументы примерно такие, что неприлично делать очередь с линейным временем доступа...sad.gif Кто что может подсказать? Как написать правильно? Очень срочно нужно...sad.gif
volvo
Ссылка на то, как правильно - в третьем сообщении темы... Однако, тебе это не понравилось, ты стал делать по-своему... Тогда извини, но я не понимаю, что ты хочешь... Делай по-своему дальше...
w@rlock
он у меня не компилится просто...sad.gif тем более как просто от туда очередь то выдрать? sad.gif
lays
Я тут тоже очередь пытаюсь всё сделать (некоторые вещи уже из выше написаного взял) wink.gif У 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;

}

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

(проверено под Turbo C++)
Нажмите для просмотра прикрепленного файла

(проверено под GCC/MinGW)
Нажмите для просмотра прикрепленного файла

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

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

Где его можно скачать? Он компилит под дос?
volvo
Компилит, причем ТОЛЬКО под ДОС... Качать здесь: http://www.mai-dep704.ru/soft/ (Turbo C++ 3), потом надо будет еще настроить IDE, в частности, прописать в Options -> Directories правильные пути...
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.