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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Реализация на массиве)
Строка 2: Строка 2:
 
[[Файл: lifo.png|thumb|right|200px|Стек]]
 
[[Файл: lifo.png|thumb|right|200px|Стек]]
 
'''Стек''' (от англ. stack — стопка) — динамическая структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Притом первым из стека удаляется элемент, который был помещен туда последним, то есть в стеке реализуется стратегия «последним вошел — первым вышел» (last-in, first-out — LIFO). Названия операций работы со стеком являются аллюзиями к стопкам (stacks) в реальной жизни как, например, удерживаемые пружиной стопки тарелок, используемые в кафетериях, - порядок вытаскивания (pop) тарелок из стопки обратен порядку их в неё помещению (push), и лишь (текущая) верхняя тарелка может быть извлечена.
 
'''Стек''' (от англ. stack — стопка) — динамическая структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Притом первым из стека удаляется элемент, который был помещен туда последним, то есть в стеке реализуется стратегия «последним вошел — первым вышел» (last-in, first-out — LIFO). Названия операций работы со стеком являются аллюзиями к стопкам (stacks) в реальной жизни как, например, удерживаемые пружиной стопки тарелок, используемые в кафетериях, - порядок вытаскивания (pop) тарелок из стопки обратен порядку их в неё помещению (push), и лишь (текущая) верхняя тарелка может быть извлечена.
 
+
==Реализации==
==Реализация на массиве==
+
===На массиве===
 
<wikitex>Операция вставки нового элемента применительно к стекам часто называется $push$ (запись в стек), а операция удаления — $pop$ (снятие со стека). Стек, способный вместить не более $n$ элементов, можно реализовать с помощью массива $S [1..n]$. Этот массив обладает атрибутом $S.top$, представляющим собой индекс последнего помещенного в стек элемента. Стек состоит из элементов $S[1..S.top]$, где $S[1]$ — элемент на дне стека, а $S[S.top]$ — элемент на его вершине.  
 
<wikitex>Операция вставки нового элемента применительно к стекам часто называется $push$ (запись в стек), а операция удаления — $pop$ (снятие со стека). Стек, способный вместить не более $n$ элементов, можно реализовать с помощью массива $S [1..n]$. Этот массив обладает атрибутом $S.top$, представляющим собой индекс последнего помещенного в стек элемента. Стек состоит из элементов $S[1..S.top]$, где $S[1]$ — элемент на дне стека, а $S[S.top]$ — элемент на его вершине.  
  
Строка 29: Строка 29:
 
Как видно из псевдокода выше, все операции со стеком выполняются за $O(1)$. Память требуется только для хранения самих элементов, т.е. необходимо $O(n)$ памяти.</wikitex>
 
Как видно из псевдокода выше, все операции со стеком выполняются за $O(1)$. Память требуется только для хранения самих элементов, т.е. необходимо $O(n)$ памяти.</wikitex>
  
==Реализация на списке==
+
===На списке===
 
<wikitex>Стек можно реализовать и на списке. Для этого необходимо создать список и операции работы стека на созданном списке. Ниже представлен пример реализации стека на односвязном списке. Стек будем "держать" за голову. Добавляться новые элементы посредством операции $push$ будут перед головой, сами при этом становясь новой головой, а элементом для изъятия из стека с помощью $pop$ будет текущая голова. После вызова функции $push$ текущая голова уже станет старой и будет являться следующим элементом за добавленным, то есть ссылка на следующий элемент нового элемента будет указывать на старую голову. После вызова функции $pop$ будет получена и возвращена информация, хранящаяся в текущей голове. Сама голова будет изъята из стека, а новой головой станет элемент, который следовал за изъятой головой.
 
<wikitex>Стек можно реализовать и на списке. Для этого необходимо создать список и операции работы стека на созданном списке. Ниже представлен пример реализации стека на односвязном списке. Стек будем "держать" за голову. Добавляться новые элементы посредством операции $push$ будут перед головой, сами при этом становясь новой головой, а элементом для изъятия из стека с помощью $pop$ будет текущая голова. После вызова функции $push$ текущая голова уже станет старой и будет являться следующим элементом за добавленным, то есть ссылка на следующий элемент нового элемента будет указывать на старую голову. После вызова функции $pop$ будет получена и возвращена информация, хранящаяся в текущей голове. Сама голова будет изъята из стека, а новой головой станет элемент, который следовал за изъятой головой.
  
 
  struct ListItem
 
  struct ListItem
{
+
     int data
     int data;
+
     ListItem* next
     ListItem* next;
 
 
     ListItem()
 
     ListItem()
    {
+
         data = -1
         data = -1;
+
         next = NULL
         next = NULL;
 
    }
 
};
 
 
  struct Stack
 
  struct Stack
{
+
     ListItem* head
     ListItem* head;
 
 
     Stack()
 
     Stack()
    {
+
         head = new ListItem()
         head = new ListItem();
 
    }
 
 
     void push(int element)
 
     void push(int element)
    {
+
         ListItem* NewHead = new ListItem()
         ListItem* NewHead = new ListItem();
+
         ListItem* OldHead = new ListItem()
         ListItem* OldHead = new ListItem();
 
 
         OldHead = head;
 
         OldHead = head;
         NewHead->data = element;
+
         NewHead->data = element
         NewHead->next = OldHead;
+
         NewHead->next = OldHead
 
         head = NewHead;
 
         head = NewHead;
     }
+
     pop()
    int pop()
+
         int element = head->data
    {
+
         head = head->next
         int element = head->data;
+
         return element
         head = head->next;
+
</wikitex>
         return element;
+
 
     }
+
===На саморасширяющемся массиве===
  };</wikitex>
+
<wikitex>Возможна реализация стека на [[Саморасширяющийся_массив|векторе]]. Для этого нужно создать вектор и определить операции стека на нём. В функции $push$ Перед тем, как добавить новый элемент, будем проверять, не нужно ли расширить массив вдвое, а в $pop$, перед тем, как изъять элемент из массива, - не нужно ли вдвое сузить размер вектора. Ниже приведён пример реализации на векторе.
 +
 
 +
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>
  
 
== См. также ==
 
== См. также ==

Версия 18:07, 11 июня 2012

Определение

Стек

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

Реализации

На массиве

<wikitex>Операция вставки нового элемента применительно к стекам часто называется $push$ (запись в стек), а операция удаления — $pop$ (снятие со стека). Стек, способный вместить не более $n$ элементов, можно реализовать с помощью массива $S [1..n]$. Этот массив обладает атрибутом $S.top$, представляющим собой индекс последнего помещенного в стек элемента. Стек состоит из элементов $S[1..S.top]$, где $S[1]$ — элемент на дне стека, а $S[S.top]$ — элемент на его вершине.

Если $S.top = 0$, то стек не содержит ни одного элемента и является пустым $(empty)$. Протестировать стек на наличие в нем элементов можно с помощью операции-запроса $Stack$_$Empty$. Если элемент снимается с пустого стека, говорят, что он опустошается $(underflow)$, что обычно приводит к ошибке. Если значение $S.top$ больше $n$, то стек переполняется $(overflow)$. (В представленном ниже псевдокоде возможное переполнение во внимание не принимается.)

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

Stack_Empty(S)
    if S.top == 0
        return true
    else
        return false

push(S,x)
    S.top = S.top + 1
    S[S.top] = x

pop(S)
    if Stack_Empty(S)
        return error "underflow"
    else 
        S.top = S.top - 1
        return S[S.top + 1]

Как видно из псевдокода выше, все операции со стеком выполняются за $O(1)$. Память требуется только для хранения самих элементов, т.е. необходимо $O(n)$ памяти.</wikitex>

На списке

<wikitex>Стек можно реализовать и на списке. Для этого необходимо создать список и операции работы стека на созданном списке. Ниже представлен пример реализации стека на односвязном списке. Стек будем "держать" за голову. Добавляться новые элементы посредством операции $push$ будут перед головой, сами при этом становясь новой головой, а элементом для изъятия из стека с помощью $pop$ будет текущая голова. После вызова функции $push$ текущая голова уже станет старой и будет являться следующим элементом за добавленным, то есть ссылка на следующий элемент нового элемента будет указывать на старую голову. После вызова функции $pop$ будет получена и возвращена информация, хранящаяся в текущей голове. Сама голова будет изъята из стека, а новой головой станет элемент, который следовал за изъятой головой.

struct ListItem
    int data
    ListItem* next
    ListItem()
        data = -1
        next = NULL
struct Stack
    ListItem* head
    Stack()
        head = new ListItem()
    void push(int element)
        ListItem* NewHead = new ListItem()
        ListItem* OldHead = new ListItem()
        OldHead = head;
        NewHead->data = element
        NewHead->next = OldHead
        head = NewHead;
    pop()
        int element = head->data
        head = head->next
        return element

</wikitex>

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

<wikitex>Возможна реализация стека на векторе. Для этого нужно создать вектор и определить операции стека на нём. В функции $push$ Перед тем, как добавить новый элемент, будем проверять, не нужно ли расширить массив вдвое, а в $pop$, перед тем, как изъять элемент из массива, - не нужно ли вдвое сузить размер вектора. Ниже приведён пример реализации на векторе.

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>

См. также

Ссылки