Введение в стек — учебные пособия по структуре данных и алгоритмам

Куча

Это линейная структура данных, которая следует определенному порядку выполнения операций.

ЛИФО (последним пришел первым ушел):

This strategy states that the element that is inserted last will come out first. You can take a pile of plates kept on top of each other as a real-life example. The plate which we put last is on the top and since we remove the plate that is at the top, we can say that the plate that was put last comes out first.

Основные операции со стеком

Для того, чтобы производить манипуляции в стеке, нам предусмотрены определенные операции.

• push() для вставки элемента в стек
• pop() для удаления элемента из стека
• top() Возвращает верхний элемент стека.
• isEmpty() возвращает true, если стек пуст, иначе false.
• size() возвращает размер стека.

Толкать:

Добавляет элемент в стек. Если стек заполнен, говорят, что это состояние переполнения.

Алгоритм отжима:

begin
 if stack is full
    return
 endif
else  
 increment top
 stack[top] assign value
end else
end procedure

Поп:

Удаляет элемент из стека. Элементы извлекаются в порядке, обратном их перемещению. Если стек пуст, говорят, что это состояние Underflow.

Алгоритм поп:

begin
 if stack is empty
    return
 endif
else
 store value of stack[top]
 decrement top
 return value
end else
end procedure

Верхний:

Возвращает верхний элемент стека.

Алгоритм для топа:

begin 
  return stack[top]
end procedure

пустой:

Возвращает true, если стек пуст, иначе false.

Алгоритм для isEmpty :

begin
 if top < 1
    return true
 else
    return false
end procedure

Понимание стека практически:

There are many real-life examples of a stack. Consider the simple example of plates stacked over one another in a canteen. The plate which is at the top is the first one to be removed, i.e. the plate which has been placed at the bottommost position remains in the stack for the longest period of time. So, it can be simply seen to follow the LIFO/FILO order.

Анализ сложности:

• Сложность времени

Типы стеков:

• Стек регистров: этот тип стека также является элементом памяти, присутствующим в блоке памяти, и может обрабатывать только небольшой объем данных. Высота стека регистров всегда ограничена, так как размер стека регистров очень мал по сравнению с памятью.
• Стек памяти: этот тип стека может обрабатывать большой объем данных памяти. Высота стека памяти является гибкой, поскольку он занимает большой объем данных памяти.

Приложения стека:

• Преобразование инфикса в постфикс/префикс
• Функции повтора-отмены во многих местах, таких как редакторы, фотошоп.
• Вперед и назад функции в веб-браузерах
• Используется во многих алгоритмах, таких как Ханойская башня, обход дерева, задачи с запасами и задачи с гистограммами.
• Возврат является одним из методов разработки алгоритмов. Некоторыми примерами возврата являются задача коня-тур, задача N-ферзя, поиск пути через лабиринт и игровые шахматы или шашки во всех этих задачах, в которые мы каким-то образом погружаемся, если этот способ неэффективен, мы возвращаемся к предыдущему состояние и пойти по какому-то другому пути. Чтобы вернуться из текущего состояния, нам нужно сохранить предыдущее состояние, для этого нам нужен стек.
• В графических алгоритмах, таких как топологическая сортировка и сильно связанные компоненты
• В управлении памятью любой современный компьютер использует стек в качестве основного средства управления для текущих целей. Каждая программа, работающая в компьютерной системе, имеет собственное распределение памяти.
• Обращение строк также является еще одним применением стека. Здесь один за другим каждый символ вставляется в стек. Таким образом, первый символ строки находится в нижней части стека, а последний элемент строки — в верхней части стека. После выполнения операций извлечения из стека мы получаем строку в обратном порядке.
• Стек также помогает в реализации вызова функций на компьютерах. Последняя вызванная функция всегда завершается первой.
• Стеки также используются для реализации операции отмены/повтора в текстовом редакторе.

Реализация стека:

Есть два способа реализовать стек

• Использование массива
• Использование связанного списка

Реализация стека с использованием массивов:

Преимущества реализации массива:

• Легко реализовать.
• Память экономится, так как указатели не задействованы.

Недостатки реализации массива:

• Он не является динамическим, т. е. не увеличивается и не уменьшается в зависимости от потребностей во время выполнения. [Но в случае массивов с динамическим размером, таких как вектор в C++, список в Python, ArrayList в Java, стеки также могут увеличиваться и уменьшаться при реализации массива].
• Общий размер стека должен быть определен заранее.

Реализация стека с использованием связанного списка:

Преимущества реализации Linked List:

• Реализация связанного списка стека может увеличиваться и уменьшаться в соответствии с потребностями во время выполнения.
• Он используется во многих виртуальных машинах, таких как JVM.

Недостатки реализации связанного списка:

• Требует дополнительной памяти из-за участия указателей.
• Случайный доступ в стеке невозможен.

Статьи по Теме:

• Реализовать стек, используя односвязный список
• Приложения, преимущества и недостатки стека