Стек — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определение)
м (Поправка пунктуации.)
(не показаны 34 промежуточные версии 5 участников)
Строка 1: Строка 1:
 
== Определение ==
 
== Определение ==
 
[[Файл: lifo.png|thumb|right|200px|Стек]]
 
[[Файл: lifo.png|thumb|right|200px|Стек]]
'''Стек''' (от англ. ''stack'' {{---}} стопка) {{---}} структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Притом первым из стека удаляется элемент, который был помещен туда последним, то есть в стеке реализуется стратегия «последним вошел {{---}} первым вышел» (last-in, first-out {{---}} LIFO). Названия операций работы со стеком являются аллюзиями к стопкам (stacks) в реальной жизни как, например, удерживаемые пружиной стопки тарелок, используемые в кафетериях {{---}} порядок вытаскивания тарелок из стопки обратен порядку их в неё помещению, и лишь (текущая) верхняя тарелка может быть извлечена.
+
'''Стек''' (от англ. ''stack'' {{---}} стопка) {{---}} структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Притом первым из стека удаляется элемент, который был помещен туда последним, то есть в стеке реализуется стратегия «последним вошел {{---}} первым вышел» (last-in, first-out {{---}} LIFO). Примером стека в реальной жизни может являться стопка тарелок: когда мы хотим вытащить тарелку, мы должны снять все тарелки выше. Вернемся к описанию операций стека:
* <tex> \mathrm {push} </tex> (запись в стек) {{---}} операция вставки нового элемента
+
* <tex> \mathtt{empty} </tex> {{---}} проверка стека на наличие в нем элементов,
* <tex> \mathrm {pop} </tex> (снятие со стека) {{---}} операция удаления нового элемента
+
* <tex> \mathtt{push} </tex> (запись в стек) {{---}} операция вставки нового элемента,
* <tex> \mathrm {empty} </tex> {{---}} проверка стека на наличие в нем элементов
+
* <tex> \mathtt{pop} </tex> (снятие со стека) {{---}} операция удаления нового элемента.
* <tex> \mathrm {size} </tex> {{---}} операция получения количества элементов в очереди
 
  
 
==Реализации==
 
==Реализации==
Строка 11: Строка 10:
 
===На массиве===
 
===На массиве===
 
Перед реализацией стека выделим ключевые поля:
 
Перед реализацией стека выделим ключевые поля:
* <tex>s [1..n]</tex> {{---}} массив, с помощью которого реализуется стек, способный вместить не более <tex>n</tex> элементов
+
* <tex>\mathtt{s[1\dots n]} </tex> {{---}} массив, с помощью которого реализуется стек, способный вместить не более <tex>n</tex> элементов,
* <tex>s.top</tex> {{---}} индекс последнего помещенного в стек элемента
+
* <tex>\mathtt{s.top}</tex> {{---}} индекс последнего помещенного в стек элемента.
  
Стек состоит из элементов <tex>s[1..s.top]</tex>, где <tex>s[1]</tex> {{---}} элемент на дне стека, а <tex>s[s.top]</tex> {{---}} элемент на его вершине.
+
Стек состоит из элементов <tex>\mathtt {s[1\dots s.top]}</tex>, где <tex>\mathtt{s[1]}</tex> {{---}} элемент на дне стека, а <tex>\mathtt{s[s.top]}</tex> {{---}} элемент на его вершине.
Если <tex>s.top = 0</tex>, то стек не содержит ни одного элемента и является пустым <tex>(empty)</tex>. Протестировать стек на наличие в нем элементов можно с помощью операции {{---}} запроса <tex> \mathrm {stackEmpty} </tex>. Если элемент снимается с пустого стека, говорят, что он опустошается <tex>(underflow)</tex>, что обычно приводит к ошибке. Если значение <tex>s.top</tex> больше <tex>n</tex>, то стек переполняется <tex>(overflow)</tex>. (В представленном ниже псевдокоде возможное переполнение во внимание не принимается.)  
+
Если <tex>\mathtt{s.top = 0}</tex>, то стек не содержит ни одного элемента и является пустым (англ. ''empty''). Протестировать стек на наличие в нем элементов можно с помощью операции {{---}} запроса <tex> \mathtt{stackEmpty} </tex>. Если элемент снимается с пустого стека, говорят, что он опустошается (англ. ''underflow''), что обычно приводит к ошибке. Если значение <tex>\mathtt{s.top}</tex> больше <tex>\mathtt{n}</tex>, то стек переполняется (англ. ''overflow''). (В представленном ниже псевдокоде возможное переполнение во внимание не принимается.)  
  
 
Каждую операцию над стеком можно легко реализовать несколькими строками кода:
 
Каждую операцию над стеком можно легко реализовать несколькими строками кода:
 
   
 
   
  '''function''' push(s, elemeent):
+
'''boolean''' empty():
 +
  '''return''' s.top == 0
 +
 
 +
  '''function''' push(element : '''T'''):
 
   s.top = s.top + 1
 
   s.top = s.top + 1
 
   s[s.top] = element
 
   s[s.top] = element
  
  '''T''' pop(s):
+
  '''T''' pop():
   '''if''' stackEmpty(s)
+
   '''if''' empty()
 
     '''return''' error "underflow"
 
     '''return''' error "underflow"
 
   '''else'''  
 
   '''else'''  
 
     s.top = s.top - 1
 
     s.top = s.top - 1
 
     '''return''' s[s.top + 1]
 
     '''return''' s[s.top + 1]
 
'''boolean''' stackEmpty(s):
 
  '''return''' s.top == 0
 
 
'''int''' size(s)
 
  '''if''' head > tail
 
    '''return''' n - head + tail
 
  '''else'''
 
    '''return''' tail - head
 
  
 
Как видно из псевдокода выше, все операции со стеком выполняются за <tex>O(1)</tex>.
 
Как видно из псевдокода выше, все операции со стеком выполняются за <tex>O(1)</tex>.
  
===На списке===
+
===На саморасширяющемся массиве===
Стек можно реализовать и на [[Список | списке]]. Для этого необходимо создать список и операции работы стека на созданном списке. Ниже представлен пример реализации стека на односвязном списке. Стек будем "держать" за голову. Добавляться новые элементы посредством операции <tex> \mathrm {push} </tex> будут перед головой, сами при этом становясь новой головой, а элементом для изъятия из стека с помощью <tex> \mathrm {pop} </tex> будет текущая голова. После вызова функции <tex> \mathrm {push} </tex> текущая голова уже станет старой и будет являться следующим элементом за добавленным, то есть ссылка на следующий элемент нового элемента будет указывать на старую голову. После вызова функции <tex> \mathrm {pop} </tex> будет получена и возвращена информация, хранящаяся в текущей голове. Сама голова будет изъята из стека, а новой головой станет элемент, который следовал за изъятой головой.
+
Возможна реализация стека на [[Саморасширяющийся_массив| динамическом массиве]], в результате чего появляется существенное преимущество над обычной реализацией: при операции push мы никогда не сможем выйти за границы массива, тем самым избежим ошибки исполнения.
  
Заведем конструктор вида <code>ListItem(ListItem next, T data)</code>
+
Создадим вектор и определим операции стека на нём. В функции <tex> \mathtt {push} </tex> Перед тем, как добавить новый элемент, будем проверять, не нужно ли расширить массив вдвое, а в <tex> \mathtt {pop} </tex>, перед тем, как изъять элемент из массива, {{---}} не нужно ли вдвое сузить размер вектора. Ниже приведён пример реализации на векторе.
  
 
Ключевые поля:
 
Ключевые поля:
* <tex>head.data</tex> {{---}} значение в верхушке стека
+
* <tex>\mathtt{s[0\dots n-1]}</tex> {{---}} старый массив, в котором хранится стек,
* <tex>head.next</tex> {{---}} значение следующее за верхушкой стека
+
* <tex>\mathtt{newStack[0\dots newSize]}</tex> {{---}} временный массив, где хранятся элементы после перекопирования,
 +
* <tex>\mathtt{head}</tex> {{---}} верхушка стека,
 +
* <tex>\mathtt{capacity}</tex> {{---}} размер массива.
  
  '''function''' push(element):
+
  '''function''' push(element : '''T'''):
   newHead = ListItem(head, element)
+
   '''if''' head == capacity - 1
   head = newHead
+
    '''T''' newStack[capacity * 2]
 +
    '''for''' i = 0 '''to''' capacity - 1
 +
      newStack[i] = s[i]
 +
    s = newStack
 +
    capacity = capacity * 2
 +
  head++
 +
   s[head] = element
  
 
  '''T''' pop():
 
  '''T''' pop():
   data = head.data
+
   temp = s[head]
   head = head.next
+
   head--
   '''return''' data
+
  '''if''' head < capacity / 4
 +
    '''T''' newStack[capacity / 2]
 +
    '''for''' i = 0 '''to''' capacity / 4 - 1
 +
      newStack[i] = s[i]
 +
    s = newStack
 +
    capacity = capacity / 2
 +
   '''return''' temp
  
В реализации на списке, кроме самих данных, хранятся указатели на следующие элементы, которых столько же, сколько и элементов, то есть, так же <tex>n</tex>. Стоит заметить, что, хотя общая оценка затрачиваемой памяти <tex>O(n)</tex>, в ней скрыта бóльшая константа из-за того, что все элементы лежат в памяти не подряд, и реализация на списке требует несколько больше памяти.
+
===На списке===
 +
Стек можно реализовать и на [[Список | списке]]. Для этого необходимо создать список и операции работы стека на созданном списке. Ниже представлен пример реализации стека на односвязном списке. Стек будем "держать" за голову. Добавляться новые элементы посредством операции <tex> \mathtt{push} </tex> будут перед головой, сами при этом становясь новой головой, а элементом для изъятия из стека с помощью <tex> \mathtt{pop} </tex> будет текущая голова. После вызова функции <tex> \mathtt{push} </tex> текущая голова уже станет старой и будет являться следующим элементом за добавленным, то есть ссылка на следующий элемент нового элемента будет указывать на старую голову. После вызова функции <tex> \mathtt{pop} </tex> будет получена и возвращена информация, хранящаяся в текущей голове. Сама голова будет изъята из стека, а новой головой станет элемент, который следовал за изъятой головой.
  
===На саморасширяющемся массиве===
+
Заведем конструктор вида <code>ListItem(next : '''ListItem''', data : '''T''')</code>
Возможна реализация стека на [[Саморасширяющийся_массив|векторе]]. Для этого нужно создать вектор и определить операции стека на нём. В функции <tex> \mathrm {push} </tex> Перед тем, как добавить новый элемент, будем проверять, не нужно ли расширить массив вдвое, а в <tex> \mathrm {pop} </tex>, перед тем, как изъять элемент из массива, {{---}} не нужно ли вдвое сузить размер вектора. Ниже приведён пример реализации на векторе.
 
  
 
Ключевые поля:
 
Ключевые поля:
* <tex>s[0..n-1]</tex> {{---}} старый массив, в котором хранится стек
+
* <tex>\mathtt{head.data}</tex> {{---}} значение в верхушке стека,
* <tex>newStack[0..newSize]</tex> {{---}} новый массив, в котором хранится стек
+
* <tex>\mathtt{head.next}</tex> {{---}} значение следующее за верхушкой стека.
* <tex>head</tex> {{---}} верхушка стека
 
* <tex>size</tex> {{---}} размер стека
 
  
  '''function''' push(element):
+
  '''function''' push(element : '''T'''):
  '''if''' head == size - 1
+
   head = ListItem(head, element)
    '''T''' newStack[size * 2]
 
    '''for''' i = 0 '''to''' size - 1
 
      newStack[i] = s[i]
 
    s = newStack
 
    size = size * 2
 
   head++
 
  s[head] = element
 
  
 
  '''T''' pop():
 
  '''T''' pop():
   temp = head
+
   data = head.data
   head--
+
   head = head.next
   '''if''' head < size / 4
+
   '''return''' data
    '''T''' newStack[size / 2]
+
 
    '''for''' i = 0 '''to''' size / 4 - 1
+
В реализации на списке, кроме самих данных, хранятся указатели на следующие элементы, которых столько же, сколько и элементов, то есть, так же <tex>\mathtt{n}</tex>. Стоит заметить, что стек требует <tex>O(n)</tex> дополнительной памяти на указатели в списке.
      newStack[i] = s[i]
 
    s = newStack
 
    size  = size / 2
 
  '''return''' s[temp]
 
  
 
== См. также ==
 
== См. также ==
Строка 95: Строка 89:
 
* [[Персистентный стек]]
 
* [[Персистентный стек]]
  
== Ссылки ==
+
== Источники информации ==
 
* [[wikipedia:ru:Стек|Википедия {{---}} Стек]]
 
* [[wikipedia:ru:Стек|Википедия {{---}} Стек]]
 
*Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10
 
*Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10

Версия 17:53, 10 июля 2019

Определение

Стек

Стек (от англ. stack — стопка) — структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Притом первым из стека удаляется элемент, который был помещен туда последним, то есть в стеке реализуется стратегия «последним вошел — первым вышел» (last-in, first-out — LIFO). Примером стека в реальной жизни может являться стопка тарелок: когда мы хотим вытащить тарелку, мы должны снять все тарелки выше. Вернемся к описанию операций стека:

  • [math] \mathtt{empty} [/math] — проверка стека на наличие в нем элементов,
  • [math] \mathtt{push} [/math] (запись в стек) — операция вставки нового элемента,
  • [math] \mathtt{pop} [/math] (снятие со стека) — операция удаления нового элемента.

Реализации

Для стека с [math]n[/math] элементами требуется [math]O(n)[/math] памяти, так как она нужна лишь для хранения самих элементов.

На массиве

Перед реализацией стека выделим ключевые поля:

  • [math]\mathtt{s[1\dots n]} [/math] — массив, с помощью которого реализуется стек, способный вместить не более [math]n[/math] элементов,
  • [math]\mathtt{s.top}[/math] — индекс последнего помещенного в стек элемента.

Стек состоит из элементов [math]\mathtt {s[1\dots s.top]}[/math], где [math]\mathtt{s[1]}[/math] — элемент на дне стека, а [math]\mathtt{s[s.top]}[/math] — элемент на его вершине. Если [math]\mathtt{s.top = 0}[/math], то стек не содержит ни одного элемента и является пустым (англ. empty). Протестировать стек на наличие в нем элементов можно с помощью операции — запроса [math] \mathtt{stackEmpty} [/math]. Если элемент снимается с пустого стека, говорят, что он опустошается (англ. underflow), что обычно приводит к ошибке. Если значение [math]\mathtt{s.top}[/math] больше [math]\mathtt{n}[/math], то стек переполняется (англ. overflow). (В представленном ниже псевдокоде возможное переполнение во внимание не принимается.)

Каждую операцию над стеком можно легко реализовать несколькими строками кода:

boolean empty():
  return s.top == 0
function push(element : T):
  s.top = s.top + 1
  s[s.top] = element
T pop():
  if empty()
    return error "underflow"
  else 
    s.top = s.top - 1
    return s[s.top + 1]

Как видно из псевдокода выше, все операции со стеком выполняются за [math]O(1)[/math].

На саморасширяющемся массиве

Возможна реализация стека на динамическом массиве, в результате чего появляется существенное преимущество над обычной реализацией: при операции push мы никогда не сможем выйти за границы массива, тем самым избежим ошибки исполнения.

Создадим вектор и определим операции стека на нём. В функции [math] \mathtt {push} [/math] Перед тем, как добавить новый элемент, будем проверять, не нужно ли расширить массив вдвое, а в [math] \mathtt {pop} [/math], перед тем, как изъять элемент из массива, — не нужно ли вдвое сузить размер вектора. Ниже приведён пример реализации на векторе.

Ключевые поля:

  • [math]\mathtt{s[0\dots n-1]}[/math] — старый массив, в котором хранится стек,
  • [math]\mathtt{newStack[0\dots newSize]}[/math] — временный массив, где хранятся элементы после перекопирования,
  • [math]\mathtt{head}[/math] — верхушка стека,
  • [math]\mathtt{capacity}[/math] — размер массива.
function push(element : T):
  if head == capacity - 1
    T newStack[capacity * 2]
    for i = 0 to capacity - 1
      newStack[i] = s[i]
    s = newStack
    capacity = capacity * 2
  head++
  s[head] = element
T pop():
  temp = s[head]
  head--
  if head < capacity / 4
    T newStack[capacity / 2]
    for i = 0 to capacity / 4 - 1
      newStack[i] = s[i]
    s = newStack
    capacity = capacity / 2
  return temp

На списке

Стек можно реализовать и на списке. Для этого необходимо создать список и операции работы стека на созданном списке. Ниже представлен пример реализации стека на односвязном списке. Стек будем "держать" за голову. Добавляться новые элементы посредством операции [math] \mathtt{push} [/math] будут перед головой, сами при этом становясь новой головой, а элементом для изъятия из стека с помощью [math] \mathtt{pop} [/math] будет текущая голова. После вызова функции [math] \mathtt{push} [/math] текущая голова уже станет старой и будет являться следующим элементом за добавленным, то есть ссылка на следующий элемент нового элемента будет указывать на старую голову. После вызова функции [math] \mathtt{pop} [/math] будет получена и возвращена информация, хранящаяся в текущей голове. Сама голова будет изъята из стека, а новой головой станет элемент, который следовал за изъятой головой.

Заведем конструктор вида ListItem(next : ListItem, data : T)

Ключевые поля:

  • [math]\mathtt{head.data}[/math] — значение в верхушке стека,
  • [math]\mathtt{head.next}[/math] — значение следующее за верхушкой стека.
function push(element : T):
  head = ListItem(head, element)
T pop():
  data = head.data
  head = head.next
  return data

В реализации на списке, кроме самих данных, хранятся указатели на следующие элементы, которых столько же, сколько и элементов, то есть, так же [math]\mathtt{n}[/math]. Стоит заметить, что стек требует [math]O(n)[/math] дополнительной памяти на указатели в списке.

См. также

Источники информации