Написание функций основных операций работы со статическим стеком. Написание программы, демонстрирующей работу всех подпрограмм

1.Условие задачи

Написать функции основных операций работы со статическим стеком.

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

2. Анализ задачи

Дано:  – ограниченная последовательность символов, у которой доступен последний добавленный элемент.

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

Метод решения:

Составим список наиболее распространенных операций со статическим стеком.

1.  Создание стека.

2.  Добавление элемента  в стек.

3.  Удаление элемента из стека.

4.  Проверка, пуст ли стек.

5.  Проверка, полон ли стек.

6.  Просмотр содержимого стека.

3. Структура основных входных и выходных данных:

Статический стек состоит из массива и указателя на последний элемент, называемый вершиной стека:

Стек в памяти компьютера представляется структурой из массива и указателя на вершину стека.

struct  sstack {char A[n]; int beg;};

sstack *A;

4. Алгоритм решения задачи.

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

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

beg=beg+1; A_beg=a;

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

a=A_beg; beg=beg-1;

Чтобы проверить, пуст ли стек достаточно убедиться в том, что значение указателя равно -1.

Если beg=-1 то стек пуст

Если beg>-1 то стек не пуст

Чтобы проверить полноту стека нужно сравнить значение указателя с размерностью массива.

Если beg<=n то стек не полон

Если beg>n то стек полон

В программе, демонстрирующей работу подпрограмм, каждой операции будет дан свой номер(i).

Стек в памяти компьютера представляется структурой из массива и указателя на вершину стека.

struct  sstack {char A[n]; int beg;};

sstack *A;

5. Текст программы:

Модуль  SSTACK.CPP

#include <stdio.h>

const n=20;

struct sstack {char A[n];int beg;};

void newstack(sstack *S) {S->beg=-1;}

void instack(sstack *S, char c) {S->beg++;S->A[S->beg]=c;}

void outstack(sstack *S, char *c){*c=S->A[S->beg]; S->beg--;}

int pust(sstack *S) {if (S->beg==-1) return 1;

return 0;}

void smotrim(sstack *S) {for (int i=S->beg;i>=0;i--) printf("%c",S->A[i]);}

int polon(sstack *S){if (S->beg==n-1) return 1; return 0;}

Модуль  PROGA.CPP(Главный)

#include <stdio.h>

#include "Z:\SSTACK.CPP"

void main()

{

char a; int s=0; char b;

printf("Создать стек? y/n..");

scanf("%c", &a);

if (a=='y')

   { sstack A; newstack(&A);

   go: printf("\nВыберите действия\n");

       printf("[1] Положить элемент в стек\n");

       printf("[2] Взять элемент из стека \n");

       printf("[3] Проверить, пуст ли стек\n");

       printf("[4] Просмотреть содержимое стека\n");

       printf("[0] Выйти из программы\n");

       scanf("%i", &s);

       switch (s){

       case  1 :{if (polon(&A)) {printf("Стек полон!!\n"); getchar(); goto go;} else {getchar(); printf("Введите символ.."); char b; scanf("%c", &b); instack(&A,b);}  goto go;} break;

       case  2 :{if (!pust(&A)){outstack(&A, &b); printf("Взят элемент %c",b);} goto go;} break;

       case  3 :{if (!pust(&A)) printf("стек не пуст"); else printf("Стек пуст"); goto go;} break;

       case  4 :{if (!pust(&A)) smotrim(&A); goto go;} break;

            }

   }

}

6.Набор тестов

№	Действие	Результат	Примечание
1	Переполнение стека	Сообщение «стек полон» И возврат в меню	Статический стек ограничен 20 элементами.
2	Взятие из пустого стека	Возврат в меню	Взятие из пустого стека невозможно, поэтому, сначала программа проверяет стек на пустоту, а затем, если он  не пуст, продолжает работу, иначе возвращается в меню.
3	s=1 b=’a’		В стек положили символ ‘a’.
4	s=4	“a”	На экране выведено содержимое стека.
5	s=2		Из стека взят единственный элемент.

7.  Вывод: На всех тестах программа выдала ожидаемый результат. Следовательно, задача решена верно.