Линейные списки (продолжение). Очереди

1.

Линейные списки
(продолжение). Очереди

2.

3.

FIFO
(first in – first out)

4.

Голова
inf
Хвост
next
inf
next
inf
next
NULL

5.

6.

Описание структуры
struct node {
int data;
struct node *next;
} *front, *back;
Голова
очереди
Хвост
очереди

7. 1. Инициализация очереди (создание пустой очереди)

void initialize() {
front = back = NULL;
}

8. 2. Подсчет числа элементов очереди (размер очереди)

int getQueueSize() {
struct node *temp = front;
int count = 0;
if(front == NULL && back == NULL)
return 0;
while(temp != back){
count++;
temp = temp->next;
}
if(temp == back)
count++;
return count;
}

9. 3. Вывод первого элемента очереди

int getFrontElement() {
return front->data;
}
4. Вывод последнего элемента очереди
int getBackElement() {
return back->data;
}

10. 5. Проверка очереди на пустоту

void isEmpty() {
if (front == NULL && back == NULL)
printf("Empty Queue\n");
else
printf("Queue is not Empty\n");
}

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

void enqueue(int num) {
struct node *temp;
temp = (struct node *)malloc(sizeof(struct node));
temp->data = num;
temp->next = NULL;
if (back == NULL) {
front = back = temp;
} else {
back->next = temp;
back = temp;
}
}

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

void enqueue(int num) {
struct node *temp;
1: temp = (struct node *)malloc(sizeof(struct node));
2: temp->data = num;
3: temp->next = NULL;
4: if (back == NULL) {
5: front = back = temp;
6:} else {
7: back->next = temp;
8: back = temp;
}
}
endueue(3);
front
3
NULL
NULL
temp
3
next
temp
3
data
next
back
5
temp
temp
3
2
1

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

void enqueue(int num) {
struct node *temp;
1: temp = (struct node *)malloc(sizeof(struct node));
2: temp->data = num;
3: temp->next = NULL;
4: if (back == NULL) {
5: front = back = temp;
6:} else {
7: back->next = temp;
8: back = temp;
}
}
back
NULL
temp
8
next
temp
8
data
next
3
2
1
temp
endueue(8);
front
back
3
NULL

14.

endueue(3);
front
back
3
next
NULL
endueue(8);
front
back
3
next
8
next
NULL

15. 7. Выборка элемента из очереди

void dequeue() {
struct node *temp;
if (front == NULL) {
printf("\nQueue is Empty \n");
return;
}
else {
temp = front;
front = front->next;
if(front == NULL){
back = NULL;
}
printf("Removed Element : %d\n", temp->data);
free(temp);
}
}

16. 7. Выборка элемента из очереди

void dequeue() {
struct node *temp;
if (front == NULL) {
printf("\nQueue is Empty \n");
return;
}
else {
1:
temp = front;
2:
front = front->next;
if(front == NULL){
3:
back = NULL;
}
4:
5:
back
8
printf("Removed Element : %d\n", temp->data);
free(temp);
}
}
front
temp
3
NULL

17. 7. Выборка элемента из очереди

void dequeue() {
struct node *temp;
if (front == NULL) {
printf("\nQueue is Empty \n");
return;
}
else {
1:
temp = front;
2:
front = front->next;
if(front == NULL){
3:
back = NULL;
}
4:
5:
front = NULL
back = NULL
back
8
printf("Removed Element : %d\n", temp->data);
free(temp);
}
}
front
temp
NULL

18. Решение практических задач и использованием очереди

int main() {
FILE *f;
int info;
initialize();
if ((f=fopen("in.txt","r"))==NULL) printf("No file");
else
while(fscanf(f,"%d",&info) != EOF)
enqueue(info);
printQueue();
printf("\nSize of Queue : %d\n", getQueueSize());
printf("Front Element : %d\n", getFrontElement());
printf("Rear Element : %d\n", getBackElement());
while (front!=NULL) dequeue();
printQueue();
return 0;
}

19.

void main()
{ int choice, value;
while(1)
{ printf("Выберите пункт меню \n");
printf("1. Вставить элемент в очередь\n");
printf("2. Удалить элемент из очереди \n");
printf("3. Проверить очередь на пустоту\n");
printf("4. Считать первый элемент очереди\n");
printf("5. Получить число элементов в очереди\n");
printf("6. Выход\n");
scanf("%d", &choice);
switch (choice)
{ case 1:
insert();
break;
case 2:
deletee();
break;
case 3:
check();
break;
case 4:
first_element();
break;
case 5:
queue_size();
break;
case 6:
exit(0);
default:
printf("Неправильный выбор\n");
} } }
break;

20.

Все в очередь!!!