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

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

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

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

Стек, впрочем как и очередь, должен поддерживать следующие операции:

• push – добавить (положить) в конец стека новый элемент
• pop – извлечь из стека последний элемент
• top – узнать значение последнего элемента (не удаляя его)
• length – узнать количество элементов в стеке
• clear – очистить стек (удалить из него все элементы)

Реализовать стек и набор операций над ним в D можно следующим образом:

private
{
	import std.range;
}

// стек для хранения данных
class Stack(T)
{
private:
	T[] elements;
	
public:
	
	// добавление элемента в конец
	void push(T element)
	{
		elements ~= element;
	}
	
	// добавление ряда элементов
	void push(T[] elementsArray)
	{
		elements ~= elementsArray;
	}
	
	// удалить один элемент
	void pop()
	{
		--elements.length;
	}
	
	// количество элементов
	size_t length() const @property
	{
		return elements.length;
	}
	
	// вершина стека
	T top() const @property
	{
		return elements[$-1];
	}
	
	// содержимое стека
	T[] content() @property
	{
		return elements;
	}
	
	// очистить стек
	void clear()
	{
		elements.length = 0;
	}
	
	// стек пустой ?
	bool empty() const @property
	{
		if (elements.length == 0)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
}

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

Реализуем это:

// Очередь
class ShiftedStack(T, size_t M) : Stack!T
{
private:
	T[M] emptyStack = T.init;

public:
	this()
	{
		elements ~= emptyStack;
	}
	
	
	override
	{
		void push(T element)
		{
			elements ~= element;
			elements = elements[1..$];
		}
		
		
		void push(T[] elementsArray)
		{
			if (!elements.empty)
			{
				elements ~= elementsArray;
				elements = elements[0..M];
			}
		}
		
		void pop()
		{
			if (!elements.empty)
			{
				super.pop();
				elements ~= emptyStack;
				elements = elements[0..M];
			}
		}
		
		
		size_t length() const @property
		{
			return M;
		}
		
		void clear()
		{
			elements = emptyStack;
		}
	}
}