Как очистить stack c
(англ. ) называется хранилище данных, в котором можно работать только с одним элементом: тем, который был добавлен в стек последним. Стек должен поддерживать следующие операции: push Добавить (положить) в конец стека новый элемент
pop Извлечь из стека последний элемент
back Узнать значение последнего элемента (не удаляя его)
size Узнать количество элементов в стеке
clear Очистить стек (удалить из него все элементы)
Хранить элементы стека мы будем в массиве. Для начала будем считать, что максимальное количество элементов в стеке не может превосходить константы MAX_SIZE , тогда для хранения элементов массива необходимо создать массив размера MAX_SIZE .
Объявим структуру данных типа stack .
const int MAX_SIZE=1000; struct stack < int m_size; // Количество элементов в стеке int m_elems[MAX_SIZE]; // Массив для хранения элементов stack(); // Конструктор ~stack(); // Деструктор void push(int d); // Добавить в стек новый элемент int pop(); // Удалить из стека последний элемент // и вернуть его значение int back(); // Вернуть значение последнего элемента int size(); // Вернуть количество элементов в стеке void clear(); // Очистить стек >;
Объявленная здесь структура данных stack реализует стек целых чисел. Поле структуры m_size хранит количество элементов в стеке в настоящее время, сами элементы хранятся в элементах массива m_elems с индексами 0.. m_size-1 . Элементы, добавленные позже, получают большие номера.
Упражнение A — простой стек
Реализуйте структуру данных «стек», релизовав все указанные здесь методы. Напишите программу (функцию main ), содержащую описание стека и моделирующую работу стека. Функция main считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения одной команды программа должна вывести одну строчку. Возможные команды для программы: push n Добавить в стек число n (значение n задается после команды). Программа должна вывести ok .
pop Удалить из стека последний элемент. Программа должна вывести его значение.
back Программа должна вывести значение последнего элемента, не удаляя его из стека.
size Программа должна вывести количество элементов в стеке.
clear Программа должна очистить стек и вывести ok .
exit Программа должна вывести bye и завершить работу.
Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в стеке в любой момент не превосходит 100, все команды pop_back и back корректны, то есть при их исполнении в стеке содержится хотя бы один элемент.
Пример протокола работы программы
Ввод Вывод push 2 ok push 3 ok push 5 ok back 5 size 3 pop 5 size 2 push 7 ok pop 7 clear ok size 0 exit bye
Упражнение B — стек с обработкой ошибок
Аналогично предыдущему заданию, только снимается ограничение на корректность вызовов методов back и pop . Данные операции должны перед исполнением проверять, содержится ли в стеке хотя бы один элемент. Если во входных данных встречается операция back или pop , при этом стек пуст, то программа должна вместо числового значения вывести строку error .
При этом должна быть реализована двойная защита: вызов методов forward и pop для пустого стека не должен приводить к обращению к несуществующим элементам массива m_elems , а функция main должна выводить сообщение error , при считывании некорректной операции.
Пример протокола работы программы
Ввод Вывод push 2 ok back 2 pop 2 size 0 pop error push 1 ok size 1 exit bye
Упражнение C — стек без ограничения на размер
Реализуйте стек динамического размера, то есть ограниченный только объемом свободной оперативной памяти. Для этого используйте указатели и динамически распределяемую память. Если для полностью заполненного стека вызывается метод push размер динамического массива, отведенного для хранения стека, должен увеличиваться.
Очередь
Очередью (aнгл. )) называется структура данных, в которой элементы кладутся в конец, а извлекаются из начала. Таким образом, первым из очереди будет извлечен тот элемент, который будет добавлен раньше других.
Элементы очереди будем также хранить в массиве. При этом из очереди удаляется первый элемент, и, чтобы не сдвигать все элементы очереди, будем в отдельном поле m_start хранить индекс элемента массива, с которого начинается очередь. При удалении элементов, очередь будет «ползти» дальше от начала массива. Чтобы при этом не происходил выход за границы массива, замкнем массив в кольцо: будем считать, что за последним элементом массива следует первый.
Описание структуры очередь:
const int MAX_SIZE=1000; struct queue < int m_size; // Количество элементов в очереди int m_start; // Номер элемента, с которого начинается очередь int m_elems[MAX_SIZE]; // Массив для хранения элементов queue(); // Конструктор ~queue(); // Деструктор void push(int d); // Добавить в очередь новый элемент int pop(); // Удалить из очереди первый элемент // и вернуть его значение int front(); // Вернуть значение первого элемента int size(); // Вернуть количество элементов в очереди void clear(); // Очистить стек >;
Упражнение D — простая очередь
Реализуйте простейшую очередь, размер которой не превосходит 100 элементов. Очередь поддерживает те же операции, что и стек, за исключением операции back , которая заменена операцией front . Операции front и pop всегда корректны.
Упражнение E — очередь с обработкой ошибок
Аналогично заданию B, но для очереди. Операции front и pop могут быть некорректными, в этом случае необходимо вывести error .
Программа должна содержать «двойную защиту» от некорректных операций: как в функции main , так и в самих методах pop и front .
Упражнение F — очередь без ограничений на размер
Аналогично заданию C, но для очереди. Необходимо реализовать очередь, память для которой динамически выделяется при увеличении количества элементов в ней.
Дек
Деком (англ. – аббревиатура от double-ended queue, двухсторонняя очередь) называется структура данных, в которую можно удалять и добавлять элементы как в начало, так и в конец. Дек хранится в памяти так же, как и очередь. Система команд дека: push_front Добавить (положить) в начало дека новый элемент
push_back Добавить (положить) в конец дека новый элемент
pop_front Извлечь из дека первый элемент
pop_back Извлечь из дека последний элемент
front Узнать значение первого элемента (не удаляя его)
back Узнать значение последнего элемента (не удаляя его)
size Узнать количество элементов в деке
clear Очистить дек (удалить из него все элементы)
Упражнение G — простой дек
Аналогично заданиям A и D, но для дека. Количество элементов в деке в любой момент не превосходит 100. Все операции pop_front , pop_back , front , back всегда корректны.
Упражнение H — дек с обработкой ошибок
Аналогично заданиям B и E, но для дека. Количество элементов в деке в любой момент не превосходит 100. При выполнении некорректных операций необходимо вывести error .
Упражнение I — дек неограниченного размера
Аналогично заданиям C и F, но для дека. Необходимо увеличивать размер дека при увеличении числа элементов в нем. При выполнении некорректных операций необходимо вывести error .
Исключения и освобождение стека в C++
В механизме исключений C++ элемент управления перемещается из оператора throw в первый оператор catch, который может обработать выданный тип. По достижении инструкции catch все автоматические переменные, которые находятся в область между операторами бросить и перехватом, уничтожаются в процессе очистки стека. При очистке стека выполнение продолжается следующим образом.
- Элемент управления достигает инструкции по обычному последовательному try выполнению. Выполняется защищенный раздел в блоке try .
- Если исключение не возникает во время выполнения защищенного раздела, предложения, следовать за try блоком, catch не выполняются. Выполнение продолжается в инструкции после последнего catch предложения, следующего за связанным try блоком.
- Если исключение создается во время выполнения защищенного раздела или в любой подпрограмме, вызываемой защищенным разделом напрямую или косвенно, создается объект исключения из объекта, созданного операндом throw . (Это означает, что конструктор копирования может быть вовлечен.) На этом этапе компилятор ищет catch предложение в более высоком контексте выполнения, которое может обрабатывать исключение создаваемого типа или catch обработчика, который может обрабатывать любой тип исключения. Обработчики catch проверяются в порядке их внешнего вида после try блока. Если соответствующий обработчик не найден, проверяется следующий динамически заключенный try блок. Этот процесс продолжается до тех пор, пока не будет рассмотрен самый внешний заключиющий try блок.
- Если соответствующий обработчик по-прежнему не найден или исключение возникает во время процесса очистки до получения элемента управления обработчиком, вызывается предопределенная функция времени выполнения terminate . Если исключение возникает после создания исключения, но до начала процесса очистки, вызывается функция terminate .
- Если соответствующий обработчик найден, и он перехватывается по значению, его формальный catch параметр инициализируется путем копирования объекта исключения. Если обработчик выполняет перехват по ссылке, параметр инициализируется для ссылки на объект исключения. После инициализации формального параметра начинается процесс очистки стека. Это включает в себя уничтожение всех автоматических объектов, которые были полностью созданы , но еще не деструированы, между началом try блока, связанного с catch обработчиком и сайтом создания исключения. Удаление происходит в порядке, обратном созданию. Обработчик catch выполняется, и программа возобновляет выполнение после последнего обработчика, то есть при первой инструкции или конструкции, которая не является обработчиком catch . Элемент управления может вводить catch обработчик только через исключение, вызываемое исключение, никогда не с помощью goto инструкции или case метки в инструкции switch .
Пример очистки стека
В следующем примере показано, как очистить стек при создании исключения. Выполнение потока переходит от оператора throw в C к оператору catch в main , и при этом удаляются все функции. Обратите внимание, что порядок создания и удаления объектов Dummy соответствует порядку их выхода из области видимости. Также обратите внимание, что завершается выполнение только функции main , содержащей оператор catch. Функция A никогда не возвращается после вызова B() , и B никогда не возвращается после вызова C() . Обратите внимание, что если раскомментировать определение указателя Dummy и соответствующую инструкцию DELETE, а затем запустить программу, указатель не удаляется. Это показывает, что может произойти, если функции не предоставляют гарантию исключения. Дополнительные сведения см. в разделе «Практическое руководство . Проектирование исключений». Если закомментировать оператор catch, можно наблюдать за тем, что происходит при завершении выполнения программы в результате необработанного исключения.
#include #include using namespace std; class MyException<>; class Dummy < public: Dummy(string s) : MyName(s) < PrintMsg("Created Dummy:"); >Dummy(const Dummy& other) : MyName(other.MyName) < PrintMsg("Copy created Dummy:"); >~Dummy() < PrintMsg("Destroyed Dummy:"); >void PrintMsg(string s) < cout string MyName; int level; >; void C(Dummy d, int i) < cout void B(Dummy d, int i) < cout void A(Dummy d, int i) < cout int main() < cout catch (MyException& e) < cout cout > c; > /* Output: Entering main Created Dummy: M Copy created Dummy: M Entering FunctionA Copy created Dummy: A Entering FunctionB Copy created Dummy: B Entering FunctionC Destroyed Dummy: C Destroyed Dummy: B Destroyed Dummy: A Destroyed Dummy: M Caught an exception of type: class MyException Exiting main. */ Стек
С тек – наверное, самая простая структура данных, которую мы будем изучать и которой будем постоянно пользоваться. Стек – это структура данных, в которой элементы поддерживают принцип 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: Попытка положить новый элемент на стек, который не может больше расти (например, не хватает оперативной памяти)
Программная реализация
- 1) Стек фиксированного размера на массиве
- 2) Динамически растущий стек на массиве
- 3) Динамически растущий стек на односвязном списке
Стек фиксированного размера, построенный на массиве
О тличительная особенность – простота реализации и максимальная скорость выполнения. Такой стек может применяться в том, случае, когда его максимальный размер известен заранее или известно, что он мал.
Сначала определяем максимальный размер массива и тип данных, которые будут в нём храниться:
#define STACK_MAX_SIZE 20 typedef int T;
Теперь сама структура
typedef struct Stack_tag < T data[STACK_MAX_SIZE]; size_t size; >Stack_t;
Здесь переменная size – это количество элементов, и вместе с тем указатель на вершину стека. Вершина будет указывать на следующий элемент массива, в который будет занесено значение.
Кладём новый элемент на стек.
void push(Stack_t *stack, const T value) < stack->data[stack->size] = 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[stack->size] = value; stack->size++; >
Аналогично, определим операцию Pop, которая возвращает элемент с вершины и переходит к следующему
T pop(Stack_t *stack) < if (stack->size == 0) < exit(STACK_UNDERFLOW); >stack->size--; return stack->data[stack->size]; >
И функция peek, возвращающая текущий элемент с вершины
T peek(const Stack_t *stack) < if (stack->size return stack->data[stack->size - 1]; >
Ещё одно важное замечание – у нас нет функции создания стека, поэтому необходимо вручную обнулять значение 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()
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[stack->top] = value; stack->top++; >
Функции pop и peek аналогичны тем, которые использовались для массива фиксированного размера
T pop(Stack_t *stack) < if (stack->top == 0) < exit(STACK_UNDERFLOW); >stack->top--; return stack->data[stack->top]; > T peek(const Stack_t *stack) < if (stack->top return stack->data[stack->top - 1]; >
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
Эта однопоточная реализация стека использует мало обращений к памяти, достаточно проста и универсальна, работает быстро и может быть реализована, при необходимости, за несколько минут. Она используется всегда в дальнейшем, если не указано иное.
У неё есть недостаток, связанный с методом увеличения потребляемой памяти. При умножении в 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; >
Конечно, можно хранить размер отдельно, можно обернуть стек со всеми данными ещё в одну структуру и т.д. Рассмотрим всё это при более подробном изучении списков.
void main() < int i; Node_t *head = NULL; for (i = 0; i < 300; i++) < push(&head, i); >printf("size = %d\n", getSize(head)); while (head) < printf("%d ", peek(head)); printf("%d ", pop2(&head)); >_getch(); >
void main() < int i; Node_t *head = NULL; Node_t *tmp; for (i = 0; i < 300; i++) < push(&head, i); >printf("size = %d\n", getSize(head)); while (head) < printf("%d ", peek(head)); tmp = pop1(&head); printf("%d ", tmp->value); free(tmp); > _getch(); >
ru-Cyrl 18- tutorial Sypachev S.S. 1989-04-14 sypachev_s_s@mail.ru Stepan Sypachev students
Всё ещё не понятно? – пиши вопросы на ящик
Как очистить stack c
Класс Stack представляет коллекцию, которая использует алгоритм LIFO («последний вошел — первый вышел»). При такой организации каждый следующий добавленный элемент помещается поверх предыдущего. Извлечение из коллекции происходит в обратном порядке — извлекается тот элемент, который находится выше всех в стеке.
Стек — довольно часто встречаемая структура данных в реальной жизни. Банальные примеры стеков — стопка книг или тарелок, где каждую новую книгу или тарелку помещают поверх предыдущей. А извлекают из этой стопки книги/тарелки в обратном порядке — сначала самую верхнюю и так далее. Другой пример — одежда: допустим, человек выходит на улицу в зимнюю погоду и для этого сначала одевает майку, потом рубашку, затем свитер, и в конце куртку. Когда человек снимает с себя одежду — он делает это в обратном порядке: сначала снимает куртку, потом свитер и так далее.
Создание стека
Для создания стека можно использовать один из трех конструкторов. Прежде всего можно создать пустой стек:
Stack people = new Stack();
При создании пустого стека можно указать емкость стека:
Stack people = new Stack(16);
Также можно инициализировать стек элементами из другой коллекции или массивом:
var employees = new List < "Tom", "Sam", "Bob" >; Stack people = new Stack(employees); foreach (var person in people) Console.WriteLine(person); Console.WriteLine(people.Count); // 3
Для перебора стека можно использовать стандартный цикл foreach . Причем в цикле в соответствии с аалгоритмом стека LIFO данные извлекаются в порядке, обратном их добавлению. Консольный вывод в данном случае:
Bob Sam Tom 3
Для получения количества элементов стека применяется свойство Count .
Методы Stack
В классе Stack можно выделить следующие методы:
- Clear : очищает стек
- Contains : проверяет наличие в стеке элемента и возвращает true при его наличии
- Push : добавляет элемент в стек в верхушку стека
- Pop : извлекает и возвращает первый элемент из стека
- Peek : просто возвращает первый элемент из стека без его удаления
Посмотрим на примере:
var people = new Stack(); people.Push("Tom"); // people = < Tom >people.Push("Sam"); // people = < Sam, Tom >people.Push("Bob"); // people = < Bob, Sam, Tom >// получаем первый элемент стека без его удаления string headPerson = people.Peek(); Console.WriteLine(headPerson); // Bob string person1 = people.Pop(); // people = < Sam, Tom >Console.WriteLine(person1); // Bob string person2 = people.Pop(); // people = < Tom >Console.WriteLine(person2); // Sam string person3 = people.Pop(); // people = < >Console.WriteLine(person3); // Tom
Работу стека можно представить следующей иллюстрацией:
Стоит отметить, что если с помощью методов Peek или Pop мы попытаемся получить первый элемент стека, который пуст, то программа выдаст исключение. Соответственно перед получением элемента мы можем проверять количество элементов в стеке:
if(people.Count > 0)
Либо можно использовать пару методов:
- bool TryPop(out T result) : удаляет из стека первый элемент и передает его в переменную result, возвращает true , если очередь не пуста и элемент успешно получен.
- bool TryPeek(out T result) : передает в переменную result первый элемент стека без его извлечения, возвращает true , если элемент успешно получен.
var people = new Stack(); people.Push("Tom"); // people = < Tom >// удаляем элементы var success1 = people.TryPop(out var person1); // success1 = true if (success1) Console.WriteLine(person1); // Tom var success2 = people.TryPeek(out var person2); // success2 = false if (success2) Console.WriteLine(person2);