#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct Phrase { // Наша фраза (в С++ структура является классом, если приебутся)
	string subject, verb, noun, adjective; // это наши члены предложения
	bool ExtendedType; // если содержит Adjective (прилагательное), то надо выставить в true.

	Phrase(const string &subject, const string &verb, const string &noun) { // Конструктор
/* Тут мы присваеваем нашим полям значения, в т. ч. и значения по умолчанию */
		ExtendedType = false;
		this->subject = string(subject);
		this->verb = string(verb);
		this->noun = string(noun);
	}

	Phrase(const string &subject, const string &verb, const string &adjective, const string &noun) { // Конструктор для расширенного типа структуры (ExtendedType = true)
/* То же самое, что и в предыдущем конструкторе */
		ExtendedType = true;
		this->subject = string(subject);
		this->verb = string(verb);
		this->adjective = string(adjective);
		this->noun = string(noun);
	}

	Phrase(const Phrase *phrase) { // copy constructor from a pointer - конструктор копирования
		subject = phrase->subject;
		verb = phrase->verb;
		noun = phrase->noun;
		ExtendedType = phrase->ExtendedType;
		if (ExtendedType)
			adjective = phrase->adjective;
	}

	//No dynamically allocated fields, so no need for destructor. - деструктор можем оставить по умолчанию, т.к. динамическая память не выделяется

	string getSubject() { // это геттер для subject'а
		return subject;
	}

};

ostream& operator<<(ostream& os, Phrase *phrase) { // Перегруженный оператор <<, нужен, чтобы выводить предложения в заданном формате (указанном в задании)
	os << phrase->subject << " " << phrase->verb << " kein "; // выводим предложение
	if (phrase->ExtendedType) // если есть прилагательное, выводим и его
		os << phrase->adjective << " ";
	os << phrase->noun << "."; // окончание вывода
	return os; // возврат объекта вывода ostream
}

struct Node { // Узел (нод)
	Phrase *phrase; // указатель на Фразу
	Node *nextNode; // указатель следующий и предыдущий ноды
	Node *prevNode;

	Node(Phrase *phrase, Node *nextNode = nullptr, Node *prevNode = nullptr) : /* это инициализирующий конструктор называется */ phrase(phrase), nextNode(nextNode), prevNode(prevNode) {}

	~Node() {
		delete phrase;
	} // т.к. динамич. память есть (выделенная new), то нужен деструктор
};

class Stack { // Стек
	Node *head; // вершина стека
	int size; // размер стека

public:
	Stack() : head(nullptr), size(0) {} // Инициализирующий конструктор

	~Stack() {
                /* тут мы бежим по линейному списку и удаляем каждый его элемент */
		Node *cur, *next = nullptr;
		cur = head;
		if (cur != nullptr)
			next = cur->nextNode;
		delete cur;
		while (cur != nullptr) {
			delete cur;
			cur = next;
			next = next->nextNode;
		}
	}

	void push(const Phrase *phrase) { // этот метод добавляет элемент в стек
		Phrase *tempPhrase = new Phrase(*phrase); //creating a copy of a phrase - создаем копию Phrase
		Node *node = new Node(tempPhrase);
		if (size == 0)
			head = node;	// если размер стека - 0, то вершиной служит node, созданный нами выше
		else { // во всех остальных случаях
			Node *cur = head;
			head->nextNode = node;
			node->prevNode = head;
			head = node; // перед тем как приравнять node вершине стека, нужно поместить в указатель на текущий нод(узел) вершину
		}
		size++;
	}

	Phrase *peek() {
		if (size == 0)
			return nullptr; // если стек пуст, то и возвращать нечего
		return head->phrase; // в другом случае возвращаем нашу фразу
	}

	Phrase *pop() { // Удаление со стека
		if (size == 0)
			return nullptr; // если стек пуст, поступаем так же

		Node *temp = head; // указатель на временную ноду = head (вершине стека, точнее адресу)
		head = head->prevNode;
		Phrase *tempPhrase = new Phrase(*temp->phrase);
		delete temp;
		size--;
		return tempPhrase;
	}

	int getSize() {
		return size;
	}

	bool isEmpty() {
		return size == 0;
	}

};

int main() {
	vector<Phrase *> strings;
	strings.push_back(new Phrase("Ich", "hore", "Larm"));
	strings.push_back(new Phrase("Er", "sah", "Katzen"));
	strings.push_back(new Phrase("Ich", "hore", "sanfte", "Musik"));
	strings.push_back(new Phrase("Er", "sieht", "schwarze", "Katze")); // Это наши примеры предложений.

	Stack *stack = new Stack(); // Создаем стек
	for (int i = 0; i < 4; i++)
		stack->push(strings[i]); // Пушим туда наши строки

	cout << stack->pop() << endl; // А далее следуют, начиная с этой строки, примеры работы твоего интерфейса, просто куча тестиков, типо подтвердить что все работает.
	cout << "Vector still contains it, so it is copied properly:\n" << strings[3] << endl; // мы копируем все по правильному
	Phrase *phr = stack->peek(); // тырим нашу фразу
	cout << "Stack size is " << stack->getSize() << ", which is proper.\n" << endl;
	cout << "Peek() return phrase: " << phr << endl;
	stack->pop();
	stack->pop();
	stack->pop(); // удаляем эл-ты со стека

	cout << "When the stack size is " << stack->getSize() << ", pop() and push() will return a nullptr."; // когда размер стека = 0, то pop() и push() возвращают nullptr (хотя мне кажется на мой косой взгляд что только pop() возвращает nullptr, но эт неточно)
	phr = stack->pop();
        // а это подтверждение предыдущей фразы
	if (phr == nullptr)
		cout << "This phrase pointer is a nullptr." << endl;
	else
		cout << "This phrase pointer is not a nullptr." << endl; // проверка

	cout << "Now, let's delete the stack completely, and check that the original phrases are still in place." << endl;
	delete stack; // стек удалили, а строки остались (как и требовалось в задании)
	for (int i = 0; i < 4; i++)
		cout << strings[i] << endl;

}