Стек

1. Понятие за стек

Стекът е крайно, линейно наредено множество от елементи, които се обработват на принципа LIFO (Last Input First Output), т.е. елементи могат да се включват и изключват само в единия му край, наричан връх на стека.

При прочитане на елемент от върха на стека, заеманата от него памет се освобождава.

2. Програмна реализация на стек

2.1. Реализация чрез масив:

Дефинира се масив и два указатела – един за базата(BP) и един за върха(SP). Типът на елементите на масива трябва да е еднакъв. Ако се налага да се работи с разнотипни елементи, то се дефинира масив от указатели към тези елементи.

Стек с реализиран с масив

#include <iostream.h>

#include <stdlib.h>

#define N 100 //размер на масива, а следователно и на стека

float A[N]; //масива, чрез който се създава стека

int BP=-1, //индекс на базата на стека

SP=-1; //индекс на върха на стека

//ф-я, която записва в стека стойността на х

void WriteStack(float x)

{//ако индекса на върха сочи последният елемент от масива - препълване

if(SP==N-1)

cout<<"\nСтекът е препълнен\n";

else A[++SP]=x; //в противен случай увеличава индекса за върха на

//стека (SP) с 1 и записва стойността на х

}

//ф-я, която чете от стека най-горната стойност

void ReadStack()

{

if (SP==BP) cout<<"\nСтекът е празен\n ";

else cout<<A[SP--]<<'\n';

}

//ф-я за изчистване на стека

void EmptyStack()

{

BP=-1;SP=-1;

}

//ф-я, която показва съдържанието на стека

void ShowStack()

{

cout<<"Съдържанието на стека е следното:\t";

for(int i=0;i<=SP;i++)

cout<<A[i]<<' ';

}

void main(void)

{ int i;

float x;

for(;;)

{

cout<<"1.Запис в стека\n";

cout<<"2.Четене от стека\n";

cout<<"3.Изчистване на стека\n";

cout<<"4.Край\n";

cout<<"Изберете команда (от 1 до 4) ";cin>>i;

switch(i)

{

case 1: cout<<"Въведете стойност за записване в стека ";cin>>x;

WriteStack(x);

break;

case 2: ReadStack();

break;

case 3: EmptyStack();

break;

case 4: exit(0);

}

ShowStack();

}

2.2. Реализация чрез линеен списък

Клас Stack

Стекът е динамична структура от данни, изградена на принципа LIFO (последен влязъл, първи излязъл). Тя може да бъде реализирана с помощта на линеен едносвързан списък, като се използват само член-функциите за добавяне в края и изключване в края на списъка. За реализиране на структурата стек съм създала класа Stack, наследник на класа LList. В него, като лични данни съм дефинирала указателите First и End, съответно за първи (база на стека) и последен (връх на стека) елемент на стека. В конструктора тези указатели се нулират. В деструктора се извиква член-функцията Clear(), която унищожава стека, освобождава заетата от него памет и нулира указателите First и End.

Член-функцията Push() реализира добавяне на елемент към стека. Тя има един аргумент от тип Node (указател към елемента, който ще се добавя). Тя извиква член-функцията на базовия клас Add_end(), като й подава за аргументи указателят към новия елемент и адресите на указателите First и End.

Член функцията Pop() изключва прочита и изключва елемента от върха на стека. В нея се извеждат данните на елемента и се извиква член-функцията Del_end() на базовия клас, за да унищожи този елемент. В случай, че стека е празен (End=NULL), се извежда съобщение.

Програмната реализация е следната:

void Stack::Pop()

{

if(End)

{

End->output();

Del_end(&First,&End);

}

else cout<<"The Stack is empty.\n";

}

Член-функцията Clear() унищожава целия стек, освобождава заетата от елементите му памет и нулира указателите First и End.

Член-функцията OutList () извиква съответната член-функция на базовия клас за да изведе съдържанието на стека.

Дефиниция на класа Stack.

class Stack : public LList

{

Node *First,*End;

public:

Stack();

virtual ~Stack();

void Push(Node *el);

void Pop();

void Clear();

void OutList();

};

Дефиницията на класа Stack е съхранена във файл с името Stack.h, а дефинициите на член-функциите - във файл с името Stack.cpp.

StackDemo

Програмата StackDemo демонстрира възможностите на класа Stack.За целта съм създала главна функция main, в която съм дефинирала 2 обекта А и B от тип Stack. Във възлите на стека А са разположени обекти от тип MyFloatList, а във възлите на стека B са разположени обекти от тип MyCharList. Указателят elA е от тип MyFloatList, а elB – от тип MyCharList и се използват за съхраняване на адресите на новосъздадените елементи. Целочислената променлива k се използва за избор на точка от менюто.

В тялото на тази функция се извежда меню, състоящо се от 7 команди. Всяка една от командите се избира чрез нейния номер. Оператор switch осигурява изпълнението на избраното действие.

Безкраен цикъл for осигурява многократното извеждане на менюто. От програмата се излиза, като се въведе номера на командата End. За по-добра нагледност при всяко завъртане на цикъла се показва съдържанието на стековете.

Програмната реализация е следната:

void main()

{

Stack A,B;

MyFloatList *elA;

MyCharList *elB;

int k;

for(;;)

{

cout<<"\n1.Add to Stack A\n";

cout<<"2.Pop from Stack A\n";

cout<<"3.Add to Stack B\n";

cout<<"4.Pop from Stack B\n";

cout<<"5.Clear A\n";

cout<<"6.Clear B\n";

cout<<"7.End\n";

cout<<"Choice (1-5):";cin>>k;

switch(k)

{

case 1:elA=new MyFloatList; elA->input(); A.Push(elA); break;

case 2:cout<<"A: ";A.Pop();cout<<'\n'; break;

case 3:elB=new MyCharList; elB->input(); B.Push(elB); break;

case 4:cout<<"B: ";B.Pop();cout<<'\n'; break;

case 5:A.Clear(); break;

case 6:B.Clear(); break;

case 7:exit(0); break;

default:cout<<"Error!";

}

cout<<"A: ";A.OutList();

cout<<"B: ";B.OutList();

}

Главната функция е съхранена във файл с името StackDemo.cpp. За да се компилира програмата е необходимо да се създаде файл-проект, в който да се включат файловете:

· StackDemo.cpp

· List.cpp

· MyFloatList.cpp

· MyCharList.cpp.

Целият сорс можете да изтеглите от тук.