Нужен очень шаблон класса "очередь" на С++, с простыми операциями, такими как вставить новый элемент в очередь, взять вершину очереди, проверка на пустоту очереди, размер очереди, вывод элементов и т.п. Может у кого есть что-нить подобное?
в FAQ есть это все на паскале.
Ну и поиском пользуйся...
Здесь выкладывался шаблонный class TQueue: http://forum.pascal.net.ru/index.php?s=&showtopic=14077&view=findpost&p=81649
(реализация - в присоединенном файле, на расширение не смотри, это именно C++, просто тогда еще нельзя было присоединять СРР файлы)
С шаблонами и классами работаю первый раз. Попытался написать очередь через массив.
Не понимаю, почему функции 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;
}
//////////////////////////////////////////////////////////
// Конец модуль теста и программы
//////////////////////////////////////////////////////////
template <class T>(допустимые индексы - от 0 до 9, чтобы было понятно, о чем я)
T queue <T> :: showHead () {
cout << "\nend = " << end << " ";
cout << "Head - " << q[end];
}
volvo
Да и правда…
Но теперь вообще запутался…Как написать тогда функции просмотра головы и хвоста, подсказать можешь?
И если я вынимаю один элемент их очереди, то место освобождается, а всунуть я получается ничего уже не могу туда
Значит, так...
Проблема - в том, что такой способ не очень подходит для реализации очереди, это вообще-то для реализации Стека было придумано - с очередью надо будет поизвращаться... Я вот тут кое-что набросала - в MinGW вроде работает:
Что еще хотелось бы отметить: половину из этих методов можно внести прямо в определение класса, кроме этого -
// посмотреть первый элементМетод ничего не возвращает - я сделала его void-ом...
template <class T>
T queue <T> :: showHead () {
cout << "\nHead - " << q[end];
}
Большое спасибо
Вот эту функцию можно пояснить еще:
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;
}
Алена, volvo, w@rlock
здорово
правда функцию pop тоже не до конца понял... комментарии мона?
T value = q[begin];?
volvo
спасибо.
но почему ++i, а не i++ ? вроде бы менял, изменений не заметил...
да. но ведь в данном примере в цикле pop при ++i значение i[1] присвоется i[2]. а при i++ i[0] присвоется i[1] ?
for(int i = 0; i < end; ++i) q[i] = q[i + 1];аналогично
int i = 0;
while(i < end) {
q[i] = q[i + 1];
++i;
}
а вот если ещё конструктор копирования написать свой? как это сделать?
Писал-писал этот шаблон, а так и не сдал
Сказали сменить реализацию Аргументы примерно такие, что неприлично делать очередь с линейным временем доступа... Кто что может подсказать? Как написать правильно? Очень срочно нужно...
Ссылка на то, как правильно - в третьем сообщении темы... Однако, тебе это не понравилось, ты стал делать по-своему... Тогда извини, но я не понимаю, что ты хочешь... Делай по-своему дальше...
он у меня не компилится просто... тем более как просто от туда очередь то выдрать?
Я тут тоже очередь пытаюсь всё сделать (некоторые вещи уже из выше написаного взял) У 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;
}
Извиняюсь за оффтоп:
Компилит, причем ТОЛЬКО под ДОС... Качать здесь: http://www.mai-dep704.ru/soft/ (Turbo C++ 3), потом надо будет еще настроить IDE, в частности, прописать в Options -> Directories правильные пути...