## Стек
**Стек** (stack) - это АТД, работающий по принципу LIFO (Last In First Out: последним зашел - первым вышел)
Операции:
- **nullStack** - обнуление стека
- **empty** - проверка стека на пустоту
- **push** - добавление элемента в стек
- **pop** - удаление элемента из стека
### Реализация стека с помощью динамического массива
![Реализация стека с помощью динамического массива](../Pictures/02_01.%20Реализация%20стека%20с%20помощью%20динамического%20массива.png)  
```cpp
struct Stack {
	int top;
	int* data;
};

void InitStack(Stack& st, int capacity) {
	st.data = new int[capacity];
	st.top = -1;
}

void push(Stack& st, int value) {
	st.data[++st.top] = value;
}

int pop(Stack& st) {
	return st.data[st.top--];
}

void nullStack(Stack& st) {
	st.top = -1;
}

bool empty(Stack& st) {
	return st.top == -1;
}
```

Недостаток реализации в массиве - то, что у массива заранее определен размер и, при достижении последнего элемента массива с попыткой добавления еще одного, возникает ошибка переполнения стека. Чтобы этого избежать, можно реализовывать стек с помощью динамического линейного списка
### Реализация стека с помощью динамического линейного списка
```cpp
struct Node {
	int data;
	Node *next;
};
void initStack(Node *&top) {
	top = NULL;
}
void push(Node *&top, int value) {
	Node *tmp = new Node;
	tmp->next=top;
	top=tmp;
	top->data=value;
}
int pop(Node *&top) {
	Node *tmp = top;
	int d = top->data;
	top = top->next;
	delete(tmp);
	return d;
}
bool empty(Node *&top) {
	return top == NULL;
}
void nullStack(Node *&top) {
	Node *tmp;
	while (!empty(top)) {
		tmp = top;
		top = top->next;
		delete(tmp);
	}
}
```
## Очередь
**Очередь** (queue) - линейный список, работающий по принципу FIFO (First In First Out: первым вошел - первым вышел)
Операции:
- **nullQueue** - обнуление очереди
- **empty** - проверка очереди на пустоту
- **add (enqueue)** - добавление элемента в очередь
- **del (dequeue)** - удаление элемента из очереди
### Реализация очереди с помощью динамического массива
```cpp
struct Queue1 {
	int head, tail, size;
	int* data;
};
void nullQueue(Queue1& q) {
	q.head = 0;
	q.tail = q.size - 1;
}
void InitQueue(Queue1& q, int capacity) {
	q.size = capacity + 1;
	q.data = new int[q.size];
	nullQueue(q);
}
int next(Queue1& q, int n) {
	return (n + 1) % q.size;
}
bool empty(Queue1& q) {
	return next(q.tail) == q.head;
}
void add(Queue1& q, int value) {
	if (next(q, next(q, q.tail)) == q.head) {
		cout << "Queue overflow" << endl;
	}
	else
	{
		q.tail = next(q.tail);
		q.tail = next(q.tail);
		q.data[q.tail] = value;
	}
}
int del(Queue1& q) {
	if (empty(q)) {
		cout << "Queue is empty" << endl;
		return 0;
	}
	else {
		int d = q.data[q.head];
		q.head = next(q, q.head);
		return d;
	}
}
```

Недостаток реализации в массиве заключается в том, что когда очередь дойдет до последнего элемента в массиве, логично предположить, что очередь будет переполнена. Однако, к этому времени из головы могут быть забраны несколько элементов и реально в массиве свободное место будет. Чтобы в такой ситуации не перегонять всю очередь в начало массива, было предложено считать массив закольцованным - когда за последним элементом массива следует первый. В этом случае для вычисления N-ного элемента массива, следующего за **i**-тым элементом, используется формула **(i+1) % array.size**. Чтобы при такой реализации различать пустую и переполненную очередь, решили считать очередь пустой, если сразу за хвостом следует голова, а переполненной - если голова находится через 1 элемент от хвоста, т. е. в массиве из **n** элементов максимально может поместиться **n-1** элементов очереди.
### Реализация очереди с помощью динамического линейного списка
```cpp
class Queue {
private:
	struct Node {
		int data;
		Node* next;
	};
	Node* head;
	Node* tail;
public:
	Queue() {
		head = NULL;
	}
	bool empty() {
		return head == NULL;
	}
	void add(int value) {
		if (empty()) {
			head = new Node;
			head->data = value;
			head->next = NULL;
			tail = head;
		}
		else {
			tail->next = new Node;
			tail = tail->next;
			tail->data = value;
			tail->next = NULL;
		}
	}
	int del() {
		if (empty()) {
			cout << "empty queue" << endl;
		}
		else {
			int d = head->data;
			Node* tmp = head;
			head = head->next;
			delete(tmp);
			return d;
		}
	}
	void nullQueue() {
		Node* tmp;
		while (!empty()) {
			tmp = head;
			head = head->next;
			delete(tmp);
		}
	}
};
```
## Дек
**Дек** (double-ended queue) - двухсторонняя очередь  
Операции:
- Включение элемента слева
- Включение элемента справа
- Исключение элемента слева
- Исключение элемента справа
- Проверка на пустоту
- Очистка
## Двухсвязные динамические списки
Операции:
- Перемещение по списку в 2 направлениях
- Вставка элемента слева, справа, в середину
- Удаление элемента слева, справа, в середине