Применения стека

Стек

Типы структур данных

ПРИКЛАДНАЯ МЕХАНИКА

Юрий Александрович Балакин

Иван Андреевич Шевелев

Леонид Васильевич Буторин

Елена Борисовна Бусыгина

Учебно-практическое пособие

Подписано к печати:

Тираж:

Заказ №:

Любой набор знаков, рассматриваемый безотносительно к его содер­жательному смыслу, назы­вают данными. Данные обычно изо­бра­жают некоторую информацию, которую мож­но получить, если извес­тен смысл, приписываемый данным. Однако в программи­рова­нии обычно приходится иметь дело именно с данными. Например, разрабатывая систему хранения и поиска текстов, программист может и не знать их содер­жания. Его задача - обеспечить экономное использование памяти и быстрый поиск требу­емых текстов по заданным признакам. Для решения этой задачи достаточно знать лишь коли­чественные характеристики текстов, рассматриваемых как данные. Вообще, ком­пью­теры выполняют только обработку данных, которая заинтересованным лицам представ­ля­ется как обработка информации.

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

Стек – одномерный, динамически изменяемый набор данных. Новый элемент всегда добавляют к одному и тому же концу набора, назы­ваемому вершиной стека. Удале­ние элемента допустимо тоже только из вершины стека. Таким образом, над стеком воз­мож­­ны только две операции: поместить в стек и взять из стека. Стек называют также магазином по аналогии с магазином огне­стрель­ного оружия, в котором патрон послед­ним вставленный в магазин, первым поступает в ствол. По этой же причине дисци­плину работы со стеком называют "последний пришел, первый ушел". В английском языке исполь­зу­ется аббревиатура LIFO (Last In, First Out). Стек может быть реализован в массиве или в списке. Реализация класса STACK, использующего массив, приведена ниже.

// Определение класса

const int MAXSTACK=20; // максимальное число элементов в стеке

class STACK {

// элементы стека -целые числа

private:

int A[MAXSTACK]; // массив для элементов стека

int v; // указатель на вершину стека

// (индекс элемента на вершине стека)

bool OverFlow; // индикатор переполнения стека

bool Empty; // признак "стек пуст"

public:

STACK(); // конструктор

void Push(int NewElement); // поместить в стек

int Pop(); // вытолкнуть из стека

// возвращает выталкиваемый элемент

bool StackOwerFlow(){return OverFlow;}; // Стек переполнен ?

bool StackIsEmpty(){return Empty;}; // стек пуст ?

AnsiString ToString(); // создать строку по содержимому

// стека для показа

};

// Методы класса STACK

#include "Stack.h"

//---------------------------------

STACK::STACK(){ // конструктор

v=-1; // стек пуст

OverFlow=false; // стек не переполнен

Empty=true; // стек пуст

}

//----------------------------------

void STACK::Push(int NewElement){

// поместить в стек значение NewElement

if(v>=MAXSTACK){

// переполнение

OverFlow=true;

return;

}

A[++v]=NewElement;

Empty=false;

}

//-----------------------------------

int STACK::Pop(){

int p=-1; // -1 возвращается, если стек пуст

if(!Empty){

p=A[v--];

if(v<0){

Empty=true;

}

}

return p;

}