Очередь

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

Очередь организована, в отличие от стека, согласно дисциплине обслуживания FIFO:

  • FIRST - первый
  • INPUT - вошел
  • FIRST - первый
  • OUTPUT - вышел

Очередь

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

Существует несколько способов реализации очереди:

  • с помощью одномерного массива;
  • с помощью связанного списка;
  • с помощью класса объектно-ориентированного программирования.

Простейшие операции с очередью:

  • init() инициализация очереди.
  • insert (q, x) — помещение элемента x в конец очереди q (q — указатель на очередь);
  • x=remove (q) — удаление элемента x из очереди q;
  • isempty(q) — возвращает true (1), если очередь пуста и false (0) в противном случае;
  • print(q) – вывод элементов очереди q.

Рассмотрим реализацию очереди на базе массива. Используем массив и две переменные:

  • frnt – позиция первого элемента в очереди;
  • rear – позиция последнего элемента в очереди

Изначально frnt=1 и rear=0.

Очередь пуста, если rear<frnt.

Число элементов в очереди можно определить как

n = rear-frnt+1
#define QMAX 100
struct queue {
  int qu[QMAX];
  int rear, frnt;
};
Инициализация очереди
void init(struct queue *q) {
  q->frnt = 1;
  q->rear = 0;
  return;
}
Добавление элемента в очередь
void insert(struct queue *q, int x) {
  if(q->rear < QMAX-1) {
    q->rear++;
    q->qu[q->rear]=x;
  }
  else
    printf("Очередь полна!\n");
  return;
}
Проверка пустоты очереди
int isempty(struct queue *q) {
  if(q->rear < q->frnt)    return(1);
  else  return(0);
}
Вывод элементов очереди
void print(struct queue *q) {
  int h;
  if(isempty(q)==1) {
    printf("Очередь пуста!\n");
    return;
  }
  for(h = q->frnt; h<= q->rear; h++)
    printf("%d ",q->qu[h]);
  return;
}
Удаление элемента из очереди
int remove(struct queue *q) {
  int x;
  if(isempty(q)==1) {
    printf("Очередь пуста!\n");
    return(0);
  }
  x = q->qu[q->frnt];
  q->frnt++;
  return(x);
}

Недостатком в предложенной реализации очереди является то, что очередь смещается в сторону старших адресов массива, что может вызвать скорое переполнение.
Для устранения этого недостатка предложена другая реализация функции удаления элемента из очереди:

int removex(struct queue *q) {
  int x, h;
  if(isempty(q)==1) {
    printf("Очередь пуста!\n");
    return(0);
  }
  x = q->qu[q->frnt];
  for(h = q->frnt; h < q->rear; h++) {
    q->qu[h] = q->qu[h+1];
  }
  q->rear--;
  return(x);
}

Пример Создать очередь из 8 элементов. Вывести ее на экран. Поочередно удалить все элементы очереди.

int main() {
  struct queue *q;
  int a;
  system("chcp 1251");
  system("cls");
  q = (queue*)malloc(sizeof(queue));
  init(q);
  print(q);
  for(int i=0;i<8;i++) {
    printf("Введите элемент очереди: ");
    scanf("%d",&a);
    insert(q, a);
  }
  printf("\n");
  print(q);
  while(q->frnt <= q->rear) {
    a = remove(q);
    printf("\nУдален элемент %d\n", a);
    print(q);
  }
  getchar(); getchar();
  return 0;
}

Результат выполнения
queue1

Реализация очереди на базе односвязного линейного списка
struct list {
  int field;
  struct list *ptr;
};
struct queue {
  struct list *frnt, *rear;
};

Инициализация очереди
Очередь пуста если   q->front = q->rear = 0.

void init(struct queue *q) {
  q->frnt = 0;
  q->rear = 0;
}

Проверка пустоты очереди

int isempty(struct queue *q) {
  if(q->frnt==0)
    return(1);
  else
    return(0);
}

Добавление элемента в очередь

void insert(struct queue *q, int x) {
  if((q->rear==0) && (q->frnt==0)) {
    q->rear = init(x);
    q->frnt = q->rear;
  } else
    q->rear = addelem(q->rear, x);
}

Вывод элементов очереди

void print(struct queue *q) {
  struct list *h;
  if(isempty(q)==1) {
    printf("Очередь пуста!\n");
    return;
  }
  for(h = q->frnt; h!= NULL; h=h->ptr)
    printf("%d ",h->field);
  return;
}

Удаление элемента из очереди

int remove(struct queue *q) {
  struct list *temp;
  int x;
  if(isempty(q)==1) {
    printf("Очередь пуста!\n");
    return(0);
  }
  x = q->frnt->field;
  temp = q->frnt;
  q->frnt = q->frnt->ptr;
  free(temp);
  return(x);
}

Получение первого элемента в очереди без его удаления

int test(struct queue *q) {
  int x;
  x = q->frnt->field;
  return(x);
}

Пример Создать очередь из 8 элементов на базе ОЛС. Вывести ее на экран. Поочередно удалить все элементы очереди.

int main() {
  struct queue *q;
  int a;
  system("chcp 1251");
  system("cls");
  q = (queue*)malloc(sizeof(queue*));
  init(q);
  print(q);
  for(int i=0;i<8;i++) {
    printf("Введите элемент очереди: ");
    scanf("%d",&a);
    insert(q, a);
  }
  printf("\n");
  print(q);
  while(q->frnt!= NULL) {
    a = remove(q);
    printf("\nУдален элемент %d\n", a);
    print(q);
  }
  getchar(); getchar();
  return 0;
}

Результат выполнения
Результат выполнения: очередь

Реализация очереди на базе класса ООП
#include <iostream>
using namespace std;
class Queue {
    static const int SIZE=100;
    int *queue;
    int frnt, rear;
  public :
    Queue () ;
    void push ( int num ) ;
    void out();
    int size();
    void pop();
    int front();
    int back();
} ;
//Конструктор
Queue::Queue() {
  queue = new int[SIZE];
  frnt = rear = 0 ;
}
//Вывод элементов очереди
void Queue::out() {
  for(int i=frnt+1;i<rear+1;i++)
    cout<<" "<<queue[i];
}
//Помещение элемента в очередь
void Queue::push ( int num ) {
  if ( rear+1 == frnt || ( rear + 1 ==SIZE && !frnt )) {
    cout << "очередь полна" <<endl ;
    return ;
  }
  rear++;
  if ( rear==SIZE ) rear = 0 ;
  queue [ rear ] = num;
}
// Извлечение элемента из очереди
void Queue::pop() {
  if ( frnt == rear ) {
    cout << "очередь пуста" <<endl ;
    return ;
  }
  frnt++;
  if ( frnt==SIZE ) frnt = 0 ;}
//Определение размера очереди
int Queue::size() {
  int s=0;
  for(int i=frnt; i<rear; i++)
    s++;
  return s;
}
// Последний элемент очереди
int Queue::back() {
return queue[rear]; }
// Первый элемент очереди
int Queue::front() {
return queue[frnt+1]; }
int main() {
  Queue queue1;
  int i;
  system("chcp 1251");
  system("cls");
  for (i= 1 ; i <= 5 ; i++ )
    queue1.push ( i ) ;
  cout<<"Изначальная очередь ";
  queue1.out();
  cout<<endl;
  cout<<"введите еще элемент: ";
  cin>>i;
  queue1.push(i);
  cout<<"теперь очередь имеет следующий вид"<<endl;
  queue1.out();
  cout<<endl<<"Размер очереди:"<<endl;
  cout<<queue1.size();
  cout<<endl <<"последний элемент:"<< endl;
  cout<<queue1.back();
  cout<<endl<<"первый элемент"<<endl;
  cout<<queue1.front();
  cout<<endl <<"удаление элемента";
  queue1.pop();
  cout<<endl <<"текущие данные";
  queue1.out();
  cout<<endl <<"еще одно добавление элемента";
  queue1.push(i);
  queue1.out();
  cout<<endl;
  cin.get(); cin.get();
  return 0;
}

Результат выполнения
Очередь: программа
Назад


Назад: Структуры данных

Комментариев к записи: 1

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *