Инструменты пользователя

Инструменты сайта


stack

Назад

Стек

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

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

Наиболее наглядным примером организации стека служит детская пирамидка, где добавление и снятие колец осуществляется как раз согласно определению стека.

Основные операции над стеком и его элементами.

  1. Добавление элемента в стек. Push
  2. Удаление элемента из стека. Pop
  3. Проверка, пуст ли стек. (Стек считается «пустым», если указатель вершины совпадает с указателем нижней границы.) IsEmpty
  4. Просмотр элемента в вершине стека без удаления. IsFull
  5. Очистка стека. Clear
#include <iostream>
#include <time.h>
using namespace std;
class Stack
{
private:
	enum {empty = -1, full = 5};
	int top;
	char str[full + 1];
public:
	Stack()
	{
		//Изначально стек пуст
		top = empty;
	}
	void Push (char c)
	{
		// Если в стеке есть место, то увеличиваем на вершину стека и вставляем новый элемент
		if (!IsFull())
			str[++top] = c;
	}
	char Pop ()
	{
		// Если в стеке есть элементы, то возвращаем верхний и уменьшаем указатель на вершину стека
		if (!IsEmpty())
			return str [top--];
		// Если в стеке элементов нет
		else 
			return 0;
	}
	bool IsEmpty ()
	{
		//Проверка, пуст ли стек.
		return top == empty;
	}
	bool IsFull ()
	{
		//Проверка, полный ли стек.
		return top == full;
	}
	void Clear()
	{
		//Очистка стека
		top = empty;
	}
};
void main()
{
	srand (time(0));
	Stack stack;
	char c;
	//Пока стек не заполнится
	while (!stack.IsFull())
	{
		c = rand ()%4+2;
		stack.Push(c);
	}
	//Пока стек не освободится
	while (c=stack.Pop())
	{
		cout<<c<<" ";
	}
}

Очередь

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

#include <iostream>
#include <time.h>
using namespace std;
class Queue
{
private:
	// Очередь
	int * Wait;
	// Текущий размер очереди
	int QueueLength;
	// Максимальный размер очереди
	int MaxQueueLength;
public:
	Queue(int m)
	{
		//получаем размер
		MaxQueueLength=m;
		//создаем очередь
		Wait=new int[MaxQueueLength];
		// Изначально очередь пуста
		QueueLength = 0;
	}
 
	void Add (int c)
	{
		// Если в очереди есть, то увеличиваем количество значений и вставляем новый элемент
		if(!IsFull())
			Wait[QueueLength++] = c;
	}
 
	int Extract()
	{
		// Если в очереди есть элементы, то возвращаем тот, 
		// который вошел первым и сдвигаем очередь	
		if(!IsEmpty()){
			//запомнить первый
			int temp=Wait[0];
 
			//сдвинуть все элементы
			for(int i=1;i<QueueLength;i++)
				Wait[i-1]=Wait[i];
 
			//уменьшить количество
			QueueLength--;
 
			//вернуть первый(нулевой)
			return temp;
		}
 
		else // Если в стеке элементов нет
			return -1;
	}
 
	bool IsFull ()
	{
		return QueueLength == MaxQueueLength;
	}
 
	bool Queue::IsEmpty()
	{
		// Пуст?
		return QueueLength == 0;
	}
 
	void Show()
	{
		for(int i=0;i<QueueLength;i++)
		{
			cout<<Wait[i]<<" ";
		}
		cout<<endl;
	}	
 
	~Queue()
	{
		//удаление очереди
		delete[]Wait;
	}
 
};
void main ()
{
	srand(time(0));
	//создание очереди из 25 элементов
	Queue QU(25);
 
	//заполнение части элементов
	for(int i=0;i<5;i++)
	{
		QU.Add(rand()%50);
	}
 
	//показ очереди
	QU.Show();
 
	//извлечение элемента
	QU.Extract();
 
	//показ очереди
	QU.Show();
}

Кольцевая очередь

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

В качестве самого простого примера, можно привести известный вам с детства круговорот воды в природе, или трамваи, курсирующие по круговому маршруту.

#include <iostream>
#include <time.h>
using namespace std;
class QueueRing
{
private:
	//очередь
	int *Wait;
	//Мах размер очереди
	int MaxQueueLength;
	// Текущий размер очереди
	int QueueLength;
public:
 
	QueueRing(int m)
	{
		//получаем размер
		MaxQueueLength=m;
		//создаем очередь
		Wait=new int[MaxQueueLength];
		// Изначально очередь пуста
		QueueLength = 0;
 
	}
 
	~QueueRing()
	{
		delete [] Wait;
	}
 
	void Add (int c)
	{
		// Если в очереди есть, то увеличиваем количество значений и вставляем новый элемент
		if(!IsFull())
			Wait[QueueLength++] = c;
 
	}
 
	bool IsFull()// Проверка на переполнение очереди
	{
		// Полон?
		return QueueLength == MaxQueueLength;
	}
 
	bool IsEmpty()// Проверка существования элементов в очереди
	{
		// Пуст?
		return QueueLength == 0;
	}
 
	bool Extract()// Извлечение элемента
	{
		// Если в очереди есть элементы, то возвращаем тот, который вошел первым и сдвигаем очередь	
		if(!IsEmpty())
		{
			//запомнить первый
			int temp=Wait[0];
 
			//сдвинуть все элементы
			for(int i=1;i<QueueLength;i++)
				Wait[i-1]=Wait[i];
 
			//забрасываем первый "вытолкнутый элемент в конец"
			Wait[QueueLength-1]=temp;
			return 1;
		}
		else return 0;
	}
 
	void Show ()
	{
		for (int i=0;i<QueueLength;i++)
		{
			cout<<Wait[i]<<" ";
		}
		cout<<endl;
	}
 
	void Clear()// Количество элементов в очереди
	{
		// Эффективная "очистка" очереди 
		QueueLength = 0;
	}
 
	int GetCount()// Количество элементов в очереди
	{
		// Количество присутствующих в стеке элементов
		return QueueLength;
	}
};
void main()
{
	srand(time(0));
 
	//создание очереди
	QueueRing QUR(25);
 
	//заполнение части элементов
	for(int i=0;i<5;i++){
		QUR.Add(rand()%50);
	}
	//показ очереди
	QUR.Show();
 
	//извлечение элемента
	QUR.Extract();
	//показ очереди
	QUR.Show();
 
}

Очередь с приоритетом

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

Существует несколько видов приоритетных очередей:

#include <iostream>
#include <time.h>
using namespace std;
class QueuePriority
{
private:
	// Очередь
	int * Wait;
	// Приоритет
	int * Pri;
	// Максимальный размер очереди
	int MaxQueueLength;
	// Текущий размер очереди
	int QueueLength;
public:
 
	QueuePriority(int m)
	{
		//получаем размер
		MaxQueueLength=m;
		//создаем очередь
		Wait=new int[MaxQueueLength];
		Pri=new int[MaxQueueLength];
		// Изначально очередь пуста
		QueueLength = 0;
	}
	~QueuePriority()
	{
		delete []Wait;
		delete []Pri;
 
	}
 
	bool IsEmpty()
	{
		// Пуст?
		return QueueLength == 0;
	}
 
	bool IsFull()
	{
		// Полон?
		return QueueLength == MaxQueueLength;
	}
 
	void Add(int c,int p)
	{
		// Если в очереди есть, то увеличиваем количество значений и вставляем новый элемент
		if(!IsFull())
		{
			Wait[QueueLength] = c;
			Pri[QueueLength] = p;
			QueueLength++;
		}
	}
 
	int Extract()
	{
		// Если в очереди есть элементы, то возвращаем тот, который вошел первым и сдвигаем очередь	
		if(!IsEmpty())
		{
			//пусть приоритетный элемент - нулевой
			int max_pri=Pri[0];
			//а приоритетный индекс = 0
			int pos_max_pri=0;
 
			//ищем приоритет
			for(int i=1;i<QueueLength;i++)
				//если встречен более приоритетный элемент
				if(max_pri<Pri[i])
				{
					max_pri=Pri[i];
					pos_max_pri=i;
				}
 
				//вытаскиваем приоритетный элемент
				int temp1=Wait[pos_max_pri];
 
				//сдвинуть все элементы
				for(int i=pos_max_pri;i<QueueLength-1;i++)
				{
					Wait[i]=Wait[i+1];
					Pri[i]=Pri[i+1];
				}
				//уменьшаем количество
				QueueLength--;
				// возврат извлеченного элемента	
				return temp1;
		}
		else return -1;
	}
	void Show()
	{
		//демонстрация очереди
		for(int i=0;i<QueueLength;i++)
		{
			cout<<Wait[i]<<" - "<<Pri[i]<<"\n\n";
		}
		cout<<endl;
	}
};
 
void main()
{
	srand(time(0));
 
	//создание очереди
	QueuePriority QUP(25);
 
	//заполнение части элементов
	for(int i=0;i<5;i++)
	{
		//значения от нуля до ста 
		//и приоритет от 0 до 13
		QUP.Add(rand()%100,rand()%12);
	}
	//показ очереди
	QUP.Show();
 
	//извлечение элемента
	int Pri=QUP.Extract();
 
	//показ очереди
	QUP.Show();
	cout<<"QUP="<<Pri<<endl;
}

Односвязный список

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

Односвязный список создать и реализовать достаточно просто. Каждый элемент списка представляется структурой языка C++ с двумя полями:

  1. Информационное поле, которое в общем случае может представлять собой произвольное количество полей разных типов. Вполне естественно, что если значением переменной p является указатель на элемент списка, то обращаясь к обозначению (p) с помощью стрелки (→) и имени соответствующего поля, можно манипулировать со значением любого поля информационной части.
  2. Указатель на следующий элемент списка.
#include <iostream>
using namespace std;
 
struct Element
{
	// Данные
	char data;
	// Адрес следующего элемента списка
	Element * Next;
};
 
class List
{
	// Адрес головного элемента списка
	Element * Head;
	// Адрес головного элемента списка
	Element * Tail;
	// Количество элементов списка
	int Count;
 
public:
	List()
	{
		// Изначально список пуст
		Head = Tail = NULL;   
		Count = 0;
	}
 
	// Добавление элемента в список  (Новый элемент становится последним)
	void Add(char data)
	{
		// создание нового элемента
		Element * temp = new Element;
 
		// заполнение данными
		temp->data = data;
		// следующий элемент отсутствует
		temp->Next = NULL;
		// новый элемент становится последним элементом списка если он не первый добавленный
		if(Head!=NULL)
		{
			Tail->Next=temp;
			Tail = temp;
		}
		// новый элемент становится единственным
		// если он первый добавленный
		else{
			Head=Tail=temp;
		}
	}
 
	// Удаление элемента списка (Удаляется головной элемент)
	void Del()
	{
		// запоминаем адрес головного элемента
		Element * temp = Head;
		// перебрасываем голову на следующий элемент
		Head = Head->Next;
		// удаляем бывший головной элемент
		delete temp;
	}
	// Удаление всего списка
	void DelAll()
	{
		// Пока еще есть элементы
		while(Head != 0)
			// Удаляем элементы по одному
			Del();
	}
 
	void Print()
	{
		// запоминаем адрес головного элемента
		Element * temp = Head;
		// Пока еще есть элементы
		while(temp != 0)
		{
			// Выводим данные
			cout << temp->data;
			// Переходим на следующий элемент
			temp = temp->Next;
		}
 
		cout <<endl;
	}
 
	int GetCount()
	{
		// Возвращаем количество элементов
		return Count;
	}
 
	~List()
	{
		DelAll();
	}
};
 
 
 
void main()
{
	List lst;
 
	char s[] = "Hello, World !!!";
 
	cout << s <<endl;
 
	// Определяем длину строки
	int len = strlen(s);
 
	// Загоняем строку в список
	for(int i = 0; i < len; i++)
		lst.Add(s[i]);
 
	lst.Print();
 
	// Удаляем три элемента списка
	lst.Del();
	lst.Del();
	lst.Del();
 
	lst.Print();
}

Удаляем заданы символ

	void Del(char c)
	{
		Element *i, *j;
 
		if (Head->data == c)
		{
			Del(c);
 
			return;
		}
 
		if (Head != Tail)
		{
			i = Head;
			j = Head->Next;
 
			while (j->data != c)
			{
				if (j->Next == 0)
					return;
 
				i = i->Next;
				j = j->Next;
			}
 
			i->Next = j->Next;
 
			if (Tail == j)
				Tail = i;
 
			delete j;
		}
	}

Бинарное дерево

Бинарное дерево (binary tree) - это упорядоченная древовидная динамическая структура. Каждый элемент (узел) дерева имеет не более двух элементов следующих за ним (потомков) и не более одного предыдущего (родителя).