Динамические структуры данных. Организация данных в списковые структуры

  return Delete_Double_List(Begin_Queue->Begin); 

}

Пример 2. Дана последовательность ненулевых целых чисел. Признаком конца последовательности является число 0. Найдите среди них первый наибольший отрицательный элемент. Если такого элемента нет, то выведите сообщение об этом.

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

//главная функция

int _tmain(int argc, _TCHAR* argv[]){

  int n;

  Queue *My_Queue;

  My_Queue = new Queue();

  Make_Queue(1,My_Queue);

  while (My_Queue->End->Data != 0){

    cout << "Введите значение ";

    cin >> n;

    Add_Item_Queue(n,My_Queue);

  }

  cout << "\nОчередь: \n";

  Print_Queue(My_Queue);

  Find_Max_Negative_Element(My_Queue);

  system("pause");

  return 0;

}

 

//функция поиска первого наибольшего отрицательного элемента

void Find_Max_Negative_Element(Queue* Begin_Queue){

  int tmp;

  int max=Extract_Item_Queue(Begin_Queue);

  while (Begin_Queue->Begin->Data != 0) {

    tmp = Extract_Item_Queue(Begin_Queue);

    if (max > 0 || tmp < 0 && abs(tmp) < abs(max))

      max = tmp;

  }

  if (max > 0) printf("Элементов нет!");

  else printf("Есть такой элемент: %d", max);

}

Ключевые термины

FIFO (First Input - First Output) - это метод доступа к элементам очереди по принципу , "первый пришёл - первый вышел".

LIFO (Last Input - First Output) - это метод доступа к элементам стека по принципу "последним пришел - первым вышел"

Вершина стека - это доступный элемент стека.

Конец очереди - это позиция доступного для вставки в очередь элемента.

Начало очереди - это позиция доступного для извлечения из очереди элемента.

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

Стек - это структура данных, в которой новый элемент всегда записывается в ее начало (вершину) и очередной читаемый элемент также всегда выбирается из ее начала.

Краткие итоги

Стек и очередь - это частные случаи линейного списка.

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

Стек и очередь как динамические структуры данных можно организовать на основе линейного списка.

Основными операциями со стеком являются: создание стека; печать (просмотр) стека; добавление элемента в вершину стека; извлечение элемента из вершины стека; проверка пустоты стека; удаление стека.

Очередь является списком, у которого доступны два элемента: начало и конец очереди. Поместить элемент можно только в конец очереди, а взять элемент только из ее начала.

Основными операциями с очередью являются: создание очереди; печать (просмотр) очереди; добавление элемента в конец очереди; извлечение элемента из начала очереди; проверка пустоты очереди; удаление очереди.

Стек и очередь более экономно расходуют адресное пространство по сравнению с однонаправленными и двунаправленными списками.