Лабораторная работа № 1. "ПОЛУСТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ"

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

Цель работы: исследовать и изучить стеки.


Задача работы: овладеть навыками написания программ по исследованию стеков на языке программирования ПАСКАЛЬ .


Порядок работы :

• 
  изучить описание лабораторной работы;
• 
  по заданию, данному преподавателем, разработать алгоритм программы решения задачи;
• 
  написать программу на языке ПАСКАЛЬ;
• 
  отладить программу;
• 
  решить задачу;
• 
  оформить отчет.

Краткая теория

Понятие очереди всем хорошо известно из повседневной жизни. Элементами очереди в общем случае являются заказы на то или иное обслуживание: выбить чек на нужную сумму в кассе магазина, получить нужную информацию в справочном бюро, выполнить очередную операцию по обработке детали на данном станке в автоматической линии и т.д.

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

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

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

1. 
   При первой из дисциплин заказ, поступивший в очередь первым, выбирается первым для обслуживания (и удаляется из очереди). Об этом говорит сайт https://intellect.icu . Эту дисциплину обслуживания принято называть FIFO (First input-First output, т.е. первый пришел - первый ушел). Очередь открыта с обеих сторон.

2. 
   Вторую дисциплину принято называть LIFO (Last input - First output, т.е. последний пришел - первый ушел), при которой на обслуживание первым выбирается тот элемент очереди, который поступил в нее последним. Очередь такого вида в программировании принято называть СТЕКОМ (магазином) - это одна из наиболее употребительных структур данных, которая оказывается весьма удобной при решении различных задач.

В силу указанной дисциплины обслуживания, в стеке доступна единственная его позиция, которая называется ВЕРШИНОЙ стека - эта позиция, в которой находится последний по времени поступления в стек элемент. Когда мы заносим новый элемент в стек, то он помещается поверх вершины и теперь уже сам находится в вершине стека. Выбрать элемент можно только из вершины стека; при этом выбранный элемент исключается из стека, а в его вершине оказывается элемент, который был занесен в стек перед выбранным из него элементом (структура с ограниченным доступом к данным).

 

Алгоритм

ОПЕРАЦИИ НАД СТЕКАМИ:

- PUSH ( s , i ) - занесение элемента в стек, где s - название стека, i - элемент, который заносится в стек;

- POP ( s ) - выборка элемента из стека. При выборке элемент помещается в рабочую область памяти, где он используется;

- EMPTY ( s ) - проверка стека на пустоту (true - пуст, false - не пуст);

- STACKTOP ( s ) - чтение верхнего элемента без его удаления.


Фрагмент программы создания стека (необходимые процедуры)


Program STACK;

const

max_st=50;

const

max_st=50;

var

st,st2: array[1..max_st] of integer;

n:integer;


function empty:boolean; {Проверка стека на наличие элементов в нем}

begin

empty:=n=0

end;


procedure push(a:char); {Поместить элемент в стек}

begin

inc(n);

st[n]:=a;

end;


procedure pop(var a:char); {Извлечь элемент из стека}

begin

a:=st[n];

dec(n);

end;


function full:boolean; {Проверка на переполнение}


begin

Full:=n=max_st

end;


procedure stacktop(var a:char); {Узнать верхний элемент}

begin

a:=st[n];

end;


begin {Основная программа}

.

.

end.

Задания

• 
  Ввести символы, формируя из них стек.

Варианты :

1.Поменять местами первый и последний элементы стека.

2.Развернуть стек, т.е. "дно" стека сделать вершиной, а вершину - "дном".

3.Удалить элемент, который находится в середине стека, если нечетное число элементов, а если четное, то два средних.

4.Удалить каждый второй элемент стека.

5.Вставить символ '*' в середину стека, если четное число элементов, а если нечетное, то после среднего элемента.

6.Найти минимальный элемент и вставить после него 0.

7.Найти максимальный элемент и вставить после него 0.

8.Удалить минимальный элемент.

9.Удалить все элементы, равные первому.

10.Удалить все элементы, равные последнему.

11.Удалить максимальный элемент.

12.Найти минимальный элемент и вставить на его место 0.

• 
  Вывести полученный стек на экран.

• 
  Распечатать полученный стек.

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

Из статьи мы узнали кратко, но содержательно про полустатические структуры данных