Лабораторная работа №7

Стек

Цель работы:

Закрепить технику работы с динамическими структурами данных на примере стека. Рассмотреть основные операции со стеком и познакомится с типичными примерами применения стека.

Общие сведения

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

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

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

Таким образом, описать стек, содержащий, например, целые числа, можно следующим образом:

Type
  PStack = ^TStack;
  TStack = Record
     Data : Integer;
     Next : PStack;
  end;
Var
  Stack : PStack;

Если стек пуст, то значение переменной Stack равно nil.

Примеры

Занесение в стек.

Занесение в стек производится аналогично вставке нового элемента в начало списка:

Var
  x : PStack;
……………
  New(x);
  x^.Data := …….;
  x^.Next := Stack;
  Stack := x;
……………

Извлечение элемента из стека.

В результате выполнения этой операции некоторой переменной N должно быть присвоено значение первого элемента стека и изменено значение указателя на начало стека:

Var
  N : Integer;
  x : PStack;
………………….
  N := Stack^.Data;
  x:= Stack;
  Stack := Stack^.Next;
  Dispose(x);
………………….

Контрольные вопросы

1. В чем сходство и отличие динамических структур данных типа список и стек?

2. Можно ли добраться до середины или конца («дна») стека, минуя его начало («вершину»)?

3. Приведите примеры из жизни, где встречается «принцип стека».

4. Оформите в виде процедуры Push занесение в стек значения.

5. Оформите в виде процедуры Pop извлечение значения из стека.

Варианты заданий

1. Подсчитать количество элементов в стеке.

2. Сформировать стек, содержащий строки и сохранить его в текстовом файле.

3. Восстановить стек, содержащий строки, из текстового файла.

4. Написать функцию, которая вычисляет среднее арифметическое элементов стека.

5. Написать процедуру присоединения стека S2 к стеку S1.

6. Определить симметричность произвольного текста любой длины. Текст должен оканчиваться точкой. Задачу решить с помощью двух стеков.

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

8. В данном тексте проверить соответствие открытия и закрытия скобок.

9. Напечатать содержимое текстового файла, выписывая символы каждой его строки в обратном порядке.

10. Проверить, является ли строка палиндромом.

Назад На главную

Учебник по языку Pascal Лабораторные работы по программированию Справочник

Нет комментариев.

Оставить комментарий: