Редактирование: Стек

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
== Определение ==
 
== Определение ==
 
[[Файл: lifo.png|thumb|right|200px|Стек]]
 
[[Файл: lifo.png|thumb|right|200px|Стек]]
'''Стек''' (от англ. ''stack'' {{---}} стопка) {{---}} структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Притом первым из стека удаляется элемент, который был помещен туда последним, то есть в стеке реализуется стратегия «последним вошел {{---}} первым вышел» (last-in, first-out {{---}} LIFO). Примером стека в реальной жизни может являться стопка тарелок: когда мы хотим вытащить тарелку, мы должны снять все тарелки выше. Вернемся к описанию операций стека:
+
'''Стек''' (от англ. stack стопка) структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Притом первым из стека удаляется элемент, который был помещен туда последним, то есть в стеке реализуется стратегия «последним вошел первым вышел» (last-in, first-out LIFO). Названия операций работы со стеком являются аллюзиями к стопкам (stacks) в реальной жизни как, например, удерживаемые пружиной стопки тарелок, используемые в кафетериях, - порядок вытаскивания (pop) тарелок из стопки обратен порядку их в неё помещению (push), и лишь (текущая) верхняя тарелка может быть извлечена.
* <tex> \mathtt{empty} </tex> {{---}} проверка стека на наличие в нем элементов,
 
* <tex> \mathtt{push} </tex> (запись в стек) {{---}} операция вставки нового элемента,
 
* <tex> \mathtt{pop} </tex> (снятие со стека) {{---}} операция удаления нового элемента.
 
  
 
==Реализации==
 
==Реализации==
Для стека с <tex>n</tex> элементами требуется <tex>O(n)</tex> памяти, так как она нужна лишь для хранения самих элементов.
+
<wikitex>Для стека с $n$ элементами требуется $O(n)$ памяти, так как она нужна лишь для хранения самих элементов.</wikitex>
 
===На массиве===
 
===На массиве===
Перед реализацией стека выделим ключевые поля:
+
<wikitex>Операция вставки нового элемента применительно к стекам часто называется $push$ (запись в стек), а операция удаления — $pop$ (снятие со стека). Стек, способный вместить не более $n$ элементов, можно реализовать с помощью массива $S [1..n]$. Этот массив обладает атрибутом $S.top$, представляющим собой индекс последнего помещенного в стек элемента. Стек состоит из элементов $S[1..S.top]$, где $S[1]$ — элемент на дне стека, а $S[S.top]$ — элемент на его вершине.  
* <tex>\mathtt{s[1\dots n]} </tex> {{---}} массив, с помощью которого реализуется стек, способный вместить не более <tex>n</tex> элементов,
 
* <tex>\mathtt{s.top}</tex> {{---}} индекс последнего помещенного в стек элемента.
 
  
Стек состоит из элементов <tex>\mathtt {s[1\dots s.top]}</tex>, где <tex>\mathtt{s[1]}</tex> {{---}} элемент на дне стека, а <tex>\mathtt{s[s.top]}</tex> {{---}} элемент на его вершине.
+
Если $S.top = 0$, то стек не содержит ни одного элемента и является пустым $(empty)$. Протестировать стек на наличие в нем элементов можно с помощью операции-запроса $Stack$_$Empty$. Если элемент снимается с пустого стека, говорят, что он опустошается $(underflow)$, что обычно приводит к ошибке. Если значение $S.top$ больше $n$, то стек переполняется $(overflow)$. (В представленном ниже псевдокоде возможное переполнение во внимание не принимается.)  
Если <tex>\mathtt{s.top = 0}</tex>, то стек не содержит ни одного элемента и является пустым (англ. ''empty''). Протестировать стек на наличие в нем элементов можно с помощью операции {{---}} запроса <tex> \mathtt{stackEmpty} </tex>. Если элемент снимается с пустого стека, говорят, что он опустошается (англ. ''underflow''), что обычно приводит к ошибке. Если значение <tex>\mathtt{s.top}</tex> больше <tex>\mathtt{n}</tex>, то стек переполняется (англ. ''overflow''). (В представленном ниже псевдокоде возможное переполнение во внимание не принимается.)  
 
  
 
Каждую операцию над стеком можно легко реализовать несколькими строками кода:
 
Каждую операцию над стеком можно легко реализовать несколькими строками кода:
 +
 +
Stack_Empty(S)
 +
    if S.top == 0
 +
        return true
 +
    else
 +
        return false
 
   
 
   
  '''boolean''' empty():
+
  push(S,x)
  '''return''' s.top == 0
+
    S.top = S.top + 1
 
+
    S[S.top] = x
'''function''' push(element : '''T'''):
+
  s.top = s.top + 1
+
  pop(S)
  s[s.top] = element
+
    if Stack_Empty(S)
 
+
        return error "underflow"
  '''T''' pop():
+
    else  
  '''if''' empty()
+
        S.top = S.top - 1
    '''return''' error "underflow"
+
        return S[S.top + 1]
  '''else'''
 
    s.top = s.top - 1
 
    '''return''' s[s.top + 1]
 
  
Как видно из псевдокода выше, все операции со стеком выполняются за <tex>O(1)</tex>.
+
Как видно из псевдокода выше, все операции со стеком выполняются за $O(1)$.</wikitex>
 
 
===На саморасширяющемся массиве===
 
Возможна реализация стека на [[Саморасширяющийся_массив| динамическом массиве]], в результате чего появляется существенное преимущество над обычной реализацией: при операции push мы никогда не сможем выйти за границы массива, тем самым избежим ошибки исполнения.
 
 
 
Создадим вектор и определим операции стека на нём. В функции <tex> \mathtt {push} </tex> Перед тем, как добавить новый элемент, будем проверять, не нужно ли расширить массив вдвое, а в <tex> \mathtt {pop} </tex>, перед тем, как изъять элемент из массива, {{---}} не нужно ли вдвое сузить размер вектора. Ниже приведён пример реализации на векторе.
 
 
 
Ключевые поля:
 
* <tex>\mathtt{s[0\dots n-1]}</tex> {{---}} старый массив, в котором хранится стек,
 
* <tex>\mathtt{newStack[0\dots newSize]}</tex> {{---}} временный массив, где хранятся элементы после перекопирования,
 
* <tex>\mathtt{head}</tex> {{---}} верхушка стека,
 
* <tex>\mathtt{capacity}</tex> {{---}} размер массива.
 
 
 
'''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
 
  
 
===На списке===
 
===На списке===
Стек можно реализовать и на [[Список | списке]]. Для этого необходимо создать список и операции работы стека на созданном списке. Ниже представлен пример реализации стека на односвязном списке. Стек будем "держать" за голову. Добавляться новые элементы посредством операции <tex> \mathtt{push} </tex> будут перед головой, сами при этом становясь новой головой, а элементом для изъятия из стека с помощью <tex> \mathtt{pop} </tex> будет текущая голова. После вызова функции <tex> \mathtt{push} </tex> текущая голова уже станет старой и будет являться следующим элементом за добавленным, то есть ссылка на следующий элемент нового элемента будет указывать на старую голову. После вызова функции <tex> \mathtt{pop} </tex> будет получена и возвращена информация, хранящаяся в текущей голове. Сама голова будет изъята из стека, а новой головой станет элемент, который следовал за изъятой головой.
+
<wikitex>Стек можно реализовать и на списке. Для этого необходимо создать список и операции работы стека на созданном списке. Ниже представлен пример реализации стека на односвязном списке. Стек будем "держать" за голову. Добавляться новые элементы посредством операции $push$ будут перед головой, сами при этом становясь новой головой, а элементом для изъятия из стека с помощью $pop$ будет текущая голова. После вызова функции $push$ текущая голова уже станет старой и будет являться следующим элементом за добавленным, то есть ссылка на следующий элемент нового элемента будет указывать на старую голову. После вызова функции $pop$ будет получена и возвращена информация, хранящаяся в текущей голове. Сама голова будет изъята из стека, а новой головой станет элемент, который следовал за изъятой головой.
  
Заведем конструктор вида <code>ListItem(next : '''ListItem''', data : '''T''')</code>
+
push(element)
 +
    OldHead = head
 +
    NewHead.data = element
 +
    NewHead.next = OldHead
 +
    head = NewHead
  
Ключевые поля:
+
pop()
* <tex>\mathtt{head.data}</tex> {{---}} значение в верхушке стека,
+
    int element = head.data
* <tex>\mathtt{head.next}</tex> {{---}} значение следующее за верхушкой стека.
+
    head = head.next
 +
    return element
  
'''function''' push(element : '''T'''):
+
В реализации на списке, кроме самих данных, хранятся указатели на следующие элементы, которых столько же, сколько и элементов.
  head = ListItem(head, element)
+
</wikitex>
  
'''T''' pop():
+
===На саморасширяющемся массиве===
  data = head.data
+
<wikitex>Возможна реализация стека на [[Саморасширяющийся_массив|векторе]]. Для этого нужно создать вектор и определить операции стека на нём. В функции $push$ Перед тем, как добавить новый элемент, будем проверять, не нужно ли расширить массив вдвое, а в $pop$, перед тем, как изъять элемент из массива, — не нужно ли вдвое сузить размер вектора. Ниже приведён пример реализации на векторе.
  head = head.next
 
  '''return''' data
 
  
В реализации на списке, кроме самих данных, хранятся указатели на следующие элементы, которых столько же, сколько и элементов, то есть, так же <tex>\mathtt{n}</tex>. Стоит заметить, что стек требует <tex>O(n)</tex> дополнительной памяти на указатели в списке.
+
struct vector
 +
    int size, n
 +
    int* v
 +
    int* w
 +
    vector()
 +
        size = 1
 +
        n = 0
 +
        v = new int[1]
 +
    pop()
 +
        int r = *(v + n)
 +
        n--
 +
        if (n < size / 4)
 +
            w = new int[size  / 2]
 +
            for i = 0..size  / 4
 +
                w[i] = v[i]
 +
            delete[] v
 +
            v = w
 +
            size  = size  / 2
 +
            return r
 +
    push(e)
 +
        if (n == s - 1)
 +
            w = new int[s * 2]
 +
            for i = 0..s
 +
                w[i] = v[i]
 +
            delete[] v
 +
            v = w
 +
            s = s * 2
 +
        n++
 +
        v[n] = e
 +
</wikitex>
  
 
== См. также ==
 
== См. также ==
 +
* [[Список]]
 
* [[Очередь]]
 
* [[Очередь]]
 
* [[Персистентный стек]]
 
* [[Персистентный стек]]
  
== Источники информации ==
+
== Ссылки ==
* [[wikipedia:ru:Стек|Википедия {{---}} Стек]]
+
*Википедия
 +
**[http://ru.wikipedia.org/wiki/Стек Стек]
 
*Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10
 
*Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 10
 
*T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 10.1
 
*T. H. Cormen. «Introduction to Algorithms» third edition, Chapter 10.1

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

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

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

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