Стеки и очереди: структура памяти, способы ее формирования, основные операции

Стек (магазин) является упорядоченной, линейной, неоднородной структурой. Эти структура реализуются в виде специальным образом организованных областей ОЗУ компьютера либо в качестве самостоятельных блоков памяти. В стеке ячейки памяти (или регистры стековой памяти) соединяются друг с другом таким образом, что при занесении данных в первую ячейку содержимое всех остальных сдвигается в соседние вниз, при считывании – содержимое сдвигается вверх по ячейкам, как показано на Рис.3.1. Другими словами, вход в стек возможен только через первую ячейку (вершину стека), поэтому извлекаться первой будет та информация, которая была занесена последней, подобно пассажиру переполненного автобуса. Отличие очереди от стека только в том, что извлечение информации производится в порядке «первым вошел – первым вышел», т.е. со дна стека.

Еще одна классическая структура с ограниченным доступом к данным это очередь. Способ доступа к данным ограничен 2 концами - началом и концом очереди по принципу «первый при Очередь – структура данных, как и стек представляющая собой последовательность элементов. Добавление элементов происходит на одном конце последовательности, удаление – на другом. Дек – двусторонняя очередь, т.е. и добавление и удаление осуществляется с обеих сторон. Представление очередей и деков на массиве отличается тем, что последовательность элементов может «перемещаться» по массиву, следовательно, чтобы последовательность не выскочила за границы, нужно границы соединить вместе (зациклить). Проблемы все те же – возможность переполнения.

Реализация на динамической структуре использует ту же особенность (цикличность) и лучше всего представляется в виде кольцевого двунаправленного списка

шел, первый ушел» (FIFO - first in, first out)

23) Топологии сетей: звезда, шина, кольцо; Ethernet, CSMA/CD.

Термин «топология», или «топология сети», характеризует физическое расположение компьютеров, кабелей и других компонентов сети. Топология — это стандартный термин, который используется профессионалами при описании основной компоновки сети. Чтобы совместно использовать ресурсы или выполнять другие сетевые задачи, компьютеры должны быть подключены друг к другу. Для этой цели в большинстве сетей применяется кабель. Однако просто подключить компьютер к кабелю, соединяющему другие компьютеры, не достаточно. Различные типы кабелей в сочетании с различными сетевыми платами, сетевыми операционными системами и другими компонентами требуют и различного взаимного расположения компьютеров.Топология может также определять способ взаимодействия компьютеров в сети. Различным видам топологий соответствуют различные методы взаимодействия, и эти методы оказывают большое влияние на сеть.