Алгоритмы и структуры данных для начинающих: стеки и очереди.  Что такое стек

last in - first out , «последним пришёл - первым вышел»).

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

В некоторых языках (например, Lisp , Python ) стеком можно назвать любой список, так как для них доступны операции pop и push. В языке C++ стандартная библиотека имеет класс с реализованной структурой и методами . И т. д.

Энциклопедичный YouTube

1 / 3

Информатика. Структуры данных: Стек. Центр онлайн-обучения «Фоксфорд»

#9. Стек / 1. Ассемблер и процедуры / Программирование с нуля

Основы сетей передачи данных. Модель OSI и стек протоколов TCP IP. Основы Ethernet.

Субтитры

Программный стек

Организация в памяти

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

Но также часто стек располагается в одномерном массиве с упорядоченными адресами. Такая организация стека удобна, если элемент информации занимает в памяти фиксированное количество слов, например, 1 слово. При этом отпадает необходимость хранения в элементе стека явного указателя на следующий элемент стека, что экономит память. При этом указатель стека (Stack Pointer , - SP ) обычно является регистром процессора и указывает на адрес головы стека.

Предположим для примера, что голова стека расположена по меньшему адресу, следующие элементы располагаются по нарастающим адресам. При каждом вталкивании слова в стек, SP сначала уменьшается на 1 и затем по адресу из SP производится запись в память. При каждом извлечении слова из стека (выталкивании) сначала производится чтение по текущему адресу из SP и последующее увеличение содержимого SP на 1.

При организации стека в виде однонаправленного списка значением переменной стека является указатель на его вершину - адрес вершины. Если стек пуст, то значение указателя равно NULL.

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

struct stack { char * data ; struct stack * next ; };

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

Возможны три операции со стеком: добавление элемента (иначе проталкивание, push ), удаление элемента (pop ) и чтение головного элемента (peek ) .

При проталкивании (push ) добавляется новый элемент, указывающий на элемент, бывший до этого головой. Новый элемент теперь становится головным.

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

void push ( STACK * ps , int x ) // Добавление в стек нового элемента { if ( ps -> size == STACKSIZE ) // Не переполнен ли стек? { fputs ( "Error: stack overflow \n " , stderr ); abort (); } else { ps -> items [ ps -> size ++ ] = x ; } } int pop ( STACK * ps ) // Удаление из стека { if ( ps -> size == 0 ) // Не опустел ли стек? { fputs ( "Error: stack underflow \n " , stderr ); abort (); } else { return ps -> items [ -- ps -> size ]; } }

Область применения

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

Аналогичные процессы происходят при аппаратном прерывании (процессор X86 при аппаратном прерывании сохраняет автоматически в стеке ещё и регистр флагов). Кроме того, компиляторы размещают локальные переменные процедур в стеке (если в процессоре предусмотрен доступ к произвольному месту стека).

До использования стека он должен быть инициализирован так, чтобы регистры SS:ESP указывали на адрес головы стека в области физической оперативной памяти, причем под хранение данных в стеке необходимо зарезервировать нужное количество ячеек памяти (очевидно, что стек в ПЗУ , естественно, не может быть организован). Прикладные программы, как правило, от операционной системы получают готовый к употреблению стек. В защищенном режиме работы процессора сегмент состояния задачи содержит четыре селектора сегментов стека (для разных уровней привилегий), но в каждый момент используется только один стек .

(англ. last in - first out , «последним пришёл - первым вышел»).

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

В некоторых языках (например, Lisp , Python ) стеком можно назвать любой список, так как для них доступны операции pop и push. В языке C++ стандартная библиотека имеет класс с реализованной структурой и методами . И т. д.

Программный стек

Организация в памяти

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

Но также часто стек располагается в одномерном массиве с упорядоченными адресами. Такая организация стека удобна, если элемент информации занимает в памяти фиксированное количество слов, например, 1 слово. При этом отпадает необходимость хранения в элементе стека явного указателя на следующий элемент стека, что экономит память. При этом указатель стека (Stack Pointer , - SP ) обычно является регистром процессора и указывает на адрес головы стека.

Предположим для примера, что голова стека расположена по меньшему адресу, следующие элементы располагаются по нарастающим адресам. При каждом вталкивании слова в стек, SP сначала уменьшается на 1 и затем по адресу из SP производится запись в память. При каждом извлечении слова из стека (выталкивании) сначала производится чтение по текущему адресу из SP и последующее увеличение содержимого SP на 1.

При организации стека в виде однонаправленного списка значением переменной стека является указатель на его вершину - адрес вершины. Если стек пуст, то значение указателя равно NULL.

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

struct stack { char * data ; struct stack * next ; };

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

Возможны три операции со стеком: добавление элемента (иначе проталкивание, push ), удаление элемента (pop ) и чтение головного элемента (peek ) .

При проталкивании (push ) добавляется новый элемент, указывающий на элемент, бывший до этого головой. Новый элемент теперь становится головным.

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

void push ( STACK * ps , int x ) // Добавление в стек нового элемента { if ( ps -> size == STACKSIZE ) // Не переполнен ли стек? { fputs ( "Error: stack overflow \n " , stderr ); abort (); } else { ps -> items [ ps -> size ++ ] = x ; } } int pop ( STACK * ps ) // Удаление из стека { if ( ps -> size == 0 ) // Не опустел ли стек? { fputs ( "Error: stack underflow \n " , stderr ); abort (); } else { return ps -> items [ -- ps -> size ]; } }

Область применения

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

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

Идея стека используется в стековой машине среди стековых языков программирования .

Применение стека упрощает и ускоряет работу программы, так как идет обращение к нескольким данным по одному адресу.

Аппаратный стек

До использования стека он должен быть инициализирован так, чтобы регистры SS:ESP указывали на адрес головы стека в области физической оперативной памяти, причём под хранение данных в стеке необходимо зарезервировать нужное количество ячеек памяти (очевидно, что стек в ПЗУ , естественно, не может быть организован). Прикладные программы, как правило, от операционной системы получают готовый к употреблению стек. В защищённом режиме работы процессора сегмент состояния задачи содержит четыре селектора сегментов стека (для разных уровней привилегий), но в каждый момент используется только один стек .

Примечания

1. Машина Тьюринга: Введение (неопр.) . Проверено 12 февраля 2013.

Теги: Стек, стек на си, реализация стека, стек на массиве, динамически растущий стек, стек на односвязном сиске

Стек

С тек – наверное, самая простая структура данных, которую мы будем изучать и которой будем постоянно пользоваться. Стек – это структура данных, в которой элементы поддерживают принцип LIFO (“Last in – first out”): последним зашёл – первым вышел. Или первым зашёл – последним вышел.

Стек позволяет хранить элементы и поддерживает, обычно, две базовые операции:

• PUSH – кладёт элемент на вершину стека
• POP – снимает элемент с вершины стека, перемещая вершину к следующему элементу

Также часто встречается операция PEEK, которая получает элемент на вершине стека, но не снимает его оттуда.

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

Пусть, например, у нас есть стек чисел. Выполним несколько команд. Изначально стек пуст. Вершина стека – указатель на первый элемент, никуда не указывает. В случае си она может быть равна NULL.

Теперь стек состоит из одного элемента, числа 3. Вершина стека указывает на число 3.

Стек состоит из двух элементов, 5 и 3, при этом вершина стека указывает на 5.

Стек состоит из трёх элементов, вершина стека указывает на 7.

Вернёт значение 7, в стеке останется 5 и 3. Вершина будет указывать на следующий элемент – 5.

Вернёт 5, в стеке останется всего один элемент, 3, на который будет указывать вершина стека.

Вернёт 3, стек станет пуст.

Часто сравнивают стек со стопкой тарелок. Чтобы достать следующую тарелку, необходимо снять предыдущие. Вершина стека – это вершина стопки тарелок.

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

• 1. Stack Underflow: Попытка снять элемент с пустого стека
• 2. Stack Overflow: Попытка положить новый элемент на стек, который не может больше расти (например, не хватает оперативной памяти)

Программная реализация

Р ассмотрим три простые реализации стека:

Стек фиксированного размера, построенный на массиве

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

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

#define STACK_MAX_SIZE 20 typedef int T;

Теперь сама структура

Typedef struct Stack_tag { T data; size_t size; } Stack_t;

Здесь переменная size – это количество элементов, и вместе с тем указатель на вершину стека. Вершина будет указывать на следующий элемент массива, в который будет занесено значение.

Кладём новый элемент на стек.

Void push(Stack_t *stack, const T value) { stack->data = value; stack->size++; }

Единственная проблема – можно выйти за пределы массива. Поэтому всегда надо проверять, чтобы не было ошибки Stack overflow:

#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 void push(Stack_t *stack, const T value) { if (stack->size >= STACK_MAX_SIZE) { exit(STACK_OVERFLOW); } stack->data = value; stack->size++; }

Аналогично, определим операцию Pop, которая возвращает элемент с вершины и переходит к следующему

T pop(Stack_t *stack) { if (stack->size == 0) { exit(STACK_UNDERFLOW); } stack->size--; return stack->data; }

И функция peek, возвращающая текущий элемент с вершины

T peek(const Stack_t *stack) { if (stack->size <= 0) { exit(STACK_UNDERFLOW); } return stack->data; }

Ещё одно важное замечание – у нас нет функции создания стека, поэтому необходимо вручную обнулять значение size

Вспомогательные функции для печати элементов стека

Void printStackValue(const T value) { printf("%d", value); } void printStack(const Stack_t *stack, void (*printStackValue)(const T)) { int i; int len = stack->size - 1; printf("stack %d > ", stack->size); for (i = 0; i < len; i++) { printStackValue(stack->data[i]); printf(" | "); } if (stack->size != 0) { printStackValue(stack->data[i]); } printf("\n"); }

Заметьте, что в функции печати мы использует int, а не size_t, потому что значение len может стать отрицательным. Функция печатает сначала размер стека, а потом его содержимое, разделяя элементы символом |

Проверка

Stack_t stack; stack.size = 0; push(&stack, 3); printStack(&stack, printStackValue); push(&stack, 5); printStack(&stack, printStackValue); push(&stack, 7); printStack(&stack, printStackValue); printf("%d\n", pop(&stack)); printStack(&stack, printStackValue); printf("%d\n", pop(&stack)); printStack(&stack, printStackValue); printf("%d\n", pop(&stack)); printStack(&stack, printStackValue); _getch();

Рассмотрим также ситуации, когда есть ошибки использования. Underflow

Void main() { Stack_t stack; stack.size = 0; push(&stack, 3); pop(&stack); pop(&stack); _getch(); }

Void main() { Stack_t stack; size_t i; stack.size = 0; for (i = 0; i < 100; i++) { push(&stack, i); } _getch(); }

Динамически растущий стек на массиве

Д инамически растущий стек используется в том случае, когда число элементов может быть значительным и не известно на момент решения задачи. Максимальный размер стека может быть ограничен каким-то числом, либо размером оперативной памяти.

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

Typedef struct Stack_tag { T *data; size_t size; size_t top; } Stack_t;

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

#define INIT_SIZE 10

Алгоритм работы такой: мы проверяем, не превысило ли значение top значение size. Если значение превышено, то увеличиваем размер массива. Здесь возможно несколько вариантов того, как увеличивать массив. Можно прибавлять число, можно умножать на какое-то значение. Какой из вариантов лучше, зависит от специфики задачи. В нашем случае будем умножать размер на число MULTIPLIER

#define MULTIPLIER 2

Максимального размера задавать не будем. Программа будет выпадать при stack overflow или stack underflow. Будем реализовывать тот же интерфейс (pop, push, peek). Кроме того, так как массив динамический, сделаем некоторые вспомогательные функции, чтобы создавать стек, удалять его и чистить.

Во-первых, функции для создания и удаления стека и несколько ошибок

#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 #define OUT_OF_MEMORY -102 Stack_t* createStack() { Stack_t *out = NULL; out = malloc(sizeof(Stack_t)); if (out == NULL) { exit(OUT_OF_MEMORY); } out->size = INIT_SIZE; out->data = malloc(out->size * sizeof(T)); if (out->data == NULL) { free(out); exit(OUT_OF_MEMORY); } out->top = 0; return out; } void deleteStack(Stack_t **stack) { free((*stack)->data); free(*stack); *stack = NULL; }

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

Теперь напишем вспомогательную функцию изменения размера.

Void resize(Stack_t *stack) { stack->size *= MULTIPLIER; stack->data = realloc(stack->data, stack->size * sizeof(T)); if (stack->data == NULL) { exit(STACK_OVERFLOW); } }

Здесь, заметим, в случае, если не удалось выделить достаточно памяти, будет произведён выход с STACK_OVERFLOW.

Функция push проверяет, вышли ли мы за пределы массива. Если да, то увеличиваем его размер

Void push(Stack_t *stack, T value) { if (stack->top >= stack->size) { resize(stack); } stack->data = value; stack->top++; }

Функции pop и peek аналогичны тем, которые использовались для массива фиксированного размера

T pop(Stack_t *stack) { if (stack->top == 0) { exit(STACK_UNDERFLOW); } stack->top--; return stack->data; } T peek(const Stack_t *stack) { if (stack->top <= 0) { exit(STACK_UNDERFLOW); } return stack->data; }

Проверим

Void main() { int i; Stack_t *s = createStack(); for (i = 0; i < 300; i++) { push(s, i); } for (i = 0; i < 300; i++) { printf("%d ", peek(s)); printf("%d ", pop(s)); } deleteStack(&s); _getch(); }

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

Void implode(Stack_t *stack) { stack->size = stack->top; stack->data = realloc(stack->data, stack->size * sizeof(T)); }

Можем использовать в нашем случае

For (i = 0; i < 300; i++) { push(s, i); } implode(s); for (i = 0; i < 300; i++) { printf("%d ", peek(s)); printf("%d ", pop(s)); }

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

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

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

Ч то такое односвязный список, . Коротко: односвязный список состоит из узлов, каждый из которых содержит полезную информацию и ссылку на следующий узел. Последний узел ссылается на NULL.

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

#define STACK_OVERFLOW -100 #define STACK_UNDERFLOW -101 #define OUT_OF_MEMORY -102 typedef int T; typedef struct Node_tag { T value; struct Node_tag *next; } Node_t;

Функция вставки первого элемента проста: создаём новый узел. Указатель next кидаем на старый узел. Далее указатель на вершину стека перекидываем на вновь созданный узел. Теперь вершина стека указывает на новый узел.

Void push(Node_t **head, T value) { Node_t *tmp = malloc(sizeof(Node_t)); if (tmp == NULL) { exit(STACK_OVERFLOW); } tmp->next = *head; tmp->value = value; *head = tmp; }

Функция pop берёт первый элемент (тот, на который указывает вершина), перекидывает указатель на следующий элемент и возвращает первый. Здесь есть два варианта – можно вернуть узел или значение. Если вернём значение, то придётся удалять узел внутри функции

Node_t* pop1(Node_t **head) { Node_t *out; if ((*head) == NULL) { exit(STACK_UNDERFLOW); } out = *head; *head = (*head)->next; return out; }

T pop2(Node_t **head) { Node_t *out; T value; if (*head == NULL) { exit(STACK_UNDERFLOW); } out = *head; *head = (*head)->next; value = out->value; free(out); return value; }

Теперь вместо проверки на длину массива везде используется проверка на равенство NULL вершины стека.

Простая функция peek

T peek(const Node_t* head) { if (head == NULL) { exit(STACK_UNDERFLOW); } return head->value; }

Итерирование достаточно интересное. Просто переходим от одного узла к другому, пока не дойдём до конца

Void printStack(const Node_t* head) { printf("stack >"); while (head) { printf("%d ", head->value); head = head->next; } }

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

Size_t getSize(const Node_t *head) { size_t size = 0; while (head) { size++; head = head->next; } return size; }

Конечно, можно хранить размер отдельно, можно обернуть стек со всеми данными ещё в одну структуру и т.д. Рассмотрим всё это при более подробном изучении списков.

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

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

сегмент 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; }

Стек - это коллекция, элементы которой получают по принципу «последний вошел, первый вышел» (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; } }

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

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