Задачи программирования структура очередь

«Решение задач при помощи структур данных (стеки, очереди)»

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

Очереди

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

Есть несколько способов реализации такой структуры. Простейшей является реализация при помощи массива и двух переменных-указателей, один из которых определяет то место массива, куда элемент будет добавляться, и называется концом очереди (УК), а другой – определяет то место массива, откуда элемент будет удаляться, и называется началом очереди (УН). Если УК<>УН, то в очереди есть элементы, при этом элемент с меньшим номером считается поступившим в очередь раньше, чем элемент с большим номером.

Допустим, в очередь помещён элемент А, потом В, потом С. Тогда очередь имеет вид:

Источник

Как и зачем делать очередь на двух стеках

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

Для начала вспомним основы:

Стек

Стек реализует принцип LIFO (англ. last in — first out, «последним пришёл — первым вышел»).

Стек имеет две основные операции:

Очередь

Очередь — это структура данных с доступом к элементам FIFO (англ. First In, First Out – «первым пришёл — первым ушёл»)

Очередь имеет два основных метода в своем интерфейсе:

Обычно рассматривают два базовых подхода к реализации очереди:

Почему стек круче, чем очередь

Представим себе, что наша структура данных должна поддерживать следующий набор операций:

• Поддержка минимума (min)
• Поддержка максимума (max)
• Поддержка gcd (англ. greatest common divisor — наибольший общий делитель)
• Поддержка lcm (англ. least common multiple — наименьшее общее кратное)

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

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

Ниже пример реализации стека с поддержкой минимума на Python:

class Stack: def __init__(self): self.stack = [] def __bool__(self): return bool(self.stack) def push(self, elem): if self.stack: self.stack.append((elem, min(elem, self.stack[-1][1]))) else: self.stack.append((elem, elem)) def pop(self): return self.stack.pop()[0] def get_min(self): if not self.stack: return math.inf return self.stack[-1][1] 

А теперь подумайте, как проделать тот же фокус с очередью? Если пробовать с классической очередью, организованной на массиве, вряд ли что-то получится. Это связано с тем, что операция минимум не имеет обратную операцию (как операция сложения имеет операцию вычитания, например). Как вы могли догадаться, далее я расскажу о не совсем классической реализации очереди на двух стеках.

Очередь на двух стеках

Главное условие, которое должно быть выполнено — все операции должны выполняться за амортизированное O(1).

Возьмем два стека: s1 и s2.

Операцию push будем всегда делать в стек s1.

Операция pop будет устроена так: если стек s2 пустой, перекладываем все элементы из s1 в s2 последовательными вызовами pop и push. Теперь в стеке s2 лежат элементы в обратном порядке (самый верхний элемент — это самый первый положенный элемент в нашу очередь).

Если s2 не пуст, тупо достаем элементы из него. Как только s2 окажется снова пустым повторяем ту же операцию.

class Queue: def __init__(self): self.s1 = Stack() self.s2 = Stack() def push(self, elem): self.s1.push(elem) def pop(self): if not self.s2: while self.s1: self.s2.push(self.s1.pop()) return self.s2.pop() def get_min(self): return min(self.s1.get_min(), self.s2.get_min()) 

Время работы

Операция push: Мы тупо кладем элемент в стек s1. Время работы O(1).

Операция pop: Для каждого элемента мы делаем не более одного перекладывания из стека в стек, следовательно амортизированное время работы составит O(1).

Операция get_min: Для стеков s1 и s2 известны минимумы, поэтому мы просто берем минимум из минимумов. Время работы O(1).

Бонусная задачка

Заключение

Спасибо, что дочитали до конца!

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

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

Источник

Задачи на реализацию стеков с очередями

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

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

Подробнее об этих структурах данных вы можете прочесть в нашей статье.

Условие задачи

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

Дополнительная задача:

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

Решение

В соответствии с формулировкой задачи структура данных будет иметь следующий
вид:

class SetOfStacks < Arraylist stacks new Arraylist (); puЬlic void push ( int v) < . >puЬlic int рор ( ) < . >>

Известно, что push() должен работать так же, как для одиночного стека; это означает, что его реализация должна вызывать push() для последнего стека из массива стеков. При этом нужно действовать аккуратно: если последний стек заполнен, нужно создать новый стек. Код будет выглядеть примерно так:

public void push(int v) < Stack last = getLastStack(); if (last != null && !last.isFull()) < // Добавить в последний стек last.push(v); >else < // Необходимо создать новый стек Stack stack = new Stack(capacity); stack.push(v); stacks.add(stack); >>

Что должен делать метод рор() ? Он, как и push() , должен работать с последним стеком. Если последний стек после удаления элемента методом рор() оказывается пустым, его нужно удалить из списка стеков:

Реализация popAt(int index)

Извлечение из внутреннего стека реализуется несколько сложнее. Представьте себе систему с «переносом»: если требуется извлечь элемент из стека 1, то из стека 2 нужно удалить НИЖНИЙ элемент и занести его в стек 1. Затем аналогичная операция должна быть проделана со стеками 3 и 2, 4 и 3 и т. д. На это можно возразить, что вместо «переноса» можно смириться с тем, что неко­торые стеки заполнены не на всю емкость. Этот компромисс улучшит временную сложность (притом заметно, при большом количестве элементов), но может создать проблемы потом, если пользователь предположит, что все стеки (кроме последнего) работают на полной емкости.

import java.util.ArrayList; import java.util.EmptyStackException; public class SetOfStacks < ArrayList stacks = new ArrayList(); public int capacity; public SetOfStacks(int capacity) < this.capacity = capacity; >public Stack getLastStack() < if (stacks.size() == 0) < return null; >return stacks.get(stacks.size() - 1); > public void push(int v) < Stack last = getLastStack(); if (last != null && !last.isFull()) < // add to last last.push(v); >else < // нужно создать новый стек Stack stack = new Stack(capacity); stack.push(v); stacks.add(stack); >> public int pop() < Stack last = getLastStack(); if (last == null) throw new EmptyStackException(); int v = last.pop(); if (last.size == 0) < stacks.remove(stacks.size() - 1); >return v; > public int popAt(int index) < return leftShift(index, true); >public int leftShift(int index, boolean removeTop) < Stack stack = stacks.get(index); int removed_item; if (removeTop) removed_item = stack.pop(); else removed_item = stack.removeBottom(); if (stack.isEmpty()) < stacks.remove(index); >else if (stacks.size() > index + 1) < int v = leftShift(index + 1, false); stack.push(v); >return removed_item; > 

import java.util.EmptyStackException; public class Stack < private int capacity; public Node top; public Node bottom; public int size = 0; public Stack(int capacity) < this.capacity = capacity; >public boolean isFull() < return capacity == size; >public void join(Node above, Node below) < if (below != null) below.above = above; if (above != null) above.below = below; >public boolean push(int v) < if (size >= capacity) return false; size++; Node n = new Node(v); if (size == 1) bottom = n; join(n, top); top = n; return true; > public int pop() < if (top == null) throw new EmptyStackException(); Node t = top; top = top.below; size--; return t.value; >public boolean isEmpty() < return size == 0; >public int removeBottom() < Node b = bottom; bottom = bottom.above; if (bottom != null) bottom.below = null; size--; return b.value; >> 

Концептуально задача не сложна, но ее полная реализация потребует написания довольно объемного кода. Хорошая стратегия в подобных задачах — разделение кода на методы. Например, в нашем коде присутствует метод leftShift , который вызывается в методе popAt . Этот прием сделает код более прозрачным и понятным.

Решение дополнительной задачи

С учетом главного различия между очередью и стеком (FIFO против LIFO) нужно изменить методы peek() и рор() так, чтобы они работали в обратном порядке. Для обращения порядка элементов можно воспользоваться вторым стеком (выталкиваем sl и помещаем все элементы в s2). В такой реализации каждая операция peek() или рор() приводит к извлечению всех элементов из sl в s2, после чего выполняется операция peek/pop , а затем все возвращается обратно (с помощью push).

Этот алгоритм будет работать, но при последовательном выполнении операций pop/peek будут происходить лишние перемещения элементов. Можно реализовать «отложенный» подход, при котором элементы хранятся в s2 до того момента, пока
нам не понадобится их инвертировать.

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

Приведенный ниже код реализует данный алгоритм:

import java.util.Stack; public class MyQueue < Stack stackNewest, stackOldest; public MyQueue() < stackNewest = new Stack(); stackOldest = new Stack(); >public int size() < return stackNewest.size() + stackOldest.size(); >public void add(T value) < /* Все новейшие элементы находятся на вершине stackNewest */ stackNewest.push(value); >/* Перемещение элементов из stackNewest в stackOldest . Обычно это * делается для выполнения операций с stackOldest . */ private void shiftStacks() < if (stackOldest.isEmpty()) < while (!stackNewest.isEmpty()) < stackOldest.push(stackNewest.pop()); >> > public T peek() < shiftStacks(); // Перенести текущие элементы в stackOldest return stackOldest.peek(); // Получить самый старый элемент . >public T remove() < shiftStacks(); // Перенести текущие элементы в stackOldest return stackOldest.pop(); // Извлечь самый старый элемент . >> 

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

Источник