Foreversoft.ru

IT Справочник
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Стек в си шарп

Стек: классы Stack и Stack

— это контейнер, работающий по принципу «последний вошел, первый вышел» (last in, first out — LIFO). На рисунке показано представление стека, где метод Push() добавляет элемент, а метод Pop() — получает элемент, добавленный последним:

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

В классе Stack определяются следующие конструкторы:

В первой форме конструктора создается пустой стек, во второй форме — пустой стек, первоначальный размер которого определяет первоначальная емкость, задаваемая параметром initialCapacity, и в третьей форме — стек, содержащий элементы указываемой коллекции col. Его первоначальная емкость равна количеству указанных элементов.

В классе Stack определяется ряд собственных методов, помимо тех, что уже объявлены в интерфейсах, которые в нем реализуются. Некоторые из наиболее часто используемых методов этого класса приведены ниже. Эти методы обычно применяются следующим образом. Для того чтобы поместить объект на вершине стека, вызывается метод Push(). А для того чтобы извлечь и удалить объект из вершины стека, вызывается метод Pop(). Если же объект требуется только извлечь, но не удалить из вершины стека, то вызывается метод Peek(). А если вызвать метод Pop() или Peek(), когда вызывающий стек пуст, то сгенерируется исключение InvalidOperationException.

Класс Stack является обобщенным эквивалентом класса необобщенной коллекции Stack. В нем поддерживается стек в виде списка, действующего по принципу «первым пришел — последним обслужен». В этом классе реализуются интерфейсы Collection, IEnumerable и IEnumerable . Кроме того, в классе Stack непосредственно реализуются методы Clear(), Contains() и СоруТо(), определенные в интерфейсе ICollection . А методы Add() и Remove() в этом классе не поддерживаются, как, впрочем, и свойство IsReadOnly. Коллекция класса Stack имеет динамический характер, расширяясь по мере необходимости, чтобы вместить все элементы, которые должны в ней храниться.

Count

Свойство Count возвращает количество элементов в стеке.

Push()

Метод Push() добавляет элемент в вершину стека.

Pop()

Метод Pop() удаляет и возвращает элемент из вершины стека. Если стек пуст, генерируется исключение типа InvalidOperationException.

Peek()

Метод Peek() возвращает элемент из вершины стека, не удаляя его при этом.

Contains()

Метод Contains() проверяет наличие элемента в стеке и возвращает true в случае нахождения его там.

Стек в си шарп

Стек(stack) — это абстрактная структура данных, в которой элементы организованы по принципу LIFO(Last In First Out — “пришел последним, вышел первым”).

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

Алгоритм работы стека, в самой простой реализации, следующий:

  • каждый новый элемент добавляется в вершину стека при этом все последующие элементы смещаются на одну позицию вниз;
  • мы можем получить из стека только элемент расположенный в вершине(его также называют головным элементом), при этом он удаляется из стека, а последующие — смещаются на позицию вверх;
Читать еще:  Синус в си шарп

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

В библиотеке System.Collections.Generic языка C#, уже есть реализация .Net класса Stack, однако для понимания устройства этой структуры данных, напишем свою реализацию стека.

Стандартно для стека реализуют три операции:

  • Push — метод добавления нового элемента в вершину;
  • Pop — чтение элемента с его удалением;
  • Peek — чтение головного элемента без удаления из стека.

Мы добавим к этим операциям следующие:

  • Size — получение размера структуры stack;
  • Clear — метод для очистки стека.

Стек на основе массива

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

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

При необходимости можно переписать метод RebuildData таким образом, чтобы он изменял размер массива если значения не помещаются:

Пример использования фиксированного стека

В результате выполнения программа выведет на экран 5 последних добавленных имен:

Стек на основе списка(List)

Для хранения данных стека, будем использовать коллекцию List из стандартной библиотеки платформы .Net System.Collections.Generic.

Используя List для хранения данных, у нас нет необходимости следить за количеством объектов помещенных в стек, как это было в классе с массивом. Список автоматически расширяется при добавлении новых значений.

Стек. Пример обобщенной коллекции

Стек (stack) — это коллекция, в которой элементы обрабатываются по схеме «последним вошел, первым вышел» (last in, first out — LIFO).

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

Принципиальное отличие от очереди (FIFO-список) — в первой букве.
Примеры стеков: стопка тяжелых книг (добавлять и убирать можем только по одной книге), несколько патронов в магазине автомата — стрелкового оружия, стек как сегмент оперативной памяти компьютера (не куча!), см. примечание к статье Типы данных.

Краткие сведения и пример программы:

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

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

Стек реализуется с помощью классов Stack из пространства имен System.Collections и Stack из пространства имен System.Collections.Generic (в нашем примере).

В классе Stack определяются приведенные ниже конструкторы:
public Stack()
public Stack(int initialCapacity)
public Stack(ICollection collect)
В первой форме конструктора создается пустой стек, во второй форме — пустой стек, первоначальный размер которого определяет первоначальная емкость, задаваемая параметром initialCapacity, и в третьей форме — стек, содержащий элементы указываемой коллекции collect. Его первоначальная емкость равна количеству указанных элементов.

Читать еще:  Обучение си шарп

В классе Stack определяется ряд собственных методов, помимо тех, что уже объявлены в интерфейсах, которые в нем реализуются.
Некоторые из наиболее часто используемых методов этого класса приведены ниже.
Для помещения объекта в вершину стека, вызывается метод Push().
Для того чтобы извлечь и удалить объект из вершины стека, вызывается метод Pop().
Если же объект требуется только извлечь, но не удалить из вершины стека, то вызывается метод Peek().
А если вызвать метод Pop() или Peek(), когда вызывающий стек пуст, то сгенерируется исключение InvalidOperationException.

Класс Stack является обобщенным эквивалентом класса необобщенной коллекции Stack.
В нем поддерживается стек из элементов типа Т в виде списка, действующего по принципу LIFO.
В этом классе реализуются интерфейсы Collection, IEnumerable и IEnumerable .
Кроме того, в классе Stack непосредственно реализуются методы Clear(), Contains() и СоруТо(), определенные в интерфейсе ICollection .
Mетоды Add() и Remove() в этом классе не поддерживаются, достаточно методов Push() и Рор().
Коллекция класса Stack имеет динамический характер, расширяясь по мере необходимости, чтобы вместить все элементы, которые должны в ней храниться.

Давайте рассмотрим пример стека:

Для проверки ошибки при извлечении элемента из пустого стека уберите комментарий в предпоследнем операторе.

Стек в си шарп

На 39 уроке учебника C# для начинающих рассматривается класс Stack. Эта коллекция включает в себя функциональные возможности, требуемые в структуре стекирования «Last In, First Out» (LIFO, последним пришёл — первым ушёл). Стеки позволяют хранить предметы для последующего извлечения и обработки.

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

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

Платформа .NET framework включает класс Stack. Он обеспечивает все функциональные возможности, необходимые для работы стеков LIFO без дополнительного кода. Класс Stack предоставляет простую коллекцию, которая может содержать любой тип объекта, включая дубликаты и значения null.

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

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

Читать еще:  Язык паскаль с нуля

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

Третий конструктор позволяет создать предварительно заполненный стек, содержащий объекты из любого класса, реализующего ICollection .

Стеки позволяют добавлять новые элементы в верхнюю часть стека, а затем извлекать их в обратном порядке. Чтобы добавить новый элемент в верхнюю часть стека, используйте метод Push. Этот метод принимает один параметр, являющийся объектом для добавления в стек.

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

Иногда необходимо получить следующий элемент в стеке, не удаляя его из коллекции. Метод Peek используется таким же образом, как и Pop, но когда получается значение верхнего элемента, то он также остается в положении.

Другие методы работы со стеком

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

Метод Clear используется для очистки содержимого стека. Метод не требует никаких параметров.

Часто вам нужно будет определить, существует ли элемент в стеке, но вы не хотите его доставать. Метод Contains разрешает это, возвращая логическое значение, указывающее, присутствует ли объект.

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

Создание потокобезопасной обертки стека

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


Автор этого материала — я — Пахолков Юрий. Я оказываю услуги по написанию программ на языках Java, C++, C# (а также консультирую по ним) и созданию сайтов. Работаю с сайтами на CMS OpenCart, WordPress, ModX и самописными. Кроме этого, работаю напрямую с JavaScript, PHP, CSS, HTML — то есть могу доработать ваш сайт или помочь с веб-программированием. Пишите сюда.

статьи IT, стек, уроки по си шарп, си шарп, коллекции

Ссылка на основную публикацию
Adblock
detector