Основные принципы программирования: стек и куча. Стек: что это такое и применение

Память, которую используют программы, состоит из нескольких частей — сегментов :

сегмент кода (или «текстовый сегмент»), где находится скомпилированная программа. Сегмент кода обычно доступен только для чтения;

сегмент bss (или «неинициализированный сегмент данных»), где хранятся глобальные и , инициализированные нулем;

сегмент данных (или «сегмент инициализированных данных»), где хранятся инициализированные глобальные и статические переменные;

к уча (heap), откуда выделяются динамические переменные;

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

В этом уроке мы рассмотрим только кучу и стек, поскольку всё самое интересное происходит именно там.

Куча

Сегмент кучи (или просто «куча ») отслеживает память, используемую для динамического выделения. Мы уже немного поговорили о куче в .

В C++, при использовании оператора new для выделения динамической памяти, эта память выделяется в сегменте кучи самого приложения.

int *ptr = new int; // ptr выделяется 4 байта из кучи int *array = new int; // array выделяется 40 байтов из кучи

Адрес выделяемой памяти передается обратно оператором new и затем он может быть сохранен в . О механизме хранения и выделения свободной памяти нам сейчас беспокоиться не за чем. Однако стоит знать, что последовательные запросы памяти не всегда приводят к выделению последовательных адресов памяти!

int *ptr1 = new int; int *ptr2 = new int; // ptr1 и ptr2 могут не иметь последовательных адресов

При удалении динамически выделенной переменной, память возвращается обратно в кучу и затем может быть переназначена (исходя из последующих запросов). Помните, что удаление указателя не удаляет переменную, это просто приводит к возврату памяти по этому адресу обратно в операционную систему.

Куча имеет свои преимущества и недостатки:

Выделение памяти в куче сравнительно медленное.

Выделенная память остается выделенной до тех пор, пока не будет освобождена (остерегайтесь утечек памяти) или пока приложение не завершит своё выполнение (в этот момент ОС должна вернуть память обратно).

Доступ к динамически выделенной памяти осуществляется только через указатель. Разыменование указателя происходит медленнее, чем доступ к переменной напрямую.

Поскольку куча представляет собой большой резервуар памяти, то именно она используется для выделения больших , или классов.

Стек вызовов

Стек вызовов (или просто «стек ») имеет гораздо более интересную роль. Стек вызовов отслеживает все активные функции (те, которые были вызваны, но еще не завершены) от начала программы и до текущей точки выполнения, и обрабатывает выделение всех параметров функции и локальных переменных.

Стек вызовов реализуется как структура данных «Стек». Поэтому, прежде чем мы поговорим о том, как работает стек вызовов, нам нужно понять, что такое «Стек» как структура данных.

Структура данных «Стек»

Структура данных - это механизм в программировании для организации данных, чтобы они могли эффективно использоваться. Вы уже видели несколько типов структур данных, таких как массивы и структуры. Они обеспечивают механизмы для эффективного хранения данных и доступа к ним. Существует еще много дополнительных структур данных, которые обычно используются в программировании, некоторые из которых реализованы в стандартной библиотеке C++, и «Стек» является одним из таких.

Рассмотрим стопку (стек) тарелок на столе. Поскольку каждая тарелка тяжелая и они сложены (друг на друге), то вы можете сделать только одну из следующих трех вещей:

Посмотреть на поверхность верхней тарелки.

Взять верхнюю тарелку из стопки (открывая таким образом следующую, которая находится снизу – если она вообще есть).

Положить новую тарелку поверх стопки (спрятав под ней самую верхнюю тарелку — если она была).

В компьютерном программировании стек представляет собой контейнер, как структуру данных, который содержит несколько переменных (подобно массиву). Однако, в то время как массив позволяет получить доступ и изменять элементы в любом порядке (так называемый «произвольный доступ »), то стек более ограничен. Операции, которые могут выполняться в стеке, соответствуют трем перечисленным выше. В стеке вы можете :

Посмотреть на верхний элемент в стеке (используется функция top () или peek () ).

Вытянуть верхний элемент стека (используется функция pop () ).

Добавить новый элемент на вершину стека (используется функция push () ).

Стек – это структура типа LIFO (Last In, First Out – последним пришёл, первым ушёл). Последний элемент, помещенный на вершину стека, будет первым, который и выйдет из стека. Если вы положите новую тарелку поверх стопки других тарелок, то она будет первой, которую вы потом возьмете. По мере того, как элементы помещаются в стек — стек растет, по мере того, как элементы удаляются со стека – стек уменьшается.

Например, рассмотрим короткую последовательность, показывающую, как работает добавление и удаление в стеке:

Stack: empty
Push 1
Stack: 1
Push 2
Stack: 1 2
Push 3
Stack: 1 2 3
Push 4
Stack: 1 2 3 4
Pop
Stack: 1 2 3
Pop
Stack: 1 2
Pop
Stack: 1

Стопка тарелок – довольно-таки хорошая аналогия работы стека, но есть аналогия и получше. Например, рассмотрим несколько почтовых ящиков, которые расположены друг на друге. Каждый почтовый ящик может содержать только один элемент, и все почтовые ящики изначально пустые. Кроме того, каждый почтовый ящик прибивается гвоздем к почтовому ящику снизу, поэтому количество почтовых ящиков не может быть изменено. Если мы не можем изменить количество почтовых ящиков, то как мы получим поведение, подобное стеку?

Во-первых, мы используем наклейку для обозначения того, где находится самый нижний пустой почтовый ящик. В начале это будет первый почтовый ящик, который находится на полу. Когда мы добавим элемент в наш стек почтовых ящиков, то мы поместим этот элемент в почтовый ящик, на котором будет наклейка (т.е. в самый первый пустой почтовый ящик на полу), и затем переместим наклейку на один почтовый ящик выше. Когда мы вытаскиваем элемент из стека, то мы перемещаем наклейку на один почтовый ящик ниже и удаляем элемент из почтового ящика. Всё, что находится ниже маркера — находится в стеке. Всё, что находится в ящике с наклейкой и выше – не находится в стеке.

Сегмент стека вызовов

Сегмент стека вызовов содержит память, используемую для стека вызовов. При запуске приложения, функция main() помещается в стек вызовов операционной системой. Затем программа начинает своё выполнение.

Когда программа встречает вызов функции, то эта функция помещается в стек вызовов. При завершении выполнения функции, она удаляется из стека вызовов. Таким образом, просматривая функции, добавленные в стек, мы можем видеть все функции, которые были вызваны до текущей точки выполнения.

Наша аналогия с почтовыми ящиками – это действительно то, как работает стек вызовов. Стек вызовов имеет фиксированное количество адресов памяти (фиксированный размер). Почтовые ящики являются адресами памяти, а «элементы», которые мы добавляем и вытягиваем в стеке, называются фреймами (или еще «кадрами ») стека. Кадр стека отслеживает все данные, связанные с одним вызовом функции. «Наклейка» — это регистр (небольшая часть памяти в ЦП), который является указателем стека . Указатель стека отслеживает, где находится вершина стека вызовов.

Единственное отличие фактического стека вызовов от нашего гипотетического стека почтовых ящиков заключается в том, что, когда мы вытягиваем элемент из стека вызовов, то нам не нужно очищать память (т.е. вынимать всё содержимое из почтового ящика). Мы можем просто оставить эту память для следующего элемента, который и перезапишет её. Поскольку указатель стека будет ниже этого адреса памяти, то, как мы уже знаем, эта ячейка памяти не будет находится в стеке.

Стек вызовов на практике

Давайте рассмотрим более подробно, как работает стек вызовов. Ниже приведена последовательность шагов, выполняемых при вызове функции :

Программа сталкивается с вызовом функции.

Фрейм стека создается и помещается в стек, он состоит из:

Адреса инструкции, который находится за вызовом функции (так называемый «обратный адрес »). Так процессор запоминает, куда возвращаться после выполнения функции.

Аргументов функции.

Памяти для локальных переменных.

Сохраненных копий всех регистров, модифицированных функцией, которые необходимо будет восстановить после того, как функция завершит своё выполнение.

Процессор переходит к точке начала выполнения функции.

Инструкции внутри функции начинают выполняться.

После завершения функции, выполняются следующие шаги :

Регистры восстанавливаются из стека вызовов.

Фрейм стека вытягивается из стека. Освобождается память всех локальных переменных и аргументов.

Обрабатывается возвращаемое значение.

ЦП возобновляет выполнение кода (исходя из обратного адреса).

Возвращаемые значения могут обрабатываться разными способами, в зависимости от архитектуры компьютера. Некоторые архитектуры считают возвращаемое значение частью фрейма стека. Другие используют регистры процессора.

Знать все детали работы стека вызовов не так уж и важно. Однако понимание того, что функции при вызове добавляются в стек, а при завершении выполнения – удаляются из стека, даёт основы, необходимые для понимания рекурсии, а также некоторых других концепций, которые полезны при .

Пример стека вызовов

Рассмотрим следующий фрагмент кода:

Стек вызовов этой программы выглядит следующим образом:

boo() (включая параметр b)
main()

Переполнение стека

Стек имеет ограниченный размер и, следовательно, может содержать только ограниченный объем информации. В Windows размер стека по умолчанию составляет 1 МБ. На некоторых других Unix-системах этот размер может достигать и 8 МБ. Если программа пытается поместить слишком много информации в стек, то это приведет к переполнению стека. Переполнение стека (stack overflow) происходит при запросе на память, в то время, когда вся память стека уже выделена — в этом случае все запросы на выделения начнут переливаться (переполняться) в другие разделы памяти.

Переполнение стека является результатом добавления слишком большого числа переменных в стек и/или создания слишком большого количества вложенных вызовов функций (например, где функция A вызывает функцию B, которая в свою очередь вызывает функцию C, а та вызывает функцию D и т.д. и т.п.). Переполнение стека обычно приводит к сбою в программе.

Например:

int main() { int stack; return 0; }

int main ()

int stack [ 100000000 ] ;

return 0 ;

Эта программа пытается добавить огромный массив в стек вызовов. Поскольку размера стека недостаточно для обработки такого массива, то его добавление переходит и на другие части памяти, которые программа использовать не может. Следовательно, получаем сбой.

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

void boo() { boo(); } int main() { boo(); return 0; }

Стек является общей структурой данных для представления данных, которые должны обрабатываться в определенном порядке. Например, когда функция вызывает другую функцию, которая, в свою очередь, вызывает третью функцию, важно, чтобы третья функция вернулась на вторую функцию, а не первую.

Один из способов реализации такого порядка обработки данных — это организовать своего рода очередь вызовов функций. Последняя добавленная в стек функция, будет завершена первой и наоборот, первая добавленная в стек функция будет завершена последней. Таким образом, сама структура данных обеспечивает надлежащий порядок вызовов.

Концептуально, структура данных — стек очень проста: она позволяет добавлять или удалять элементы в определенном порядке. Каждый раз, когда добавляется элемент, он попадает на вершину стека, единственный элемент, который может быть удален из стека — элемент, который находится на вершине стека. Таким образом, стек, как принято говорить, «первым пришел, последним ушел — FILO» или «последним пришел, первым ушел — LIFO». Первый элемент, добавленный в стек будет удален из него в последнюю очередь.

Так в чем же дело? Зачем нам нужны стеки? Как мы уже говорили, стеки — удобный способ организации вызовов функций. В самом деле, «стек вызовов» это термин, который часто используют для обозначения списка функций, которые сейчас либо выполняются, либо находятся в режиме ожидания возвращаемого значения других функций.

В некотором смысле, стеки являются частью фундаментального языка информатики. Когда вы хотите реализовать очередь типа — «первый пришел, последним ушел», то имеет смысл говорить о стеках с использованием общей терминологии. Кроме того, такие очереди участвуют во многих процессах, начиная от теоретических компьютерных наук, например функции push-down и многое другое.

Стеки имеют некоторые ассоциируемые методы:

  • Push — добавить элемент в стек;
  • Pop — удалить элемент из стека;
  • Peek — просмотреть элементы стека;
  • LIFO — поведение стека,
  • FILO Equivalent to LIFO

Этот стек был реализован с шаблонами, чтобы его можно было использовать практически для любых типов данных. Причем размер стека определяется динамически, во время выполнения программы. В стек добавлена также дополнительная функция: peek() , которая показывает n-й элемент от вершины стека.

#ifndef STACK_H #define STACK_H #include // для assert #include #include // для setw template class Stack { private: T *stackPtr; // указатель на стек const int size; // максимальное количество элементов в стеке int top; // номер текущего элемента стека public: Stack(int = 10); // по умолчанию размер стека равен 10 элементам Stack(const Stack &); // конструктор копирования ~Stack(); // деструктор inline void push(const T &); // поместить элемент в вершину стека inline T pop(); // удалить элемент из вершины стека и вернуть его inline void printStack(); // вывод стека на экран inline const T &Peek(int) const; // n-й элемент от вершины стека inline int getStackSize() const; // получить размер стека inline T *getPtr() const; // получить указатель на стек inline int getTop() const; // получить номер текущего элемента в стеке }; // реализация методов шаблона класса STack // конструктор Стека template Stack::Stack(int maxSize) : size(maxSize) // инициализация константы { stackPtr = new T; // выделить память под стек top = 0; // инициализируем текущий элемент нулем; } // конструктор копирования template Stack::Stack(const Stack & otherStack) : size(otherStack.getStackSize()) // инициализация константы { stackPtr = new T; // выделить память под новый стек top = otherStack.getTop(); for(int ix = 0; ix < top; ix++) stackPtr = otherStack.getPtr(); } // функция деструктора Стека template Stack::~Stack() { delete stackPtr; // удаляем стек } // функция добавления элемента в стек template inline void Stack::push(const T &value) { // проверяем размер стека assert(top < size); // номер текущего элемента должен быть меньше размера стека stackPtr = value; // помещаем элемент в стек } // функция удаления элемента из стека template inline T Stack::pop() { // проверяем размер стека assert(top > 0); // номер текущего элемента должен быть больше 0 stackPtr[--top]; // удаляем элемент из стека } // функция возвращает n-й элемент от вершины стека template inline const T &Stack::Peek(int nom) const { // assert(nom <= top); return stackPtr; // вернуть n-й элемент стека } // вывод стека на экран template inline void Stack::printStack() { for (int ix = top - 1; ix >= 0; ix--) cout << "|" << setw(4) << stackPtr << endl; } // вернуть размер стека template inline int Stack::getStackSize() const { return size; } // вернуть указатель на стек (для конструктора копирования) template inline T *Stack::getPtr() const { return stackPtr; } // вернуть размер стека template inline int Stack::getTop() const { return top; } #endif // STACK_H

Шаблон класса Stack реализован в отдельном *.h файле, да, именно реализован, я не ошибся. Все дело в том, что и интерфейс шаблона класса и реализация должны находиться в одном файле, иначе вы увидите список ошибок похожего содержания:

ошибка undefined reference to «метод шаблона класса»

Интерфейс шаблона класса объявлен с 9 по 28 строки. Все методы класса содержат комментарии и, на мой взгляд, описывать их работу отдельно не имеет смысла. Обратите внимание на то, что все методы шаблона класса Стек объявлены как . Это сделано для того, чтобы ускорить работу класса. Так как встроенные функции класса работают быстрее, чем внешние.

Сразу после интерфейса шаблона идет реализация методов класса Стек, строки 32 — 117. В реализации методов класса ничего сложного нет, если знать как устроен стек, шаблоны и . Заметьте, в классе есть два конструктора, первый объявлен в строках 32-33, — это конструктор по умолчанию. А вот конструктор в строках 41-5, — это конструктор копирования. Он нужен для того, чтобы скопировать один объект в другой. Метод Peek , строки 80 — 88 предоставляет возможность просматривать элементы стека. Необходимо просто ввести номер элемента, отсчет идет от вершины стека. Остальные функции являются служебными, то есть предназначены для использования внутри класса, конечно же кроме функции printStack() , она вывод элементы стека на экран.

Теперь посмотрим на драйвер для нашего стека, под драйвером я подразумеваю программу в которой тестируется работа класса. Как всегда это main функция, в которой мы и будем тестировать наш шаблон класса Stack . Смотрим код ниже:

#include using namespace std; #include "stack.h" int main() { Stack stackSymbol(5); int ct = 0; char ch; while (ct++ < 5) { cin >> ch; stackSymbol.push(ch); // помещаем элементы в стек } cout << endl; stackSymbol.printStack(); // печать стека cout << "\n\nУдалим элемент из стека\n"; stackSymbol.pop(); stackSymbol.printStack(); // печать стека Stack newStack(stackSymbol); cout << "\n\nСработал конструктор копирования!\n"; newStack.printStack(); cout << "Второй в очереди элемент: "<< newStack.Peek(2) << endl; return 0; }

Создали объект стека, строка 9, размер стека при этом равен 5, то есть стек может поместить не более 5 элементов. Заполняем стек в , строки 13 — 17. В строке 21 выводим стек на экран, после удаляем один элемент из стека, строка 24 и снова выводим содержимое стека, поверьте оно изменилось, ровно на один элемент. Смотрим результат работы программы:

LOTR! | ! | R | T | O | L Удалим элемент из стека | R | T | O | L Сработал конструктор копирования! | R | T | O | L Второй в очереди элемент: T

В строке 28 мы воспользовались конструктором копирования, о том самом, о котором я писал выше. Не забудем про функцию peek() , давайте посмотри на второй элемент стека, строка 33.

На этом все! Стек у нас получился и исправно работает, попробуйте его протестировать, например на типе данных int . Я уверен, что все останется исправно работать.

– Игорь (Администратор)

В рамках данной статьи, я расскажу вам что такое стек , а так же для чего он нужен и где применяется.

Большое количество задач, связанных с информацией, поддаются типизированному решению. Поэтому нет ничего удивительного в том, что для многих из них уже давно придуманы методы, термины и описания. Например, нередко можно услышать такие слово, как стек. Звучит весьма сложно, однако все существенно проще.

Стек (stack) - это метод представления однотипных данных (можно просто называть типом) в порядке LIFO (Last In - First Out, что означает "первый вошел - последний вышел"). Стоит упомянуть, что в русской технике его так же называют "магазином". И речь тут не о продуктовом магазине, а о рожке с патронами для оружия, так как принцип весьма схож - первый вставленный патрон будет использован последним.

Примечание : Стоит знать, что у этого слова могут быть и другие значения. Поэтому если речь не касается компьютеров, то имеет смысл уточнить.

Чтобы лучше понять, приведу жизненный пример. Допустим у вас есть стопка листов. Каждый исписанный лист вы кладете рядом, а каждый следующий поверх остальных. Чтобы достать к примеру, самый первый лист из полученной стопки, вам необходимо вытащить все остальные листы. Вот по этому же самому принципу и устроен stack. То есть, каждый последний добавленный элемент становится верхним и чтобы достать, к примеру, самый первый элемент необходимо вытащить все остальные.

Для чего нужен стек? Основное предназначение это решение типовых задач, где необходимо поддерживать последовательность состояний чего-либо или где нужно инверсионное представление данных (то есть в обратную сторону).

В компьютерной сфере стек используется в аппаратных устройствах (например, процессоре), в операционной системе и многих программах. Если рассматривать пример, с которым знаком практически каждый, кто занимался программированием, то без стека не была бы возможна рекурсия, ведь при каждом повторном входе в функцию нужно сохранять текущее состояние на вершине, а при каждом выходе из функции быстро восстанавливать это состояния (то есть, как раз последовательность LIFO). А если копнуть еще глубже, то в принципе весь подход к запуску и выполнению программ устроен на принципе стека, где прежде чем следующая программа, запущенная из основной, будет выполняться, состояние предыдущей заносится в стек, чтобы когда запущенное приложение или подпрограмма закончила выполняться, предыдущая программа нормально продолжила выполняться с места остановки.

Какие операции у stack? Основных операций всего две:

1. Добавление элемента в вершину стека называется push

2. Извлечения верхнего элемента называется pop

Но, так же периодически можно встретить реализацию операции чтения верхнего элемента без его извлечения - называется peek .

Как организуется стек? Обычно стек реализуется двумя вариантами:

1. С помощью массива и переменной, которая указывает на ячейку с вершиной стека

2. С помощью связанных списков

У каждого из этих 2-х вариантов есть свои плюсы и минусы. Например, связанные списки более безопасны в плане применения, так как каждый добавляемый элемент помещается в динамически созданную структуру (нет проблем с количеством элементов - нет дырок безопасности, позволяющих свободно перемещаться в памяти программы). Однако, в плане хранения и быстроты использования они менее эффективны (требуют дополнительное место для хранения указателей; разбросаны в памяти, а не расположены друг за другом, как в массивах).

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

Стек

Стек - самая популярная и, пожалуй, самая важная структура данных в программировании. Стек представляет собой запоминающее устройство, из которого элементы извлекаются в порядке, обратном их добавлению. Это как бы неправильная очередь, в которой первым обслуживают того, кто встал в нее последним. В программистской литературе общепринятыми являются аббревиатуры, обозначающие дисциплину работы очереди и стека. Дисциплина работы очереди обозначается FIFO, что означает первым пришел - первым уйдешь (First In First Out). Дисциплина работы стека обозначается LIFO, последним пришел - первым уйдешь (Last In First Out).

Стек можно представить в виде трубки с подпружиненым дном, расположеной вертикально. Верхний конец трубки открыт, в него можно добавлять, или, как говорят, заталкивать элементы. Общепринятые английские термины в этом плане очень красочны, операция добавления элемента в стек обозначается push, в переводе "затолкнуть, запихнуть". Новый добавляемый элемент проталкивает элементы, помещеные в стек ранее, на одну позицию вниз. При извлечении элементов из стека они как бы выталкиваются вверх, по-английски pop ("выстреливают").

Примером стека может служить стог сена, стопка бумаг на столе, стопка тарелок и т.п. Отсюда произошло название стека, что по-английски означает стопка. Тарелки снимаются со стопки в порядке, обратном их добавлению. Доступна только верхняя тарелка, т.е. тарелка на вершине стека . Хорошим примером будет также служить железнодорожный тупик, в который можно составлять вагоны.

Стек применяется довольно часто, причем в самых разных ситуациях. Объединяет их следующая цель: нужно сохранить некоторую работу, которая еще не выполнена до конца, при необходимости переключения на другую задачу. Стек используется для временного сохранения состояния не выполненного до конца задания. После сохранения состояния компьютер переключается на другую задачу. По окончании ее выполнения состояние отложенного задания восстанавливается из стека, и компьютер продолжает прерванную работу.

Почему именно стек используется для сохранения состояния прерванного задания? Предположим, что компьютер выполняет задачу A. В процессе ее выполнения возникает необходимость выполнить задачу B. Состояние задачи A запоминается, и компьютер переходит к выполнению задачи B. Но ведь и при выполнении задачи B компьютер может переключиться на другую задачу C, и нужно будет сохранить состояние задачи B, прежде чем перейти к C. Позже, по окончании C будет сперва восстановлено состояние задачи B, затем, по окончании B, - состояние задачи A. Таким образом, восстановление происходит в порядке, обратном сохранению, что соответствует дисциплине работы стека.



Стек позволяет организовать рекурсию, т.е. обращение подпрограммы к самой себе либо непосредственно, либо через цепочку других вызовов. Пусть, например, подпрограмма A выполняет алгоритм, зависящий от входного параметра X и, возможно, от состояния глобальных данных. Для самых простых значений X алгоритм реализуется непосредственно. В случае более сложных значений X алгоритм реализуется как сведение к применению того же алгоритма для более простых значений X. При этом подпрограмма A обращается сама к себе, передавая в качестве параметра более простое значение X. При таком обращении предыдущее значение параметра X, а также все локальные переменные подпрограммы A сохраняются в стеке. Далее создается новый набор локальных переменных и переменная, содержащая новое (более простое) значение параметра X. Вызванная подпрограмма A работает с новым набором переменных, не разрушая предыдущего набора. По окончании вызова старый набор локальных переменных и старое состояние входного параметра X восстанавливаются из стека, и подпрограмма продолжает работу с того места, где она была прервана.

На самом деле даже не приходится специальным образом сохранять значения локальных переменных подпрограммы в стеке. Дело в том, что локальные переменные подпрограммы (т.е. ее внутренние, рабочие переменные, которые создаются в начале ее выполнения и уничтожаются в конце) размещаются в стеке, реализованном аппаратно на базе обычной оперативной памяти. В самом начале работы подпрограмма захватывает место в стеке под свои локальные переменные, этот участок памяти в аппаратном стеке называют обычно блок локальных переменных или по-английски frame ("кадр "). В момент окончания работы подпрограмма освобождает память, удаляя из стека блок своих локальных переменных.

Кроме локальных переменных, в аппаратном стеке сохраняются адреса возврата при вызовах подпрограмм. Пусть в некоторой точке программы A вызывается подпрограмма B . Перед вызовом подпрограммы B адрес инструкции, следующей за инструкцией вызова B, сохраняется в стеке. Это так называемый адрес возврата в программу A. По окончании работы подпрограмма B извлекает из стека адрес возврата в программу A и возвращает управление по этому адресу. Таким образом, компьютер продолжает выполнение программы A, начиная с инструкции, следующей за инструкцией вызова. В большинстве процессоров имеются специальные команды, поддерживающие вызов подпрограммы с предварительным помещением адреса возврата в стек и возврат из подпрограммы по адресу, извлекаемому из стека. Обычно команда вызова назывется call, команда возврата - return.

В стек помещаются также параметры подпрограммы или функции перед ее вызовом. Порядок их помещения в стек зависит от соглашений, принятых в языках высокого уровня. Так, в языке Си или C++ на вершине стека лежит первый аргумент функции, под ним второй и так далее. В Паскале все наоборот, на вершине стека лежит последний аргумент функции. (Поэтому, кстати, в Си возможны функции с переменным числом аргументов, такие, как printf, а в Паскале нет.)

В Фортране-4, одном из самых старых и самых удачных языков программирования, аргументы передаются через специальную область памяти, которая может располагаться не в стеке, поскольку до конца 70-х годов XX века еще существовали компьютеры вроде IBM 360 или ЕС ЭВМ без аппаратной реализации стека. Адреса возврата также сохранялись не в стеке, а в фиксированных для каждой подпрограммы ячейках памяти. Программисты называют такую память статической в том смысле, что статические переменные занимают всегда одно и то же место в памяти в любой момент работы программы. При использовании только статической памяти рекурсия невозможна, поскольку при новом вызове предыдущие значения локальных переменных разрушаются. В эталонном Фортране-4 использовались только статические переменные, а рекурсия была запрещена. До сих пор язык Фортран широко используется в научных и инженерных расчетах, однако, современный стандарт Фортрана-90 уже вводит стековую память, устраняя недостатки ранних версий языка.

Стек - это коллекция, элементы которой получают по принципу «последний вошел, первый вышел» (Last-In-First-Out или LIFO) . Это значит, что мы будем иметь доступ только к последнему добавленному элементу.

В отличие от списков, мы не можем получить доступ к произвольному элементу стека. Мы можем только добавлять или удалять элементы с помощью специальных методов. У стека нет также метода Contains , как у списков. Кроме того, у стека нет итератора. Для того, чтобы понимать, почему на стек накладываются такие ограничения, давайте посмотрим на то, как он работает и как используется.

Наиболее часто встречающаяся аналогия для объяснения стека - стопка тарелок. Вне зависимости от того, сколько тарелок в стопке, мы всегда можем снять верхнюю. Чистые тарелки точно так же кладутся на верх стопки, и мы всегда будем первой брать ту тарелку, которая была положена последней.

Если мы положим, например, красную тарелку, затем синюю, а затем зеленую, то сначала надо будет снять зеленую, потом синюю, и, наконец, красную. Главное, что надо запомнить - тарелки всегда ставятся и на верх стопки. Когда кто-то берет тарелку, он также снимает ее сверху. Получается, что тарелки разбираются в порядке, обратном тому, в котором ставились.

Теперь, когда мы понимаем, как работает стек, введем несколько терминов. Операция добавления элемента на стек называется «push», удаления - «pop». Последний добавленный элемент называется верхушкой стека, или «top», и его можно посмотреть с помощью операции «peek». Давайте теперь посмотрим на заготовку класса, реализующего стек.

Класс Stack

Класс Stack определяет методы Push , Pop , Peek для доступа к элементам и поле Count . В реализации мы будем использовать LinkedList для хранения элементов.

Public class Stack { LinkedList _items = new LinkedList(); public void Push(T value) { throw new NotImplementedException(); } public T Pop() { throw new NotImplementedException(); } public T Peek() { throw new NotImplementedException(); } public int Count { get; } }

Метод Push

  • Поведение: Добавляет элемент на вершину стека.
  • Сложность: O(1).

Поскольку мы используем связный список для хранения элементов, можно просто добавить новый в конец списка.

Public void Push(T value) { _items.AddLast(value); }

Метод Pop

  • Поведение: Удаляет элемент с вершины стека и возвращает его. Если стек пустой, кидает InvalidOperationException .
  • Сложность: O(1).

Push добавляет элементы в конец списка, поэтому забирать их будет также с конца. В случае, если список пуст, будет выбрасываться исключение.

Public T Pop() { if (_items.Count == 0) { throw new InvalidOperationException("The stack is empty"); } T result = _items.Tail.Value; _items.RemoveLast(); return result; }

Метод Peek

  • Поведение: Возвращает верхний элемент стека, но не удаляет его. Если стек пустой, кидает InvalidOperationException .
  • Сложность: O(1).
public T Peek() { if (_items.Count == 0) { throw new InvalidOperationException("The stack is empty"); } return _items.Tail.Value; }

Метод Count

  • Поведение: Возвращает количество элементов в стеке.
  • Сложность: O(1).

Зачем нам знать, сколько элементов находится в стеке, если мы все равно не имеем к ним доступа? С помощью этого поля мы можем проверить, есть ли элементы на стеке или он пуст. Это очень полезно, учитывая, что метод Pop кидает исключение.

Пример: калькулятор в обратной польской записи.

Классический пример использования стека - калькулятор в обратной польской, или постфиксной, записи. В ней оператор записывается после своих операндов. То есть, мы пишем:

<операнд> <операнд> <оператор>

вместо традиционного:

<операнд> <оператор> <операнд>

Другими словами, вместо «4 + 2» мы запишем «4 2 +». Если вам интересно происхождение обратной польской записи и ее названия, вы можете узнать об этом на Википедии или в поисковике.

То, как вычисляется обратная польская запись и почему стек так полезен при ее использовании, хорошо видно из следующего алгоритма:

For each input value if the value is an integer push the value on to the operand stack else if the value is an operator pop the left and right values from the stack evaluate the operator push the result on to the stack pop answer from stack.

То есть, для выражения «4 2 +» действия будут следующие:

Push(4) push(2) push(pop() + pop())

В конце на стеке окажется одно значение - 6.

Далее приводится полный код простого калькулятора, который считывает выражение (например, 4 2 +) из консоли, разбивает входные данные по пробелам (["4", "2", "+"]) и выполняет алгоритм вычисления. Вычисление продолжается до тех пор, пока не будет встречено слово quit .

Void RpnLoop() { while (true) { Console.Write("> "); string input = Console.ReadLine(); if (input.Trim().ToLower() == "quit") { break; } // Стек еще не обработанных значений. Stack values = new Stack(); foreach (string token in input.Split(new char { " " })) { // Если значение - целое число... int value; if (int.TryParse(token, out value)) { // ... положить его на стек. values.Push(value); } else { // в противном случае выполнить операцию... int rhs = values.Pop(); int lhs = values.Pop(); // ... и положить результат обратно. switch (token) { case "+": values.Push(lhs + rhs); break; case "-": values.Push(lhs - rhs); break; case "*": values.Push(lhs * rhs); break; case "/": values.Push(lhs / rhs); break; case "%": values.Push(lhs % rhs); break; default: // Если операция не +, -, * или / throw new ArgumentException(string.Format("Unrecognized token: {0}", token)); } } } // Последний элемент на стеке и есть результат. Console.WriteLine(values.Pop()); } }

Очередь

Очереди очень похожи на стеки. Они также не дают доступа к произвольному элементу, но, в отличие от стека, элементы кладутся (enqueue) и забираются (dequeue) с разных концов. Такой метод называется «первый вошел, первый вышел» (First-In-First-Out или FIFO) . То есть забирать элементы из очереди мы будем в том же порядке, что и клали. Как реальная очередь или конвейер.

Очереди часто используются в программах для реализации буфера, в который можно положить элемент для последующей обработки, сохраняя порядок поступления. Например, если база данных поддерживает только одно соединение, можно использовать очередь потоков, которые будут, как ни странно, ждать своей очереди на доступ к БД.

Класс Queue

Класс Queue , как и стек, будет реализован с помощью связного списка. Он будет предоставлять методы Enqueue для добавления элемента, Dequeue для удаления, Peek и Count . Как и класс Stack , он не будет реализовывать интерфейс ICollection , поскольку это коллекции специального назначения.

Public class Queue { LinkedList _items = new LinkedList(); public void Enqueue(T value) { throw new NotImplementedException(); } public T Dequeue() { throw new NotImplementedException(); } public T Peek() { throw new NotImplementedException(); } public int Count { get; } }

Метод Enqueue

  • Поведение: Добавляет элемент в очередь.
  • Сложность: O(1).

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

Public void Enqueue(T value) { _items.AddFirst(value); }

Метод Dequeue

  • Поведение: Удаляет первый помещенный элемент из очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException .
  • Сложность: O(1).

Поскольку мы вставляем элементы в начало списка, убирать мы их будем с конца. Если список пуст, кидается исключение.

Public T Dequeue() { if (_items.Count == 0) { throw new InvalidOperationException("The queue is empty"); } T last = _items.Tail.Value; _items.RemoveLast(); return last; }

Метод Peek

  • Поведение: Возвращает элемент, который вернет следующий вызов метода Dequeue . Очередь остается без изменений. Если очередь пустая, кидает InvalidOperationException .
  • Сложность: O(1).
public T Peek() { if (_items.Count == 0) { throw new InvalidOperationException("The queue is empty"); } return _items.Tail.Value; }

Метод Count

  • Поведение:
  • Сложность: O(1).
public int Count { get { return _items.Count; } }

Двусторонняя очередь

Двусторонняя очередь (Double-ended queue) , или дек (Deque) , расширяет поведение очереди. В дек можно добавлять или удалять элементы как с начала, так и с конца очереди. Такое поведение полезно во многих задачах, например, планирование выполнения потоков или реализация других структур данных. Позже мы рассмотрим вариант реализации стека с помощью двусторонней очереди.

Класс Deque

Класс Deque проще всего реализовать с помощью двусвязного списка. Он позволяет просматривать, удалять и добавлять элементы в начало и в конец списка. Основное отличие двусторонней очереди от обычной - методы Enqueue , Dequeue , и Peek разделены на пары для работы с обоими концами списка.

Public class Deque { LinkedList _items = new LinkedList(); public void EnqueueFirst(T value) { throw new NotImplementedException(); } public void EnqueueLast(T value) { throw new NotImplementedException(); } public T DequeueFirst() { throw new NotImplementedException(); } public T DequeueLast() { throw new NotImplementedException(); } public T PeekFirst() { throw new NotImplementedException(); } public T PeekLast() { throw new NotImplementedException(); } public int Count { get; } }

Метод EnqueueFirst

  • Поведение:
  • Сложность: O(1).
public void EnqueueFirst(T value) { _items.AddFirst(value); }

Метод EnqueueLast

  • Поведение:
  • Сложность: O(1).
public void EnqueueLast(T value) { _items.AddLast(value); }

Метод DequeueFirst

  • Поведение: Удаляет элемент из начала очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException .
  • Сложность: O(1).
public T DequeueFirst() { if (_items.Count == 0) { throw new InvalidOperationException("DequeueFirst called when deque is empty"); } T temp = _items.Head.Value; _items.RemoveFirst(); return temp; }

Метод DequeueLast

  • Поведение:
  • Сложность: O(1).
public T DequeueLast() { if (_items.Count == 0) { throw new InvalidOperationException("DequeueLast called when deque is empty"); } T temp = _items.Tail.Value; _items.RemoveLast(); return temp; }

Метод PeekFirst

  • Поведение: Возвращает элемент из начала очереди, не изменяя ее. Если очередь пустая, кидает InvalidOperationException .
  • Сложность: O(1).
public T PeekFirst() { if (_items.Count == 0) { throw new InvalidOperationException("PeekFirst called when deque is empty"); } return _items.Head.Value; }

Метод PeekLast

  • Поведение:
  • Сложность: O(1).
public T PeekLast() { if (_items.Count == 0) { throw new InvalidOperationException("PeekLast called when deque is empty"); } return _items.Tail.Value; }

Метод Count

  • Поведение: Возвращает количество элементов в очереди или 0, если очередь пустая.
  • Сложность: O(1).
public int Count { get { return _items.Count; } }

Пример: реализация стека

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

У вас, возможно, возник вопрос, зачем реализовывать стек на основе очереди вместо связного списка. Причины две: производительность и повторное использование кода. У связного списка есть накладные расходы на создание узлов и нет гарантии локальности данных: элементы могут быть расположены в любом месте памяти, что вызывает большое количество промахов и падение производительности на уровне процессоров. Более производительная реализация двусторонней очереди требует массива для хранения элементов.

Тем не менее, реализация стека или очереди с помощью массива - непростая задача, но такая реализация двусторонней очереди и использование ее в качестве основы для других структур данных даст нам серьезный плюс к производительности и позволит повторно использовать код. Это снижает стоимость поддержки.

Позже мы посмотрим на вариант очереди с использованием массива, но сначала давайте взглянем на класс стека с использованием двусторонней очереди:

Public class Stack { Deque _items = new Deque(); public void Push(T value) { _items.EnqueueFirst(value); } public T Pop() { return _items.DequeueFirst(); } public T Peek() { return _items.PeekFirst(); } public int Count { get { return _items.Count; } } }

Заметьте, что вся обработка ошибок теперь лежит на классе Deque , и, кроме того, любая оптимизация очереди также отразится на стеке. Реализация обычной очереди на основе двусторонней настолько проста, что мы оставим ее читателю в качестве упражнения.

Хранение элементов в массиве

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

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

При создании очереди у нее внутри создается массив нулевой длины. Красные буквы «h» и «t» означают указатели _head и _tail соответственно.

Deque deq = new Deque(); deq.EnqueueFirst(1);

Deq.EnqueueLast(2);

Deq.EnqueueFirst(0);

Обратите внимание: индекс «головы» очереди перескочил в начало списка. Теперь первый элемент, который будет возвращен при вызове метода DequeueFirst - 0 (индекс 3).

Deq.EnqueueLast(3);

Массив заполнен, поэтому при добавлении элемента произойдет следующее:

  • Алгорим роста определит размер нового массива.
  • Элементы скопируются в новый массив с «головы» до «хвоста».
  • Добавится новый элемент.
deq.EnqueueLast(4);

Теперь посмотрим, что происходит при удалении элемента:

Deq.DequeueFirst();

Deq.DequeueLast();

Ключевой момент: вне зависимости от вместимости или заполненности внутреннего массива, логически, содержимое очереди - элементы от «головы» до «хвоста» с учетом «закольцованности». Такое поведение также называется «кольцевым буфером».

Теперь давайте посмотрим на реализацию.

Класс Deque (с использованием массива)

Интерфейс очереди на основе массива такой же, как и в случае реализации через связный список. Мы не будем его повторять. Однако, поскольку список был заменен на массив, у нас добавились новые поля - сам массив, его размер и указатели на «хвост» и «голову» очереди.

Public class Deque { T _items = new T; // Количество элементов в очереди. int _size = 0; // Индекс первого (самого старого) элемента. int _head = 0; // Индекс последнего (самого нового) элемента. int _tail = -1; ... }

Алгоритм роста

Когда свободное место во внутреннем массиве заканчивается, его необходимо увеличить, скопировать элементы и обновить указатели на «хвост» и «голову». Эта операция производится при необходимости во время добавления элемента. Параметр startingIndex используется, чтобы показать, сколько полей в начале необходимо оставить пустыми (в случае добавления в начало).

Обратите внимание на то, как извлекаются данные, когда приходится переходить в начало массива при проходе от «головы» к «хвосту».

Private void allocateNewArray(int startingIndex) { int newLength = (_size == 0) ? 4: _size * 2; T newArray = new T; if (_size > 0) { int targetIndex = startingIndex; // Копируем содержимое... // Если массив не закольцован, просто копируем элементы. // В противном случае, копирует от head до конца, а затем от начала массива до tail. // Если tail меньше, чем head, переходим в начало. if (_tail < _head) { // Копируем _items.._items в newArray..newArray[N]. for (int index = _head; index < _items.Length; index++) { newArray = _items; targetIndex++; } // Копируем _items.._items в newArray.. for (int index = 0; index <= _tail; index++) { newArray = _items; targetIndex++; } } else { // Копируем _items.._items в newArray..newArray[N] for (int index = _head; index <= _tail; index++) { newArray = _items; targetIndex++; } } _head = startingIndex; _tail = targetIndex - 1; } else { // Массив пуст. _head = 0; _tail = -1; } _items = newArray; }

Метод EnqueueFirst

  • Поведение: Добавляет элемент в начало очереди. Этот элемент будет взят из очереди следующим при вызове метода DequeueFirst .
  • Сложность:
public void EnqueueFirst(T item) { // Проверим, необходимо ли увеличение массива: if (_items.Length == _size) { allocateNewArray(1); } // Так как массив не заполнен и _head больше 0, // мы знаем, что есть место в начале массива. if (_head > 0) { _head--; } else { // В противном случае мы должны закольцеваться. _head = _items.Length - 1; } _items[_head] = item; _size++; if (_size == 1) { // Если мы добавили первый элемент в пустую // очередь, он же будет и последним, поэтому // нужно обновить и _tail. _tail = _head; } }

Метод EnqueueLast

  • Поведение: Добавляет элемент в конец очереди. Этот элемент будет взят из очереди следующим при вызове метода DequeueLast .
  • Сложность: O(1) в большинстве случаев; O(n), когда нужно расширение массива.
public void EnqueueLast(T item) { // Проверим, необходимо ли увеличение массива: if (_items.Length == _size) { allocateNewArray(0); } // Теперь, когда у нас есть подходящий массив, // если _tail в конце массива, нам надо перейти в начало. if (_tail == _items.Length - 1) { _tail = 0; } else { _tail++; } _items[_tail] = item; _size++; if (_size == 1) { // Если мы добавили последний элемент в пустую // очередь, он же будет и первым, поэтому // нужно обновить и _head. _head = _tail; } }

Метод DequeueFirst

  • Поведение: Удаляет элемент с начала очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException .
  • Сложность: O(1).
public T DequeueFirst() { if (_size == 0) { throw new InvalidOperationException("The deque is empty"); } T value = _items[_head]; if (_head == _items.Length - 1) { // Если head установлен на последнем индексе, переходим к началу массива. _head = 0; } else { // Переходим к следующему элементу. _head++; } _size--; return value; }

Метод DequeueLast

  • Поведение: Удаляет элемент с конца очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException .
  • Сложность: O(1).
public T DequeueLast() { if (_size == 0) { throw new InvalidOperationException("The deque is empty"); } T value = _items[_tail]; if (_tail == 0) { // Если tail установлен на начало массива, переходим к концу. _tail = _items.Length - 1; } else { // Переходим к предыдущему элементу. _tail--; } _size--; return value; }

Метод PeekFirst

  • Поведение: Возвращает элемент с начала очереди, не изменяя ее. Если очередь пустая, кидает InvalidOperationException .
  • Сложность: O(1).
public T PeekFirst() { if (_size == 0) { throw new InvalidOperationException("The deque is empty"); } return _items[_head]; }

Метод PeekLast

  • Поведение: Возвращает элемент с конца очереди, не изменяя ее. Если очередь пустая, кидает InvalidOperationException .
  • Сложность: O(1).
public T PeekLast() { if (_size == 0) { throw new InvalidOperationException("The deque is empty"); } return _items[_tail]; }

Метод Count

  • Поведение: Возвращает количество элементов в очереди или 0, если очередь пустая.
  • Сложность: O(1).
public int Count { get { return _size; } }

Продолжение следует

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

Еще на эту тему:

Скачать Driver Sweeper – программа для удаления драйверов из OC Windows Скачать программу для удаления драйверов карты Скачать Driver Sweeper – программа для удаления драйверов из OC Windows Скачать программу для удаления драйверов карты
Выкидывает на рабочий стол Sniper Elite V2 Что делать если лагает sniper elite 3 Выкидывает на рабочий стол Sniper Elite V2 Что делать если лагает sniper elite 3
Поиск похожей фотографии в интернет Поиск похожей фотографии в интернет