Рассмотрим, как операции над стеком реализуются на языке программирования С++ с помощью функций. Простейший стек будем реализовывать на одномерном массиве (векторе), элементом стека будет символьная переменная. Обычно указатель стека обозначается sp (Stack Pointer), в любой момент времени он содержит адрес текущего элемента, являющегося вершиной стека и единственным элементом, доступным в данный момент времени для работы со стеком.
Если исходить из предположения, что вершина стека – последний свободный элемент массива, то операция занесения элемента в стек реализуется присваиванием значения вводимого символа данному элементу. Значение указателя стека при этом должно увеличиваться на единицу, задавая ячейку, как бы находящуюся “над” верхним элементом. При такой реализации представляется вполне возможным заполнение стека с нулевого элемента массива. Если при этом задать начальное значение sp=1, легко можно реализовать все операции работы со стеком.
Начальная установка sp=1.
Загрузка элемента х в стек: stack[sp]=x; sp=sp+1.
Извлечение элемента из стека: sp=sp-1; x=stack[sp];
Необходимо учитывать, что массив содержит конечное число элементов, поэтому при занесении элемента в стек необходимо осуществлять проверку на переполнение, поэтому загрузка элемента в стек должна осуществляться с проверкой на переполнение, тогда операция занесения элемента в стек будет выглядеть следующим образом:
if (sp<=sd) {stack[sp]=x; sp=sp+1}
else //стек полон
Здесь sd – размерность стека (максимальное число элементов массива плюс один, так как в С++ нумерация индексов в массиве начинается с нуля).
При извлечении элемента из стека и при считывании значения верхнего элемента без извлечения необходимо осуществлять поверку стека на пустоту, поэтому операция извлечения реализуется так:
if (sp>1) {sp=sp-1; x=stack[sp]}
else // стек пуст.
Чтение верхнего элемента без извлечения:
if (sp>1) {x=stack[sp-1]}
else // стек пуст.
Поскольку наш стек – последовательность символов, то фрагмент программы с основными функциями работы со стеком будет выглядеть следующим образом:
#define MAX_SIZE 20
char s[MAX_SIZE]; //компоненты стека
int next=0; // позиция стека
int Empty() // проверка на пустоту
{ return next==0; }
int Full() // проверка на переполнение
{ return next==MAX_SIZE; }
void Push() // Занесение элемента в стек
{
if (next==MAX_SIZE)
{
cout<<"Ошибка: стек полон"<<endl;}
else { next++;
cout<<"Что поместить в стек?"<<endl;
cin >> s[next-1];cout<<"Добавлен"<<endl;
}
}
void Pop()// Считывание элемента с удалением
{
if (next==0) cout<<"Ошибка: стек пуст"<<endl;
else {
next--;cout<<"Удален "<<endl;
}
}
Void Stacktop() // считывание элемента без удаления
{
if (next==0) cout<<"Ошибка: стек пуст"<<endl;
else {
cout<<s[next-1]<<endl;
}
}
// Данная функция выводит верхний элемент стека на экран.
Теперь рассмотрим пример конкретной программы, которая позволяет работать с полустатистическим стеком.
// Работа со стеком. Проверка стека на пустоту.
// Добавление элемента в стек. Выборка элемента из стека.
// Проверка стека на переполнение. Печать стека.
// Просмотр содержимого стека без считывания элементов
#include <stdio.h>
#include <dos.h>
#include <iostream.h>
#include <Process.H>
#include <Stdlib.H>
#include <conio.H>
#define MAX_SIZE 200
char s[MAX_SIZE]; //компоненты стека
int next=0; // позиция стека
int Empty()
{ return next==0; }
int Full()
{ return next==MAX_SIZE; }
void Push()
{
if (next==MAX_SIZE)
{
cout<<"Ошибка: стек полон"<<endl;}
else { next++;
cout<<"Что поместить в стек?"<<endl;
cin >> s[next-1];cout<<"Добавлен"<<endl;
}
}
void Printst()
{
if (next==0)
cout<<"Cтек пуст"<<endl;
else
do
{cout<<s[next-1]<<" "<<endl;next--;}
while(next!=0);
}
void Clear()
{ next=0; }
void Pop()
{
if (next==0) cout<<"Ошибка: стек пуст"<<endl;
else {
next--;cout<<"Удален "<<endl;
}
}
void Stacktop()
{
if (next==0) cout<<"Ошибка: стек пуст"<<endl;
else
{cout<<s[next-1]<<endl;}
}
void Showst()
{
int i=0;
if (next==0) {
cout<<"Cтек пуст"<<endl;
}
else { for(i=0;i<next;i++)
cout<<s[i]<<" "<<endl;
}
}
void menu()
{
cout<<"0: Печать стека"<<endl;
cout<<"1: Добавление элемента в стек"<<endl;
cout<<"2: Удаление элемента из стека"<<endl;
cout<<"3: Считывание элемента из стека без удаления"<<endl;
cout<<"4: Проверка стека на пустоту"<<endl;
cout<<"5: Проверка стека на переполнение"<<endl;
cout<<"6: Очистка стека"<<endl;
cout<<"7: Просмотр содержимого стека без считывания элементов"<<endl;
cout<<"8: Выход"<<endl;
}
main()
{
char c;
clrscr();
textcolor(15);
do {
menu();
cin >> c;
clrscr();
switch (c) {
case '0':Printst();getch();break;
case '1':Push();break;
case '2':Pop();getch();break;
case '3':Stacktop();getch();break;
case '4':if (Empty()==1) cout<<"Стек пуст"<<endl;
else cout<<"Стек не пуст"<<endl;getch();break;
case '5':if (Full()==1)cout<<"стек полон"<<endl;
else cout<<"стек не полон"<<endl;getch();break;
case '6':Clear();cout<<
"Стек очищен"<<endl;getch();break;
case '7':Showst();getch();break;
case '8':exit(1);
}
delay(200);
}
while (c!=8);
return 0;
}
В данной программе функция Printst() выводит содержимое стека на экран в любой момент работы со стеком, при этом стек опустошается. Корректная работа с данной структурой действительно не предусматривает вывода всего содержимого без последовательного считывания с удалением элементов. На практике может возникнуть необходимость вывода содержимого стека без удаления из него элементов для отладки работы программы. Возможность такого вывода элементов в данной программе предоставляет функция Showst().
???
Теперь рассмотрим более сложные варианты реализации стеков и работы с ними.
Создадим файл, в котором определены структура дескриптора стека STC и переменная s1 типа STC, а также включены функции, реализующие рассмотренные выше операции над стеками. Дескриптор построен транслятором, память под элементы стека получена динамически. Элементы стека имеют значения типа EL, максимальное число элементов т. В дескрипторе определены указатель начала стека в виде адреса начала динамической памяти и указатели вершины и конца стека в виде целых чисел (индексов элементов стека). Этот файл включается директивой #include в исходный файл с программой для работы со стеком. Предварительно должен быть определен тип элемента EL, например define double EL. Допускаются типы EL, только такие, что переменным этого типа можно присваивать значения оператором «=». Таковыми являются скалярные типы (int, float, double, char) и структурный тип struct.
/* Файл включения для работы со стеком.
Содержит дескриптор стека и функции для работы
со стеком. Включается в головной файл после
определения элемента стека с именем EL */
/* c:\bcpp\bin\incl_stc.c */
#define STC struct st
STC /* дескриптор стека */
{ EL *un; /* Указатель начала стека */
int uk; /* Указатель конца стека */
int uv; /* Указатель вершины стека */
int m; /* число элементов в стеке */
} s1; /* s1 -переменная типа STC */
/* ======================================= */
/* ДОБАВЛЕНИЕ ЭЛЕМЕНТА В СТЕК */
int Push_el(STC *s,EL el)
{ if (s->un == NULL) /*стек не создан */
return -2;
if (s->uv == s->uk)
return -1; /* стек полон */
*(s->un + s->uv+1) = el; ++s->uv;
return 0;
}
/* ====================================== */
/* ВЫБОРКА ЭЛЕМЕНТА ИЗ СТЕКА */
int Pop_el(STC *s,EL *el)
{ if (s->un == NULL)
return -2; /* стек не создан */
if (s->uv < 0)
return -1; /* стек пуст */
else
{ *el = *(s->un + s->uv);
--s->uv;
return 0;
}
}
/* ====================================== */
/* ИЗВЛЕЧЕНИЕ ЗНАЧЕНИЯ ЭЛЕМЕНТА ИЗ СТЕКА БЕЗ УДАЛЕНИЯ ЭЛЕМЕНТА */
int Peek_el(STC *s,EL *el)
{ if (s->un == NULL)
return -2; /* стек не создан */
if (s->uv < 0)
return -1; /* стек пуст */
else
{ *el = *(s->un + s->uv);
return 0;
}
}
/* ====================================== */
/* ОСВОБОЖДЕНИЕ СТЕКА */
int Destroy_stc(STC *s)
{ free(s->un);
s->un = NULL; return 0;
}
/* ====================================== */
/* СОЗДАНИЕ СТЕКА */
int Crt_stc(STC *s)
{ int nn=12; /* число элементов стека */
if (s->un != NULL)
{ printf("\n Старый стек уничтожить? (y/n) ");
flushall();
if (getchar() != 'y')
{ printf("\n Работаем со старым стеком");
return -2;
}
}
s->un = (EL*) calloc(nn,sizeof(EL));
if (s->un == NULL)
return -1; /* память не выделена */
else
{ s->uv = -1; s->uk = nn-1;
s->m = nn; return 0;
}
}
/* *************************************************** */
/* **** Конец файла включения ************** */
Теперь рассмотрим пример программы для работы со стеком в векторной памяти. Элементом стека является переменная типа struct, Хотя в структуре содержится единственный элемент - строка. Это вызвано тем ограничением, о котором говорилось выше. Содержанием элемента стека является команда операционной системы либо имя исполняемого файла. Обработка элемента стека сводится к выполнению этой команды или исполняемого файла.
/* РАБОТА СО СТЕКОМ В ВЕКТОРНОЙ ПАМЯТИ
c:\bcpp\bin\dstackg2.c - головной файл */
#include <stdio.h>
#include <alloc.h>
#include <conio.h>
#include <string.h>
#include <process.h>
typedef struct /*Структура элемента стека с именем EL */
{ char Name[80];
} EL;
EL e;
#include "c:\bcpp\bin\incl_stc.c" /*файл включения */
char *menu[7][40];
static int p=1;
int In_el(EL*);
int Show_stc(STC);
void main_menu(void);
/* ============ГЛАВНАЯ ФУНКЦИЯ =============== */
int main()
{*menu[0]="1.Создание пустого стека";
*menu[1]="2.Включение элемента в стек";
*menu[2]="3.Выборка элемента из стека";
*menu[3]="4.Освобождение стека";
*menu[4]="5.Вывод содержимого стека на экран";
*menu[5]="6.Конец работы";
*menu[6]=" Введите номер строки";
clrscr();
printf(" Работа со стеком в векторной памяти\n");
while(p)
{ main_menu();
clrscr();
}
printf(" Конец pаботы со стеком\n");
return 0;
}
/* ======================================== */
/* ВЫВОД ГЛАВНОГО МЕНЮ */
void main_menu(void)
{ char ns; int pp=1,r=0,i; flushall(); /* чистка буферов */
while (pp)
{ for(i=0;i<7;i++)
printf("\n %s",*menu[i]);
printf("\n");
ns=getchar();
if (ns<'1' || ns>'6')
{ clrscr();
printf("\nОшибка в номере!!Будьте внимательны.");
continue;
}
else pp=0;
switch(ns)
{ case '1':if ( Crt_stc(&s1) == -1)
{ printf ("\n Память под стек не выделена");
getch();
} break;
case '2':if (In_el(&e) == 0)
{ r=Push_el(&s1,e);
if (r == -2)
{ printf("\nСтек не создан!!!");
getch();
}
else
if (r == -1)
{ printf("\n Стек полон!!!");
getch();
}
} break;
case '3': r=Pop_el(&s1,&e);
if (r == -1)
printf("\n Стек пуст");
else
if (r == -2)
printf("\n Стек не создан!!");
else
{ printf("\n Элемент выбран\n");
/* Обработка элемента */
system(e.Name);
}
getch(); break;
case '4': Destroy_stc(&s1); break;
case '5': if (Show_stc(s1) == -1)
{ printf("\n Стек не создан");
getch();
} break;
case '6': p=0;
}
}
}
/* ======================================== */
int In_el(EL *el)
{ printf("\n Ввод элемента стека или ** для отказа от ввода");
printf("\n Введите команду DOS или имя исполняемого файла\n=>");
flushall();
gets(el->Name);
return 0;
}
/* ===========================================*/
int Show_stc(STC s)
{ int i;
if (s.un == NULL)
return -1;
for (i=0; i<=s.uv; i++)
printf("\n %s",s.un[i].Name);
getch();
return 0;
}
/* ******************************************************** */