Программная реализация очереди на основе массива

 

Пример 13.1

#include < stdlib.h>

#include < stdio.h>

#include < conio.h>

#include < malloc.h>

 

/////////////// Queue for int positive (x> 0)

 

typedef struct

{

int *queue;

int head;

int tail;

int size;

} QUEUE;

 

int Init(QUEUE* Queue, int nSize);

int Extract(QUEUE* Queue);

int Add(QUEUE* Queue, int nElement);

void Clear(QUEUE* Queue);

int GetSize(QUEUE* Queue);

void Free(QUEUE* Queue);

 

Программа реализации кольцевой очереди на основе массива – queue.cpp:

#include " queue.h"

/////////////// Queue for int positive (x> 0)

//////////////////////////////////////////

int Init(QUEUE* Queue, int nSize)

 

{

Queue-> queue = (int*)malloc(nSize*(sizeof(int)));

if (Queue-> queue == NULL) return -1;

Queue-> size = nSize;

Queue-> head = 0;

Queue-> tail = 0;

return nSize;

}

 

///////////////////////////////////////////

int Extract(QUEUE* Queue)

{

int w;

if (Queue-> head == Queue-> tail) return -1;

w = Queue-> queue[Queue-> head];

if (Queue-> head == Queue-> size - 1)

Queue-> head = 0;

else

Queue-> head++;

return w;

}

///////////////////////////////////////////

int Add(QUEUE* Queue, int nElement)

{

if (Queue-> tail +1 == Queue-> head)

return -1; // Очередь заполнена - запись невозможна!

 

if (Queue-> tail == Queue-> size)

Queue-> tail=0; //Достигнут конец памяти, выделенной под очередь

Queue-> queue[Queue-> tail++] = nElement;

return 1;

}

///////////////////////////////////////////

void Clear(QUEUE* Queue)

{

Queue-> head = 0;

Queue-> tail = 0;

}

///////////////////////////////////////////

int GetSize(QUEUE* Queue)

{

if (Queue-> head == Queue-> tail)

return 0; // Очередь пуста

if (Queue-> head < Queue-> tail)

return (Queue-> tail - Queue-> head);

else

return (Queue-> size - (Queue-> head - Queue-> tail));

}

///////////////////////////////////////////

void Free(QUEUE* Queue)

{ free(Queue-> queue); }

Тестовая программа:

#include " queue.h"

 

/////////////////////////// Print of queue information

void Print(QUEUE *Queue)

{

if (Queue-> head == Queue-> tail)

printf(" \nQueue is empty! ");

else

printf (" \nhead=%u, tail=%u, (%d-%d)", Queue-> head, Queue-> tail,

Queue-> queue[Queue-> head], Queue-> queue[Queue-> tail-1]);

}

void main()

{

QUEUE Queue;

Init(& Queue, 4); Print(& Queue);

Add(& Queue, 10); Print(& Queue);

Add(& Queue, 11); Print(& Queue);

Add(& Queue, 12); Print(& Queue);

Extract(& Queue); Print(& Queue);

Add(& Queue, 13); Print(& Queue);

Extract(& Queue); Print(& Queue);

Add(& Queue, 21); Print(& Queue);

Extract(& Queue); Print(& Queue);

Add(& Queue, 22); Print(& Queue);

GetSize(& Queue);

Extract(& Queue); Print(& Queue);

Extract(& Queue); Print(& Queue);

Extract(& Queue); Print(& Queue);

Clear(& Queue); Print(& Queue);

Add(& Queue, 31); Print(& Queue);

Extract(& Queue); Print(& Queue);

Free(& Queue);

getch();

}

 

Варианты индивидуальных заданий

 

1. Создать очередь для целых (положительных и отрицательных) чисел. Максимальный размер очереди вводится с экрана. Создать функции для ввода и вывода элементов очереди. Ввести 6 элементов (положительных и отрицательных). Вывести 2 первых отрицательных элемента очереди.

2. Создать очередь для массива целых (положительных и отрицательных) чисел. Максимальный размер очереди вводится с экрана. Создать функции для ввода и вывода элементов очереди. Ввести 6 элементов. При вводе чисел в очередь попадают только отрицательные элементы. Вывести все элементы очереди.

3. Создать очередь для целых (положительных и отрицательных) чисел. Максимальный размер очереди вводится с экрана. Создать функции для ввода, вывода и определения размера очереди. Ввести 6 элементов. Вывести 2 первых элемента очереди. Вывести размер оставшейся очереди.

4. Создать очередь для целых (положительных и отрицательных) чисел. Максимальный размер очереди вводится с экрана. Создать функции для ввода, вывода и определения размера очереди. Ввести 6 элементов. Вывести элементы очереди до первого отрицательного (включительно). Вывести размер оставшейся очереди.

5. Создать очередь для символов. Максимальный размер очереди вводится с экрана. Создать функции для ввода и вывода элементов очереди. Ввести эталонный символ. Вводить символы с экрана в очередь до встречи эталонного. Вывести все элементы очереди.

6. Создать очередь для символов. Максимальный размер очереди вводится с экрана. Создать функции для ввода и вывода элементов очереди. Вводить символы с экрана в очередь. После введения 3-го символа в ответ на каждый вводимый выводить крайний левый символ.

7. Создать очередь для символов. Максимальный размер очереди вводится с экрана. Создать функции для ввода, вывода и определения размера очереди. Ввести эталонный символ. Вводить символы с экрана в очередь до встречи эталонного. Вывести размер очереди.

8. Создать очередь для символов. Максимальный размер очереди вводится с экрана. Создать функции для ввода и вывода элементов очереди. Вводить символы с экрана в очередь. В случае совпадения вводимого символа с последним элементом очереди выводить первый элемент очереди.

9. Создать очередь для символов. Максимальный размер очереди вводится с экрана. Создать функции для ввода, вывода и определения размера очереди. Вводить символы с экрана в очередь. В случае совпадения вводимого символа с последним элементом очереди выводить размер очереди.

10. Создать очередь для символов. Максимальный размер очереди вводится с экрана. Создать функции для ввода и вывода элементов очереди. Добавлять символы с экрана в очередь. В случае совпадения вводимого символа с последним элементом очереди удалять и выводить на экран все элементы очереди.

11. Создать очередь для символов. Максимальный размер очереди вводится с экрана. Создать функции для ввода и вывода элементов очереди. Вводить символы с экрана. В случае совпадения вводимого символа с последним элементом очереди в очередь его не добавлять, а удалять первый элемент.

12. Создать очередь для символов. Максимальный размер очереди вводится с экрана. Создать функции для ввода и вывода элементов очереди. Вводить символы с экрана. В случае совпадения вводимого символа с последним элементом очереди выводить размер очереди.

13. Создать очередь для целых чисел. Максимальный размер очереди вводится с экрана. Создать функции для ввода и вывода элементов очереди. Ввести в очередь числа с экрана. После этого перейти в режим, при котором при каждом вводе числа из очереди удаляется первый элемент, и если он совпадает с введенным числом, то он добавляется в очередь.

14. Создать очередь для целых чисел. Максимальный размер очереди вводится с экрана. Создать функции для ввода и вывода элементов очереди. Ввести в очередь числа с экрана. После этого перейти в режим, при котором при каждом вводе числа выводится первый элемент очереди, и если он не совпадает с введенным числом, то оно заносится в очередь.

15. Создать очередь для целых чисел. Максимальный размер очереди вводится с экрана. Создать функции для ввода и вывода элементов очереди. Ввести в очередь числа с экрана. После этого перейти в режим ввода, при котором перед добавлением элемента происходит удаление одного элемента.

16. Создать дек для целых (положительных и отрицательных) чисел. Максимальный размер дека вводится с экрана. Создать функции для ввода и вывода элементов дека. Ввести 6 элементов (положительных и отрицательных). Вывести 2 первых правых отрицательных элемента дека.

17. Создать дек для массива целых чисел. Максимальный размер дека вводится с экрана. Создать функции для ввода и вывода элементов дека. Ввести 3 элемента справа и 3 слева. При вводе чисел в дек попадают только отрицательные элементы. Вывести все элементы дека.

18. Создать дек для целых (положительных и отрицательных) чисел. Максимальный размер дека вводится с экрана. Создать функции для ввода, вывода и определения размера дека. Ввести 3 элемента справа и 3 слева. Вывести по одному элементу справа и слева. Вывести размер оставшегося дека.

19. Создать дек для целых (положительных и отрицательных) чисел. Максимальный размер дека вводится с экрана. Создать функции для ввода, вывода и определения размера дека. Ввести 3 элемента справа и 3 слева. Вывести элементы дека справа до первого отрицательного (включительно). Вывести размер оставшегося дека.

20. Создать дек для символов. Максимальный размер дека вводится с экрана. Создать функции для ввода и вывода элементов дека. Ввести эталонный символ. Вводить символы в дек поочередно справа и слева до встречи эталонного. Вывести все элементы дека.

21. Создать дек для символов. Максимальный размер дека вводится с экрана. Создать функции для ввода и вывода элементов дека. Вводить элементы в дек поочередно справа и слева. При этом в ответ на добавление элемента с противоположной стороны дека один элемент удаляется.

22. Создать дек для символов. Максимальный размер дека вводится с экрана. Создать функции для ввода, вывода и определения размера дека. Ввести эталонный символ. Вводить символы в дек поочередно справа и слева до встречи эталонного. Вывести размер дека.

23. Создать дек для символов. Максимальный размер дека вводится с экрана. Создать функции для ввода и вывода элементов дека. Добавлять символы в дек поочередно справа и слева. В случае совпадения добавляемого символа с элементом на другом конце дека выводить его на экран.

24. Создать дек для символов. Максимальный размер дека вводится с экрана. Создать функции для ввода, вывода и определения размера дека. Добавлять символы в дек поочередно справа и слева. В случае совпадения добавляемого символа с элементом на другом конце дека выводить размер дека.

 

25. Создать дек для символов. Максимальный размер дека вводится с экрана. Создать функции для ввода и вывода элементов дека. Добавлять символы в дек поочередно справа и слева. В случае совпадения добавляемого символа с концом дека вывести на экран все элементы со стороны совпавшего.

26. Создать дек для символов. Максимальный размер дека вводится с экрана. Создать функции для ввода и вывода элементов дека. Добавлять символы в дек поочередно справа и слева. В случае совпадения введенного символа с элементом соответствующего конца дека его не добавлять.

27. Создать дек для символов. Максимальный размер дека вводится с экрана. Создать функции для ввода, вывода и определения размера дека. Ввести в дек символы с экрана. Вводить символы с экрана. В случае совпадения вводимого символа с одним из концов дека выводить его размер.

28. Создать дек для целых чисел. Максимальный размер дека вводится с экрана. Создать функции для ввода и вывода элементов дека. При каждом вводе числа слева удаляется элемент, и если он не совпадает с введенным числом, то введенное число добавляется справа.

29. Создать дек для целых чисел. Максимальный размер дека вводится с экрана. Создать функции для ввода и вывода элементов дека. Ввести в дек числа с экрана. После этого перейти в режим, при котором слева удаляется элемент, и если он совпадает с введенным числом, то введенное число добавляется справа, а иначе – слева.

30. Создать дек для плавающих чисел. Максимальный размер дека вводится с экрана. Создать функции для ввода и вывода элементов дека. Ввести в дек числа с экрана. После этого перейти в режим ввода, при котором перед занесением элемента происходит удаление левого элемента.

31. Дан текстовый файл. Проанализировав в программе содержимое файла, выбрать из него числа и занести в очередь. Вывести содержимое очереди на экран и посчитать сумму этих чисел. Решение в программе оформить через подпрограммы.

32. Дан текстовый файл. Проанализировав в программе содержимое файла, выбрать из него имена и занести в очередь. Вывести содержимое очереди на экран и посчитать количество элементов образованной очереди. Решение в программе оформить через подпрограммы.

33. Проверить на равенство две очереди. Решение в программе оформить через подпрограммы.

34. Найти среди 3-х (4, 5) очередей две одинаковые. Решение в программе оформить через подпрограммы.

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

36. Создать файл символьного типа. Организовывая очереди по N элементов, создать файл слов по N символов в каждом. Решение в программе оформить через подпрограммы.

37. Создать файл целого типа. Проанализировав в программе содержимое файла, создать одну очередь однозначных чисел, а вторую – двузначных. Перемножить соответственные элементы двух очередей и организовать третью

очередь. Результат вывести в текстовый файл. Решение в программе оформить через подпрограммы.

38. Используя очередь, проверить, какие строки текстового файла являются симметричными. Решение в программе оформить через подпрограммы.

39. Используя очередь, проверить на равенство два текстовых файла. Решение в программе оформить через подпрограммы.

40. Создать две очереди. Проверить, является ли одна из очередей частью другой. Решение в программе оформить через подпрограммы.