Стек - это не что иное, как линейная структура данных, в которой вставка и удаление происходят только на одном конце. Операция вставки имеет специальное имя, известное как PUSH, а операция удаления также имеет особое имя, известное как POP. PUSH и POP - это две основные операции, которые могут выполняться только в определенном стеке. Это группа ячеек памяти, и эти ячейки связаны либо с памятью чтения, либо с памятью записи. Это используется для хранения двоичной информации во время выполнения программы, когда мы выполняем любую программу, содержимое этой программы будет сохранено в стеке. Следует Последний вошел - первым вышел (LIFO), и он используется только для хранения и извлечения данных, но не используется для хранения данных. Краткое объяснение стека / указателя стека обсуждается ниже.
Что такое стек / указатель стека?
Определение: Стек - это запоминающее устройство, используемое для хранения информации или данных в режиме LIFO (Last In First Out). Каждый раз, когда мы вводим данные в форме LIFO, элемент, который должен быть удален первым, является последним элементом вставки, поэтому последний вставленный элемент удаляется первым. Это блок памяти в адресном регистре, называемый указателем стека (SP). Указатель стека всегда указывает верхний элемент стека, что означает, в какое место должны быть вставлены данные.
Типы стека
Есть два типа стеков: стек регистров и стек памяти.
Зарегистрируйте стек
Стек регистров также представляет собой запоминающее устройство, присутствующее в блоке памяти, но обрабатывает лишь небольшой объем данных. Глубина стека всегда ограничена в стеке регистров, поскольку размер стека регистров очень мал по сравнению с размером памяти.
Отправка операции в стек регистров
Шаг 1: Указатель стека увеличивается на 1.
SP ← SP + 1
Шаг 2: Введите данные в стек.
1000 [SP] ← CT
Где DR - регистр данных
Шаг 3: Проверить, заполнен ли стек или нет
если (sp = 0) then (полное ← 1)
Шаг 4: Отметить как не пустое
пусто ← 0
Поп-операция в стеке регистров
Шаг 1: Прочитать данные из стека.
DR ← M [SP]
Шаг 2: Уменьшить точку стека.
СП ← СП-1
Шаг 3: Проверить, пуста ли стопка
если sp = 0, то пусто ← 1
Структура стека 64-битных регистров показана на рисунке ниже.
Регистрация организации стека
Стек памяти
В стеке памяти глубина стека является гибкой. Он занимает большой объем данных в памяти, тогда как в стеке регистров будет храниться только конечное количество слов памяти.
Отправка операции в стек памяти
Шаг 1: СП ← СП-1
Шаг 2: 1000 [SP] ← CT
Всплывающая операция в стеке памяти
Шаг 1: DR ← M [SP]
Шаг 2: СП ← СП-1
По сравнению с блоком регистров, блок памяти хранит большой объем данных. Рисунок стека памяти показан на рисунке ниже.
Стек памяти
Общий блок памяти разделен на три части: первый блок памяти содержит программу (ничего, кроме инструкций), вторая часть - данные (операнды), а третья часть - стек. Программные инструкции всегда сохраняются в счетчике программ (ПК), регистры данных идентифицируются адресным регистром (AR). Адреса от 3000 до 4001, используемые для стека, и первый элемент или элемент хранятся в 4001.
Указатель стека / стека в микропроцессоре 8085
Взгляд программиста на 8085 микропроцессор содержит регистры общего назначения и специальные регистры . Регистры общего назначения - это A, B, C, D, E, H, L, а регистры специального назначения - это SP (указатель стека) и PC (счетчик программ). Вид программатора микропроцессора 8085 показан на рисунке ниже.
Программист: взгляд на 8085
Указатель стека - это 16-битный регистр, содержащий адрес памяти, предположим, что содержимое указателя стека (SP) - это FC78H, тогда микропроцессор 8085 интерпретирует его. Ячейки памяти содержат полезную информацию от FC78H до FFFH и от FC77H до 0000H, ячейки памяти не содержат полезной информации. Интерпретация указателя стека показана на рисунке ниже.
Интерпретация указателя стека
Основные операции стека / указателя стека
В стеке есть две операции: операция PUSH и операция POP.
PUSH Операция
PUSH означает выталкивание или вставку элемента в стек. Операция PUSH всегда увеличивает указатель стека, а операция POP всегда уменьшает указатель стека. В случае операции push мы должны проверить, доступно ли свободное место или нет. Если свободное пространство доступно, мы можем перейти к операции push, если свободное пространство недоступно, появляется сообщение об ошибке, которое является переполнением. Переполнение должно проверяться соответственно в случае нажатия. Базовая операция нажатия и выталкивания показана на рисунке ниже.
Основные операции PUSH и POP
Рисунок (а) - стопка. Если вы хотите протолкнуть элемент, который вставляет элемент в стек, вы должны нажать (s, a), где «s» не что иное, как стек. В стек мы помещаем элемент «a», и эта операция показана на рисунке (b). Смотрите рисунок (3), предположим, что стек содержит три элемента a, b, c, и стек заполнен элементом.
Если вы хотите вставить четвертый элемент-‘d ’с помощью push (s, d), но нет места для вставки элемента, это означает, что стек переполнен. Терминология переполнения используется, когда стек заполнен, а алгоритм операции push показан ниже.
push (стек [], верх, макс. стек, элемент)
если (сверху == maxstack-1)
{
напечатать «переполнение»
}
еще
{
верх = верх + 1
стек [вверху] = элемент
}
конец
POP Operation
POP означает удаление элемента в верхней части стека. В случае операции pop мы должны проверить, является ли стек изначально пустым или нет. Если стек изначально пуст, возникает ситуация потери значимости. Предположим, что стек пуст, но вы хотите вставить элементы в стек, но в нем нет элементов, тогда это приведет к переполнению стека.
В случае срабатывания всплывающего окна необходимо проверить отсутствие значимости. В операции выталкивания, какой бы верхний элемент ни присутствовал в стеке, который должен быть извлечен или удален, поэтому не нужно указывать, какой элемент будет извлечен, по умолчанию будет извлечен самый верхний элемент. Алгоритм работы pop показан ниже.
поп (стек [], верх, элемент)
если (вверху == - 1)
{
напечатать «недополнение»
}
еще
{
item = stack [вверху]
top = top-1
}
Пример
Элементы вставляются в порядке A, B, C, D, E, он представляет собой стек из пяти элементов. На рисунке (a) мы хотим поместить элемент A в стек, тогда вершина становится нулевой (top = 0), аналогично top = 1, когда выталкивается элемент B, top = 2, когда элемент C нажимается, top = 3, когда нажимается элемент 'D', и top = 4, когда нажимается элемент 'E'.
Итак, все элементы, которые я взял, помещаются в стек, теперь стек заполнен. Если вы хотите протолкнуть другой элемент, в стеке нет места, поэтому это указывает на переполнение. Теперь стек заполнен, если вы хотите вытолкнуть элемент «E», сначала нужно удалить элемент. Операция выталкивания показана на рисунке ниже.
Нажать операцию
Мы должны использовать операцию pop для удаления элементов в стеке. Так что просто упомяните, что pop () не записывает аргументы в pop, потому что по умолчанию он удаляет верхний элемент. Первый элемент «E» удаляется, следующий элемент «D» ... »A». Когда удаляются верхние элементы, верхнее значение уменьшается. Когда top = -1, стек указывает на недостаточное количество. Операция pop показана на рисунке ниже.
POP Operation
Итак, это объяснение того, как элементы вставляются и удаляются в стеке с помощью операций push и pop.
Приложения
Применение указателя стека / стека:
- Переворот строки
- Сбалансированная скобка
- UNDO / FINGER
- Системный стек для записей активации
- Инфикс, префикс, постфикс, выражение
FAQs
1). Что такое указатель стека в руке?
Регистр указателя стека (R13) используется в качестве указателя на активный стек в ARM.
2). Почему указатель стека 16-битный?
Указатель стека (SP) и счетчик программ (PC), используемые для хранения предыдущего местоположения, и адрес ячейки памяти составляют 16 бит, поэтому указатель стека (SP) также имеет 16 бит.
3). Какова роль указателя стека?
Роль указателя стека (SP) состоит в том, чтобы указать вершину элемента в стеке.
4). Какой стек используется в 8085?
Стек, используемый в 8085, является последним вошел - первым ушел (LIFO).
5). Указатель стека - это регистр?
Да, указатель стека (SP) - это адресный регистр, который всегда указывает вершину элемента в стеке.
