Стек #3

Здравствуйте, уважаемые читатели.

Две предыдущие статьи по структуре данных (раз и два) несли общие знания без конкретизации и реализации. А в этой статье и следующих будут рассмотрены динамически структуры по отдельности и с реализацией.

Для реализации структур данных я буду использовать язык программирования С++. Мое решение было обусловлено, тем, что  этот язык является очень популярным и имеет широкие возможности по работе с памятью.

Теперь приступим к теме статьи.


 

Что такое стек и с чем его едят?

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

Стек можно представить себе как стакан с монетками, лежащими столбиком.

Т.е. мы кладем монетку на дно, потом еще одну сверху и так далее. И, чтоб достать монетку, которую мы опустили в стакан первой, нужно вытащить все предыдущие. В этом и заключается принцип стека и звучит он так: «Последним пришёл — первым вышел». Великие мира сего даже придумали специальную аббревиатуру  LIFO (англ. last in — first out).

Теперь монетки переведем в информационный эквивалент.

Имеем мы значит односвязный список. Добавили туда первый элемент (хвост списка), далее добавляем все новые элементы только слева от хвоста, т.е. каждый раз создаем новую голову. А удаляем наоборот —  с головы до хвоста. Таким образом, элемент, который последний попал в стек, выйдет из него первым (помним про LIFO). Вот небольшая картинка для наглядности:

 

С++ программирование стек

Все, как видите, очень просто. Для работы со стеком принято реализовывать три основные функции:

1. Push — втолкнуть элемент.

2. Pop — вытолкнуть элемент.

3. Peek — считать вершину (голову) стека.

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

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

#include<iostream>

using namespace std;

class stack//Класс стека
{
private:
	struct stack_ob// Структура для хранения элементов стека
	{
		int value;//Поле для хранения значения элемента стека
		stack_ob *addr; // Поле для хранения слеющего элемента
	};

	stack_ob *head; // указатель, хранящий адресс головы стека
	int size; //Текущий размер стека

public:
	stack(int x)// Конструктор класса
				//В параметр передается хвост стека
	{
		head=new(stack_ob); //Выделяем память под элемент
		head->value=x; // ЗАписываем значение
		head->addr=0; // Адрес ноль, так как это хвост стека - элемент добавленный первым
		size=1; // После выделения памяти и заполянения полей структуры стек стал иметь размер 1
	}

	int stack_size()//Функция возвращает размер стека(кол-во элеменетов)
	{
		return size;
	}

void push(int value)// Добавляет(вталкивает) элемент в стек
{
	size++;// Кол-во элементов стека увеличивается
	stack_ob *temp=head; // Записываем адрес старой головы(вершины) стека
	head=new(stack_ob); //Выделяем память под новый элемент
	head->addr=temp;	// Записываем в поле адреса головы адрес старой головы
	head->value=value;	//Записываем значение новой головы
}

void pop(int *ret)//Удаляет элемент(выталкивает) и возвращает его
				 // По адресу, хранящемся в ret, передается значение удаляемой головы
{
	if(size == 0)
	{
		cout<<"Стек пуст - удалять нечего!"<<endl;
		return;
	}

	stack_ob *temp=head; // записываем адрес головы
	*ret=head->value; // записываем значени головы
	head=head->addr; // изменяем адрес головы
	delete temp;  // удаляем старую голову
	size--; // уменьшаем размер
}

void peek(int *ret)//Выгружает значение по адресу, передаваемому в парметре
{
	if(size == 0) // Если стек пуст(size == 0), то ничего не выгружает
		{
			cout<<"Стек пуст!"<<endl;
			return;
		}
	*ret=head->value;// Выгружаем значение головы
}

};// Конец класса стека

Стек реализован на основе класса, но все это можно было сделать, используя только структуру и обычные функцию, но для С++ правильнее делать с классом.

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

Также я добавил метод для чтения количества элементов стека. Поле size не просто так сделал закрытым. Это обусловлено, тем, что size являясь публичным, мог быть вызван и мейна, что могла повлечь за собой неправильную работу класса (например, ему бы присвоили отрицательное значение). Из-за этого и был создан специальный метод для чтения размера стека.

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

Вот пример использования класса стека:

int main()
{
	system("chcp 1251");
	int b,c;
	stack a(1); //Создали объект класса и загрузили в стек первый элемент
	a.push(3); //Загрузили второй элемент
	a.push(5); // Загрузили третий элемент

    a.pop(&b); //Вытолкнули вершину в b

	a.peek(&c);// Считали новую вершину в с

	cout<<"Вершина равна : "<<c<<endl; // На экране выведется 3

	system("pause");

	return 0;
}

Если в коде вам что-то непонятно, то задавайте вопросы в комментариях — я на них всенепременно отвечу.

Исходник стека скачать.

На этом закончу свое небольшое повествование.

Все спасибо за внимание. До встречи в следующей статье.

 

Поддержать сайт и автора: Z208212694629
R429062753687
Яндекс деньги - https://money.yandex.ru/to/410013974912682

Подпишись:
На мой канал youtube
На рассылку свежих статей
На группу ВК
На группу в ОК

Понравилась статья? Поделись с друзьями)

Опубликовать в Google Buzz
Опубликовать в Google Plus
Опубликовать в LiveJournal
Опубликовать в Мой Мир
Опубликовать в Одноклассники

Стек #3: 1 комментарий

  1. Уведомление: Очередь #4 | Всего наилучшего — 73!

Добавить комментарий