Редактирование: Очередь

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
== Определение ==
 
== Определение ==
 
[[Файл: Fifo_new.png|right|150px]]
 
[[Файл: Fifo_new.png|right|150px]]
'''Очередь''' (англ. ''queue'')  {{---}} это структура данных, добавление и удаление элементов в которой происходит путём операций <tex> \mathtt{push} </tex> и <tex> \mathtt{pop} </tex> соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (англ. ''first-in, first-out {{---}} FIFO''). У очереди имеется '''голова''' (англ. ''head'') и '''хвост''' (англ. ''tail''). Когда элемент ставится в очередь, он занимает место в её хвосте. Из очереди всегда выводится элемент, который находится в ее голове. Очередь поддерживает следующие операции:
+
'''Очередь''' (англ. ''queue'')  {{---}} это структура данных, добавление и удаление элементов в которой происходит путём операций <tex> \mathtt{push} </tex> и <tex> \mathtt{pop} </tex> соответственно. Притом первым из очереди удаляется элемент, который был помещен туда первым, то есть в очереди реализуется принцип «первым вошел — первым вышел» (англ. ''first-in, first-out {{---}} FIFO''). У очереди имеется '''голова''' (англ. ''head'') и '''хвост''' (англ''tail''). Когда элемент ставится в очередь, он занимает место в её хвосте. Из очереди всегда выводится элемент, который находится в ее голове. Очередь поддерживает следующие операции:
 
* <tex> \mathtt{empty} </tex> {{---}} проверка очереди на наличие в ней элементов,
 
* <tex> \mathtt{empty} </tex> {{---}} проверка очереди на наличие в ней элементов,
 
* <tex> \mathtt {push} </tex> (запись в очередь) {{---}} операция вставки нового элемента,
 
* <tex> \mathtt {push} </tex> (запись в очередь) {{---}} операция вставки нового элемента,
Строка 18: Строка 18:
 
=== push ===
 
=== push ===
 
  '''function''' push(x : '''T'''):
 
  '''function''' push(x : '''T'''):
   '''if''' (size() != n)
+
   elements[tail] = x
    elements[tail] = x
+
  tail = (tail + 1) % n
    tail = (tail + 1) % n
 
  
 
=== pop ===
 
=== pop ===
 
  '''T''' pop():
 
  '''T''' pop():
   '''if''' (empty())  
+
   '''if''' (size == 0)  
 
     '''return null'''
 
     '''return null'''
 
   x = elements[head]
 
   x = elements[head]
Строка 31: Строка 30:
  
 
=== size ===
 
=== size ===
  '''int''' size()
+
  '''int''' size(s : '''stack<T>''')
 
   '''if''' head > tail
 
   '''if''' head > tail
 
     '''return''' n - head + tail
 
     '''return''' n - head + tail
Строка 92: Строка 91:
 
=== pop ===
 
=== pop ===
 
  '''T''' pop():
 
  '''T''' pop():
   '''if''' '''not''' rightStack.empty()
+
   '''if''' '''not''' rigthStack.empty()
 
     '''return''' popRight()  
 
     '''return''' popRight()  
 
   '''else'''
 
   '''else'''
Строка 106: Строка 105:
 
* эту реализацию несложно модифицировать для получения минимума в текущей очереди за <tex>O(1)</tex>.
 
* эту реализацию несложно модифицировать для получения минимума в текущей очереди за <tex>O(1)</tex>.
 
'''Минусы:'''
 
'''Минусы:'''
* если <tex>\mathtt{leftStack}</tex> не пуст, то операция <tex> \mathtt{pop} </tex> может выполняться <tex>O(n)</tex> времени, в отличие от других реализаций, где <tex> \mathtt{pop} </tex> всегда выполняется за <tex>O(1)</tex>.
+
* если <tex>\mathtt{leftStack}</tex> не пуст, то операция <tex> \mathtt{pop} </tex> может выполняться <tex>O(n)</tex> времени, в отличии от других реализаций, где <tex> \mathtt{pop} </tex> всегда выполняется за <tex>O(1)</tex>.
  
 
== Реализация на шести стеках ==
 
== Реализация на шести стеках ==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: