Similar presentations:
Линейные списки (продолжение). Очереди
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;