Обучение — Можно ли ограничить количество элементов в стеке


Содержание

Обучение — Можно ли ограничить количество элементов в стеке?

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

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

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

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

В стеке реализуется дисциплина обслуживания LIFO:

  • LAST — последний
  • INPUT — вошел
  • FIRST — первый
  • OUTPUT — вышел

Различают аппаратный и программный стек.

Аппаратный стек используется для хранения адресов возврата из функций и их аргументов.
Программный стек – это пользовательская модель (структура) данных.

Операции для работы со стеком

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

  • инициализация стека init(s) , где s — стек
  • помещение элемента в стек push (s, i) , где s — стек, i — помещаемый элемент;
  • удаление элемента из стека i=pop(s);
  • определение верхнего элемента без его удаления i=stkTop(s) , которая эквивалентна операциям i=pop (s); push (s, i);
  • получение вершины стека (количества элементов) i=gettop(s) , где s — стек
  • печать стека stkPrint(s) , где s — стек
  • определение пустоты стека isempty(s)
    возвращает true если стек пустой и false в противном случае.
Способы реализации стека

Существует несколько способов реализации стека:

  • с помощью одномерного массива;
  • с помощью связанного списка;
  • с помощью класса объектно-ориентированного программирования.

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

Стек можно реализовать в виде следующей структуры:

NMAX — максимальное количество элементов в стеке;
elem — массив из NMAX чисел типа float , предназначенный для хранения элементов стека;
top — индекс элемента, находящегося в вершине стека.

Инициализация стека

Индекс элемента, находящегося в вершине стека, равен 0.

Обучение — Можно ли ограничить количество элементов в стеке?

Стек представляет собой структуру данных, которая работает по принципу LIFO ( Last In First Out — «последний пришел — первый вышел»). Графически стек можно представить в виде столбика или стопки объектов:

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

Так, на приведенном рисунке вначале вершиной стека является «Tom». После добавления нового элемента «Bob» этот элемент располагается поверх элемента «Tom» и становится новой вершиной.

В библиотеке классов .NET в принципе уже есть свой класс, который выполняет роль стека. Это класс — System.Collections.Generic.Stack . Но рассмотрим, как мы сами можем реализовать структуру в виде стека.

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

В начале для реализации структуры данных определим следующий класс:

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

Для инициализации стека служат два конструктора. Конструктор без параметров создает массив items с длиной 10. Через конструктор с параметром можно самостоятельно установить длину массива.

В методе Push() добавляем элемент в массив, при этом увеличивая значение переменной count. Если же стек (а фактически массив items) уже заполнен, то выбрасываем исключение.

В методе Pop() извлекаем элемент из верхушки стека, при этом уменьшая значение переменной count. Если в стеке нет элементов, то выбрасываем исключение.

Схематично все операции можно выразить следующим образом:

Однако надо отметить, что данный стек имеет один важный недостаток — что если мы вначале не знаем точно, сколько стек может будет содержать элементов — 10, 15, 100, 200. Фиксированная длина массива накладывает ограничение на работу со стеком. Чтобы решить эту проблему, нам надо динамически менять длину массива при увеличении или уменьшении до определенного момента. Так, определим следующий класс стека:

В данном случае в класс стека по сравнению с предыдущим случаем добавлен метод Resize , который изменяет размер массива до значения max. Для этого в методе просто создается новый массив, в который копируются данные из старого.

Теперь при добавлении в методе Push() больше не надо проверять стек на переполнение. Если вдруг в массиве items больше не окажется места, то мы вызовем функцию Resize, которая увеличит массив на 10 элементов:

При удалении элемента в методе Pop аналогично изменяем размер, если в массиве items образовалось более 10 пустых ячеек.

Здесь при добавлении и удалении идет изменение количества элементов на 10. Можно увеличивать/уменьшать в два раза и т.д. Однако следует помнить, что изначальное выделение больших объемов памяти увеличит совокупную память, потребляемую приложением. При этом не факт, что хотя бы половина из нее будет использоваться.

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

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

IT-ЗАМЕТКИ

Инструменты пользователя


Инструменты сайта

Содержание

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

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

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

Основные операции над стеком и его элементами.

Очередь

Очередь — это последовательный набор элементов с переменной длиной. При этом, добавление элементов в очередь происходит с одной стороны, а удаление — с другой стороны. Данная конструкция функционирует по идеологии FIFO (First In — First Out), то есть «первым пришел — первым вышел». Для очереди принято выделять конечную последовательность элементов, из которых в каждый текущий момент времени элементами очереди заняты лишь часть последовательных элементов.

Кольцевая очередь

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

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

Очередь с приоритетом

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

Существует несколько видов приоритетных очередей:

Односвязный список

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

Односвязный список создать и реализовать достаточно просто. Каждый элемент списка представляется структурой языка C++ с двумя полями:

Удаляем заданы символ

Бинарное дерево

Бинарное дерево (binary tree) — это упорядоченная древовидная динамическая структура. Каждый элемент (узел) дерева имеет не более двух элементов следующих за ним (потомков) и не более одного предыдущего (родителя).

Обучение — Можно ли ограничить количество элементов в стеке?

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

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

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

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

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

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

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

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

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

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

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

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

Последовательное выполнение операций push 3, push 5, push 7, pop, pop, pop

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

Цукерберг рекомендует:  Задачи - Java, программа Задачи.

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ОЧЕРЕДЬ

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

Каждый элемент очереди характеризуется одним и тем же набором полей.

Логическая структура очереди приведена на рис. 1.5.

Рис. 1.5. Логическая структура очереди

Очередь функционирует по принципу FIFO (First In — First Out: «первым пришел — первым исключается»),

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

ОПЕРАЦИИ НАД ОЧЕРЕДЬЮ

Над очередью Q (от англ, queue — очередь) могут быть выполнены следующие операции:


  • 1) включение нового элемента со значением v в конец очереди — Insert(Q, v);
  • 2) исключение элемента из начала очереди — Remove(Q) и возвращение его значения;
  • 3) выработка признака «очередь пуста» — Empty(Q);
  • 4) считывание первого элемента без его удаления — HeadValue(Q);
  • 5) считывание последнего элемента очереди — RearValue(Q);
  • 6) определение числа элементов очереди Size(Q);
  • 7) очистка очереди — Clear(Q).

Первые три операции над очередью являются основными. Операции Empty, Size, и Clear для очереди аналогичны соответствующим операциям для стека.

Деком (DEQ — от англ, double ended queue — очередь с двумя концами) называется упорядоченный набор элементов, включение и исключение элементов в котором могут осуществляться с любого из двух его КОНЦОВ.

Логическая структура дека представлена на рис. 1.6.

Исключение A .Value:= v; //запись v в поле значения нового элемента Newltem A .Next:=nil; //включенный элемент будет последним if fRear <> nil // если очередь была не пуста

then fRear A .Next:=Newltem//новый элемент становится последним else fHead:= Newltem; // иначе включенный элемент — первый fRear:= Newltem; //перемещение указателя на конец очереди

Inc(fSize); //увеличение числа элементов очереди на 1

end; //procedure tQueue.Insert

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

Если элемент исключается из очереди, состоящей из единственного элемента, то после исключения указатель fRear, как и fHead, должен получить значение nil (очередь пуста). Реализация метода исключения элемента из очереди:

function tQueue.Remove: tValue;

// Исключение элемента из очереди и возвращение его значения

Remove:= Pop; // исключение элемента методом Pop стека if fHead = nil then fRear:=nil; //если очередь стала пустой

end; //function tQueue.Remove

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

Включение элемента со значением v в начало дека выполняется так же, как и включение элемента в стек. В связи с этим при реализации операции целесообразно использовать наследуемый от типа tStack метод Push, включающий элемент в вершину стека. Если элемент включается в пустой дек, то после включения указатели fHead и fRear будут ссылаться на один и тот же элемент.

procedure tDEQ.Push(v : tValue);

// Включение элемента со значением v в начало дека

inherited Push(v); //включение элемента методом Push стека. if fRear = nil // если дек был пуст then fRear:= fHead;

end; //procedure tDEQ.Push

Исключение элемента из конца дека выполняется по схеме, приве денной на рис. 1.9.

Рге A .Value; //возвращение последнего элемента дека Disltem:= fRear; // исключаемый элемент — последний

if fHead <> fRear // если в деке более одного элемента

then begin // то выполняется поиск предпоследнего элемента, Predltem:= fHead; while Predltem A .Next<>fRear do Predltem:= Predltem A .Next; fRear:= Predltem;

fRear A .Next:= nil; //который становится последним.

else begin //в деке один элементпосле исключения дек пуст fHead:= nil; fRear:= nil; end;

Dec(fSize); //уменьшение числа элементов дека на 1

end; //function tDEQ.Delete

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

ИТЕРАТОР

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

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

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

Пример. Суммирование элементов очереди без итератора.

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

Цукерберг рекомендует:  Выезжающее меню с помощью jQuery

sum: tValue; //значение суммы

q, q1 : tQueue; //основная q и вспомогательная q1 очереди

q1 :=q.Copy; //копирование основной очереди q в очередь q1

while not q1.Empty do sum:=sum+q1 .Remove;

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

Итератор включает в себя три операции:

  • 1) инициализация итератора;
  • 2) выдача очередного элемента;
  • 3) проверка, все ли элементы выданы.


Итератор удобно реализовать в виде операций в абстрактном типе данных (например, в очереди).

Для этого в секцию protected описания типа tQueue добавим новое поле

fltem: pltem; //указатель на текущий элемент очереди

и в секцию public методы:

procedure Iterlnit; function IterDone: Boolean; function lterNext:tValue;

Реализация методов итератора: procedure tQueue.Iterlnit;

fltem:=fHead; end; // tQueue. Iterlnit

function tQueue.IterDone: Boolean;

// Возвращение True, если все элементы очереди выданы

lterDone:= fltem = nil; end; // tQueue. IterDone

function tQueue.IterNext: tValue;

// Выдача итератором значения очередного элемента очереди

if not IterDone then begin

lterNext:=fltem A .Value;

fltem:=fltem A .Next;

Пример. Суммирование элементов очереди с итератором.

sum: tValue; q : tQueue;

while not q.IterDone do sum:=sum+q.IterNext;

Контрольные вопросы и задания

  • 1. В чем заключаются достоинства и недостатки последовательного и связанного способов реализации динамических структур данных?
  • 2. Назовите принципы функционирования стека, очереди и дека.
  • 3. Приведите примеры использования стека в программировании.
  • 4. Реализуйте класс — стек с базовым набором методов на основе массива нетипированных указателей на размещенные в динамической памяти элементы.
  • 5. С использованием основных методов работы со стеком составить программу копирования элементов стека в новый стек в том же порядке.
  • 6. Преобразуйте в префиксную форму записи инфиксное выражение (ах 2 +)/(bx + a)-abx при условии, что все идентификаторы — однобуквенные.
  • 7. Преобразуйте в постфиксную форму записи инфиксное выражение * + с) +d) / 2 при условии, что все идентификаторы — однобуквенные.
  • 8. Опишите процесс функционирования стека при вычислении значения постфиксного выражения abc + *d -г 2 / при а = 2,Ь = 5,с = 3, d = 4.
  • 9. Реализуйте метод копирования элементов очереди в новую очередь.
  • 10. С использованием стандартного набора методов составьте программу копирования элементов стека в новый стек в обратном порядке.
  • 11. С использованием стандартного набора методов составьте программу записи элементов очереди в новую очередь в обратном порядке.
  • 12. С использованием стандартного набора методов составьте программу переноса из очереди строк в новую очередь элементов, начинающихся на буквы «F» или «f».

Лабораторная работа 1. СТЕКИ, ОЧЕРЕДИ, ДЕКИ

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

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

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

  • • Описание класса и реализацию его методов следует разместить в отдельном модуле.
  • • Для выполнения операций, не включенных в набор операций класса, например, вывод элементов структуры, необходимо реализовать и использовать итератор, либо написать соответствующий метод.
  • • Исходные данные необходимо считывать из файла и вместе с результатами работы помещать в файл результатов.
  • • В программе следует предусмотреть вывод необходимых промежуточных и всех окончательных результатов решения задачи.
  • • По окончании работы экземпляры структур необходимо очистить и освободить память, занимаемую ими.
  • • Предусмотреть генерацию и обработку исключительных ситуаций, которые могут возникнуть при выполнении операций со структурами данных.
  • 1. Проверить правильность расстановки скобок в арифметическом выражении (допустимы четыре типа скобок: круглые, квадратные, фигурные и угловые). Для слежения за скобками воспользоваться стеком.
  • 2. Сформировать две очереди с фамилиями клиентов. Слить обе очереди в третью, расположив клиентов через одного.
  • 3. Создать стек, каждый элемент которого является совокупностью двух целых значений. Заменить нулевыми все элементы с заданной суммой значений.
  • 4. Сформировать стек с элементами — строками. Прочитать три нижних элемента стека и поменять местами верхний и нижний элементы.
  • 5. Вычислить значение выражения, записанного в постфиксной форме. Операнды представляют собой переменные с однобуквенным идентификатором или (и) цифры от 0 до 9, и в выражении используются только операции «+», «—», «*», «/».
  • 6. Прочитать из входного файла последовательность слов Pop и Push. Слово Push вталкивается в стек и выводится число элементов стека, при чтении слова Pop выполняется операция исключения элемента из стека. При невозможности выполнения операции Pop вывести нужное сообщение и работу прекратить.
  • 7. Ввести программу на языке Бейсик, состоящую из произвольного числа расположенных последовательно или вложенных инструкций:
  • 40 NEXT x

и определить правильность вложения циклов. Для каждой строки выводить сообщение вида: «Цикл по х открыт», «Цикл по х закрыт» или сообщение об ошибке.

  • 8. Преобразовать бесскобочную инфиксную запись выражения в постфиксную. Операнды представляют собой переменные с однобуквенным идентификатором или цифры от 0 до 9, и в выражении используются только операции «+», «—», «*», «/».
  • 9. Сформировать дек целочисленных элементов и преобразовать его таким образом, чтобы первый элемент стал последним, второй — предпоследним и т.д. При преобразовании исключить из дека нулевые элементы.
  • 10. Сформировать две очереди с элементами — фамилиями клиентов. Удалить из второй очереди клиентов, стоящих также и в первой.
  • 11. Ввести программу на языке Бейсик, состоящую из произвольного числа расположенных последовательно или вложенных инструкций:
  • 10 FOR х=а ТО b STEP с
  • 40 NEXT х


и перевести ее в следующую форму:

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

  • 12. Создать очередь с элементами — строками. Исключить из очереди элементы, начинающиеся с буквы А. Вывести длину получившейся очереди и значения ее первого и последнего элементов.
  • 13. Создать очередь клиентов и распределить клиентов по двум вспомогательным очередям (через одного).
  • 14. Сформировать дек, каждым элементом которого являются сведения о студенте (фамилия, номер группы, год рождения). Переписать в очередь студентов заданного года рождения.
  • 15. Создать дек, каждый элемент которого представляет собой совокупность трех вещественных значений. Исключить из дека все элементы, у которых каждое из трех значений превышает заданное. Вывести длину получившегося дека и значения его первого и последнего элементов.
  • 16. Сформировать очередь для двух стеков вещественных значений таким образом, чтобы вершина первого стека стала началом очереди, а вершина второго — ее концом.
  • 17. Вычислить значение выражения, записанного в префиксной форме. Операнды представляют собой переменные с однобуквенным идентификатором или (и) цифры от 0 до 9, и в выражении используются только операции «+», «—», «*», «/».
  • 18. Сформировать очередь целых чисел. С использованием дека расположить все элементы очереди в обратном порядке.
  • 19. Ввести программу на языке Бейсик, состоящую из произвольного числа расположенных последовательно или вложенных инструкций:
  • 10 FOR х=а ТО b STEP с 40 NEXT х

при условии, что один оператор NEXT может завершать одновременно несколько вложенных циклов (например: NEXT z,y,x), и определить правильность вложения циклов. Для каждого цикла выводить сообщение вида: «Цикл по х открыт», «Цикл по х закрыт».

  • 20. Преобразовать выражение в инфиксной форме в префиксную. Операнды представляют собой переменные с однобуквенным идентификатором или (и) цифры от 0 до 9, и в выражении используются только операции «+», «-», «*», «/».
  • 21. Сформировать две очереди с элементами — фамилиями клиентов. Удалить из первой очереди клиентов, стоящих в двух очередях.
  • 22. Исключить из стека строк три нижних элемента, если в вершине содержится текст «Вершина». В противном случае изменить содержимое трех нижних элементов на «Первый», «Второй», «Третий».
  • 23. Создать дек с элементами — двумя целочисленными значениями. Подсчитать количество элементов с заданной суммой значений, прочитать пятый и шестой элементы от начала сформированного дека.
  • 24. Сформировать два дека с фамилиями клиентов. Слить оба дека в третий, расположив клиентов через одного, начиная с конца.
  • 25. Сформировать очередь целых чисел. С использованием стека расположить все элементы исходной очереди в обратном порядке.
  • 26. Создать деке элементами — фамилиями студентов. Перенести в очередь элементы с фамилиями, начинающимися с букв «А» — «К».
  • 27. Создать дек целочисленных значений и распределить все его элементы по двум стекам через одного, начиная с последнего элемента.
  • 28. Сформировать дек, каждым элементом которого являются сведения о студенте (фамилия, номер группы, год рождения). Переписать в очередь студентов заданной группы.
  • 29. Определить, имеет ли вводимая строка вид хСу, где х — строка, состоящая из букв А и В, а у — строка, обратная строке х. Если да, то определить, имеет ли вводимая строка форму aDbD. Dz, где а, Ь,

z — строки вида хСу.

  • 30. Ввести программу на языке Бейсик, состоящую из произвольного числа расположенных последовательно или вложенных инструкций:
  • 10 FOR х=а ТО b STEP с 40 NEXT х

при условии, что один оператор NEXT может завершать одновременно несколько вложенных циклов (например: NEXT z,y,x), и перевести ее в следующую форму:

  • 10 х=а-с 20 х=х+с
  • 50 IF x DelVal then Stack2.Push(StVal); end;

// Запись оставшихся после удаления // элементов из стека 2 в стек 1 while not Stack2.Empty do Stackl .Push(Stack2.Pop);

// Вывод элементов стека 1

// в файл результатов с помощью итератора

WriteLn(fRes, ‘Из стека исключено quan — Stackl .Size,’ элементов’)

Writel_n(fRes, ‘В стеке осталось ‘,Stackl .Size,’ элементов:’);

while not Stackl .IterDone do Write(fRes, Stackl .lterNext:5:1);

// Удаление экземпляров стеков Stackl.Free; Stack2.Free;

// Закрытие файлов Close(fDat); Close(fRes);

Стек (stack) в C++: легко и просто!

Всем привет! Сегодня мы разберем структуру данных, которая часто используется для решения задач или для оптимизации программ. Все когда-то в программировании слышали такое слово как стек.

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

Что такое стек и как он работает

Стек — это структура данных, которая работает по принципу FILO (first in — last out; первый пришел — последний ушел). В C++ уже есть готовый шаблон — stack .

В стеке элемент, который вошел самый первый — выйдет самым последним. Получается, если вы добавили три элемента в стек первым будет удален последний добавленный элемент.
На рисунке 1 вы можете увидеть 6 чисел: 6, 5, 1, 2, 5, 9. Кстати извлекать их будем в таком же порядке. Например чтобы извлечь число 1 нам придется сначала извлечь числа 6 и 5, а потом уже 1. Так как это стек, эти числа мы добавляли в обратном порядке. Если быть точным вот так: 9, 5, 2, 1, 5, 6.

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

Это значит что каждый элемент (кроме последнего — он показывает на NULL , если простыми словами, то на ничего) имеет указатель на следующий элемент. Но есть элемент, на который нет указателя — первый (или как его еще называют головной).

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

Но все достоинство шаблонного стека заключается в добавлении и удалении элементов. Эти операции происходят за константное время (это хороший плюс).

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

Как создать стек в C++

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

Чтобы создать стек нам понадобится оперировать схемой ниже:

Подсчет количества элементов стека

Функция простая, но при переходе с последнего элемента на NULL происходит ошибка чтения данных. Не подскажете, в чем проблема?

Знаете кого-то, кто может ответить? Поделитесь ссылкой на этот вопрос по почте, через Твиттер или Facebook.

Посмотрите другие вопросы с метками c++ c стек или задайте свой вопрос.

Похожие

Подписаться на ленту

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

дизайн сайта / логотип © 2020 Stack Exchange Inc; пользовательское содержимое попадает под действие лицензии cc by-sa 4.0 с указанием ссылки на источник. rev 2020.11.14.35449

Динамические структуры данных: очередь и стек

Лабораторная работа 30. Динамические структуры данных: очередь и стек


Цель работы: изучить понятия, объявления, особенности доступа к данным и работы с памятью в стеках и очередях, научиться решать задачи с использованием стеков и очередей в языке C++.

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

Ознакомьтесь с материалом лекции 30.

Задания к лабораторной работе.

Выполните приведенные ниже задания.

  1. Опишите стек с целочисленным информационным полем. Заполните его длинами строк , считанных из файла. Распечатайте на экране содержимое стека. Укажите номер и длину последней самой короткой строки файла.
  2. Разработайте программу, с помощью которой можно определить наибольший допустимый размер очереди с вещественным информационным полем. Найдите этот размер (число элементов в очереди).
  3. Опишите очередь с вещественным информационным полем, и заполните ее элементами с клавиатуры. Выполните циклический сдвиг элементов в очереди так, чтобы в ее начале был расположен наибольший элемент.
  4. Разработайте программу, с помощью которой можно определить наибольший допустимый размер стека с вещественным информационным полем. Найдите этот размер (число элементов в стеке). Сравните с наибольшим допустимым размером очереди с аналогичным информационным полем.

Указания к выполнению работы.

Каждое задание необходимо решить в соответствии с изученными методами формирования, вывода и обработки данных очередей и стеков в языке С++. Обработку очередей или стеков следует выполнить на основе базовых алгоритмов: поиск , вставка элемента, удаление элемента , удаление всей динамической структуры. При объявлении списков выполните комментирование используемых полей. Задачи 2 и 4 носят исследовательский характер, поэтому при составлении отчета к ним следует подробно описать предлагаемый метод оценки максимального размера очереди или стека. Программу для решения каждого задания необходимо разработать методом процедурной абстракции, оформив комментарии к коду.

Следует реализовать каждое задание в соответствии с приведенными этапами:

  • изучить словесную постановку задачи, выделив при этом все виды данных;
  • сформулировать математическую постановку задачи;
  • выбрать метод решения задачи, если это необходимо;
  • разработать графическую схему алгоритма;
  • записать разработанный алгоритм на языке С++;
  • разработать контрольный тест к программе;
  • отладить программу;
  • представить отчет по работе.

Требования к отчету.

Отчет по лабораторной работе должен соответствовать следующей структуре.

foreach — ограничение количества циклов в переполнении стека

У меня есть цикл foreach, который мне нужно ограничить первыми 10 пунктами, а затем выйти из него.

Как бы я сделал это здесь?

Буду признателен за подробное объяснение.

Решение

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

Другие решения

Вы также можете использовать LimitIterator .

Вы можете просто перебрать array_slice($butters->users->user, 0, 10) (первые 10 элементов).

Используйте счетчик циклов и break когда вы хотите выйти.

На 10-й итерации цикл завершится в конце.

Существует несколько вариантов этого, и вам нужно выбрать одну вещь: хотите ли вы выполнить условие внешнего цикла или нет. Рассматривать:

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

Если вы уверены, что хотите сохранить foreach цикл, добавить счетчик:

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

Кроме того, вы можете переделать foreach цикл, чтобы быть for цикл, если это возможно.

Вы можете запустить счетчик перед вашим блоком foreach и проверить его в цикле, а затем отключить, если счетчик равен 10,

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

Простейшие структуры данных: стек, очередь, дек

Понятие структуры данных

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

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

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

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

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

  • Добавить элемент в стек (Сложность: )
  • Извлечь элемент из стека (Сложность: )
  • Проверить, пуст ли стек (Сложность: )

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

Приведём простую реализацию стека на C++. Для простоты максимальный размер нашего стека будет ограничен тысячей элементов:

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

Очередь

Очередь поддерживает тот же набор операций, что и стек, но имеет противоположную семантику. Для описания очереди используется аббревиатура FIFO (First In, First Out), так как первым из очереди извлекается элемент, раньше всех в неё добавленный. Название этой структуры говорит само за себя: принцип работы совпадает с обычными очередями в магазине или на почте.

Реализация очереди похожа на реализацию стека, но в этот раз нам понадобятся два указателя: для первого элемента очереди (“головы”) и последнего (“хвоста”):

При такой реализации очередь будет постепенно “ползти” вправо по выделенной области памяти (массиву), и достаточно быстро выйдет за её границы. Впрочем, эта реализация иллюстративная, на практике вы просто будете использовать уже готовую реализацию очереди из стандартной библиотеки (об этом ниже). В ней этот дефект отсутствует из-за более сложной работы с памятью.

Структура, объединяющая стек и очередь, называется дек (англ. deque — сокращение от double-ended queue, очередь с двумя концами). Как можно догадаться, она поддерживает уже знакомый набор операций:

  • Добавить элемент в начало дека (Сложность: )
  • Извлечь элемент из начала дека (Сложность: )
  • Добавить элемент в конец дека (Сложность: )
  • Извлечь элемент из конца дека (Сложность: )
  • Проверить, пуст ли дек (Сложность: )

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

Стек, очередь и дек в стандартной библиотеке C++

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

С реализацией дека дела обстоят несколько иначе. Стандартный класс std::deque является не классическим деком, а скорее вектором с возможностью вставки и добавления в начало за . Он поддерживает все операции, поддерживаемые классом std::vector , в том числе обращение к элементу по индексу и итераторы с произвольным доступом. Так что для работы с ним используйте те же методы, что и при работе с вектором.

Более сложные структуры данных

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

brestprog

Олимпиадное программирование в Бресте и Беларуси

Цукерберг рекомендует:  Cmd - Пакетная обработка
Понравилась статья? Поделиться с друзьями:
Все языки программирования для начинающих