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

Для начала немного теории:

Стек — это коллекция, элементы которой получают по принципу «последний вошел, первый вышел» (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(), должен работать с последним стеком. Если последний стек после удаления элемента методом рор() оказывается пустым, его нужно удалить из списка стеков:

			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;
	}
		

Реализация 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(); // Извлечь самый старый элемент .
	}
}
		

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