Лекции по информатике - Очередь (queue)

Общая информация

Очередь (queue) - это динамическая структура данных с последовательным доступом. Доступ к элементам очереди осуществляется следующим образом: элементы из нее можно доставать только в том порядке, в котором они были добавлены в нее.

Работа очереди организована по принципу FIFO (First In First Out) - первым пришел, первым ушел.

Пример реализации очереди целых чисел на C++

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

/*
** Класс "Очередь"
** Слава Антонов (с) 2004
** http://slava.users.otts.ru
*/

#ifndef QUEUE_H
#define QUEUE_H

#include <iostream.h>
#include <malloc.h>

// Тип элемента очереди
typedef int datatype;

// Элемент односвязного списка
struct listitem
{
  datatype data;
  listitem* next;
};

class equeue
{
  private:
    char* msg;  // сообщение об ошибке
  public:
    equeue(const char* errmsg) { msg = strdup(errmsg); }
    ~equeue() { free(msg); }
    const char* getmsg() { return msg; }
};

#define EQUEUE_EMPTY "Queue is empty"

class cqueue
{
  private:
    listitem* head; // голова односвязного списка
    listitem* tail; // хвост односвязного списка
    unsigned cnt;   // длина очереди (кол-во элементов в ней)
  public:
    cqueue();
      // конструктор по-умолчанию
    cqueue(const cqueue&);
      // конструктор копирования
      // этот конструктор вызывается в следующей ситуации:
      // cqueue Q2 = Q1

    ~cqueue() { clear(); }
      // деструктор
    cqueue& clear(); 
      // удалить все элементы очереди
    unsigned getCnt() const { return cnt; }
    cqueue& del();
      // удалить один элемент из начала очереди
    bool empty() const { return head == NULL; } 
      // признак пустой очереди
    cqueue& push(const datatype&); 
      // добавить элемент в конец очереди
    datatype pop(); 
      // извлеч элемент из начала очереди
    const datatype& get() const; 
      // посмотреть элемент в начале очереди
    cqueue& set(const datatype&); 
      // заменить элемент в начале очереди

    bool operator == (const cqueue&) const; 
      // оператор сравнения
    bool operator != (const cqueue& q) const
      { return !(*this == q); }
    cqueue& operator = (const cqueue&); 
      // оператор присваивания
    friend ostream& operator << (ostream&, const cqueue&); 
      // оператор вывода
};

cqueue::cqueue()
{
  head = tail = NULL;
}

cqueue::cqueue(const cqueue& q)
{
  head = tail = NULL;
  *this = q;
}

cqueue& cqueue::clear()
{
  while(!empty()) del();
  return *this;
}

cqueue& cqueue::del()
{
// если стек пуст - генерируем исключение
  if(empty()) throw(equeue(EQUEUE_EMPTY));

  listitem* tmp = head->next; // запоминаем указатель на
                              // следующий элемент очереди
  delete head; // удаляем элемент...
// ...и переводим указатель на следующий элемент
  if(!tmp)
    head = tail = NULL;
  else
    head = tmp;
  cnt--;
  return *this;
}

cqueue& cqueue::push(const datatype& data)
{
  listitem* item = new listitem;
  item->data = data;
  item->next = NULL;
  if(!head)
  {
    head = item;
    tail = head;
  } else
  {
    tail->next = item;
    tail = item;
  }
  cnt++;
  return *this;
}

datatype cqueue::pop()
{
  if(empty()) throw(equeue(EQUEUE_EMPTY));
  datatype data = head->data;
  del();
  return data;
}

const datatype& cqueue::get() const
{
  if(empty()) throw(equeue(EQUEUE_EMPTY));
  return head->data;
}

cqueue& cqueue::set(const datatype& data)
{
  if(empty()) throw(equeue(EQUEUE_EMPTY));
  head->data = data;
  return *this;
}

bool cqueue::operator == (const cqueue& q) const
{
  if(this == &q) return true;
  if(getCnt() != q.getCnt()) return false;
  listitem* h1 = head;
  listitem* h2 = q.head;
  while(h1)
  {
    if(h1->data != h2->data) return false;
    h1 = h1->next;
    h2 = h2->next;
  }
  return false;
}

cqueue& cqueue::operator = (const cqueue& q)
{
  if(*this == q) return *this;
  clear();
  listitem* item = q.head;
  while(item)
  {
    push(item->data);
    item = item->next;
  }
  return *this;
}

ostream& operator << (ostream& s, const cqueue& q)
{
  listitem* item = q.head;
  while(item)
  {
    s << item->data << endl;
    item = item->next;
  }
  return s;
}
 
#endif

Реализация шаблона "Очередь" на С++

/*
** Шаблон "Очередь"
** Слава Антонов (с) 2004
** http://slava.users.otts.ru
*/

#ifndef QUEUE_TEMPLATE_H
#define QUEUE_TEMPLATE_H

#include <iostream.h>
#include <malloc.h>

// Элемент односвязного списка
template <class T>
struct listitem
{
  T data;
  listitem<T>* next;
};

class equeue
{
  private:
    char* msg;  // сообщение об ошибке
  public:
    equeue(const char* errmsg) { msg = strdup(errmsg); }
    ~equeue() { free(msg); }
    const char* getmsg() { return msg; }
};

#define EQUEUE_EMPTY "Queue is empty"

template <class T>
class tqueue
{
  private:
    listitem<T>* head; // голова односвязного списка
    listitem<T>* tail; // хвост односвязного списка
    unsigned cnt;      // длина очереди (кол-во элементов в ней)
  public:
    tqueue();
      // конструктор по-умолчанию
    tqueue(const tqueue<T>&);
      // конструктор копирования
      // этот конструктор вызывается в следующей ситуации:
      // tqueue Q2 = Q1

    ~tqueue() { clear(); }
      // деструктор
    tqueue<T>& clear(); 
      // удалить все элементы очереди
    unsigned getCnt() const { return cnt; }
    tqueue<T>& del();
      // удалить один элемент из начала очереди
    bool empty() const { return head == NULL; } 
      // признак пустой очереди
    tqueue<T>& push(const T&); 
      // добавить элемент в конец очереди
    T pop(); 
      // извлеч элемент из начала очереди
    const T& get() const; 
      // посмотреть элемент в начале очереди
    tqueue<T>& set(const T&); 
      // заменить элемент в начале очереди

    bool operator == (const tqueue<T>&) const; 
      // оператор сравнения
    bool operator != (const tqueue<T>& q) const
      { return !(*this == q); }
    tqueue<T>& operator = (const tqueue<T>&); 
      // оператор присваивания
};

template <class T>
tqueue<T>::tqueue()
{
  head = tail = NULL;
}

template <class T>
tqueue<T>::tqueue(const tqueue<T>& q)
{
  head = tail = NULL;
  *this = q;
}

template <class T>
tqueue<T>& tqueue<T>::clear()
{
  while(!empty()) del();
  return *this;
}

template <class T>
tqueue<T>& tqueue<T>::del()
{
// если стек пуст - генерируем исключение
  if(empty()) throw(equeue(EQUEUE_EMPTY));

  listitem<T>* tmp = head->next; // запоминаем указатель на
                                 // следующий элемент очереди
  delete head; // удаляем элемент...
// ...и переводим указатель на следующий элемент
  if(!tmp)
    head = tail = NULL;
  else
    head = tmp;
  cnt--;
  return *this;
}

template <class T>
tqueue<T>& tqueue<T>::push(const T& data)
{
  listitem<T>* item = new listitem<T>;
  item->data = data;
  item->next = NULL;
  if(!head)
  {
    head = item;
    tail = head;
  } else
  {
    tail->next = item;
    tail = item;
  }
  cnt++;
  return *this;
}

template <class T>
T tqueue<T>::pop()
{
  if(empty()) throw(equeue(EQUEUE_EMPTY));
  T data = head->data;
  del();
  return data;
}

template <class T>
const T& tqueue<T>::get() const
{
  if(empty()) throw(equeue(EQUEUE_EMPTY));
  return head->data;
}

template <class T>
tqueue<T>& tqueue<T>::set(const T& data)
{
  if(empty()) throw(equeue(EQUEUE_EMPTY));
  head->data = data;
  return *this;
}

template <class T>
bool tqueue<T>::operator == (const tqueue<T>& q) const
{
  if(this == &q) return true;
  if(getCnt() != q.getCnt()) return false;
  listitem<T>* h1 = head;
  listitem<T>* h2 = q.head;
  while(h1)
  {
    if(h1->data != h2->data) return false;
    h1 = h1->next;
    h2 = h2->next;
  }
  return false;
}

template <class T>
tqueue<T>& tqueue<T>::operator = (const tqueue<T>& q)
{
  if(*this == q) return *this;
  clear();
  listitem<T>* item = q.head;
  while(item)
  {
    push(item->data);
    item = item->next;
  }
  return *this;
}
 
#endif

197-577-902 ICQ-статус