Стек

     Определение: Думата стек произлиза от англ. stack - купчина.
Стекът представлява наредена последователност от краен, но променлив брой
еднотипни елементи в който основните операции като включване на нов елемент,
извличане на елемент, се извършват в единия му край. Елементът върху който
се извършва операциите се нарича връх на стека.
Данните се записват във върха на стека и се четат от върха му.
Данните в стека са организирани по правилото - LIFO - Last In
First Out - последен влязъл, пръв излязъл .
В програмите стека се използва най-често за обръщение към
подпрограми ( функции, процедури и т.н.)
Стекът може да се реализира чрез :
     - Масив, но е необходимо предварително да знаем
максималния размер на масива,така че да можем да заделим памет за него.
Използва се, когато броя на елементите е известен предварително и не е голям.
за да не се получават грешки от рода недостиг на място за елементи и
преоразмеряване на масива.
     - Реализиране на динамични структори от данни (списъци, дървета,
графове). Използва се, когато максималния размер на стека не е известен
Заделянето и освобождаването на памет се осъществява в процеса на изпълнение
на програмата.
     - Допълнителна информация :
Думата стек се използва и като област от паметта за временно съхранение на данни. Програмистите на асемблер
използват стек за съхранение на данните от големи към по-малки адреси. Когато се обръщат към подпрограми в
него се съхранява инструкцията, от която трябва да продължи изпълнението на викащата програма. Регистърът SP
( Stack Pointer -стеков указател ) служи като неявен указател към върха на стека. В началото стекът е сегмент
(област от паметта) обикновенно неинициализиран с фиксиран размер, при записване на данни в него
расте в посока на малките адреси. Записване на данни в него се осъществява с инструкцията PUSH - бутам :
     PUSH     двубайтов операнд
и четат данни от него с инструкцията POP - изскачам :
     POP    двубайтов операнд.

   Пример 1 : Създаване на стек чрез масив. Въвеждате числа докато
не натиснете 0 за край на въвеждането. Програмата извежда числата
в обратен ред.

#include <iostream> //for Code Blocks
using namespace std;
int stack[20];
int top=0;
void push (int i)
{ stack [top++]=i; }
int pop()
{ return stack[top--]; }
int main ()
{
int a;
while (a!=0)
{
push(a);
cin>> a;
}
//top--;
while (top!=0) cout<< pop()<< endl;
cout<< endl;
return 0;
}
   Обяснение на примера: Масива е stack и е от 20 елемента, top e
променливата, която сочи върха на стека, чрез функцията push()
въвеждаме числата в стека,а чрез функцията pop () извеждаме от
най-горният елемент числата от стека. Ако не желаете да записва
0 като връх на стека и след това да я извежда премахнете двете
наклонени черти в реда //top--;
   Пример 2 : Създаване на стек чрез динамична структура. Въвеждаме 5 числа,
след това програмата извежда числата в обратен ред.
#include <iostream> //for Code Blocks
using namespace std;
struct link
{ int data;
link *next;
}*top=0, *p;

void push ( int n )
{ p = top;
top = new link;
top->data = n;
top->next = p;}
int pop(int &n)
{
if (top!=0)
{
n = top->data;
p = top;
top = top->next;
delete p;
}
else return 0;
}
int main()
{ int a, i;
for(i=1; i<=5; i++)
{ cin>> a;
push(a);
}
cout<< endl;
while (pop(a))
{
cout<< a<< endl;
}
return 0;
}

   Пример 3 : Въвеждаме цяло число. Програмата извежда сбора на
всички цифри от които е съставено числото.

#include <iostream> //for Code Blocks
using namespace std;
class stack
{
public:
stack();
void push(int);
void pop();
int top() ;
bool empty();
void display();
private:
int n;
int a[20];
};
stack num(int x)
{
stack s;
while(x)
{
s.push(x%10);
x=x/10;
}
return s;
}
int main()
{
int n;
cout<< "Number =";
cin>>n;
num(n).display();
return 0;
}
stack::stack()
{
n=0;
a[0]=0;
}
void stack::push(int x)
{
n++;
a[n]=x;
}
void stack::pop()
{
if (!empty()) n--;
else cout<< "Empty stack!"<< endl;
}
int stack::top()
{
return a[n];
}
bool stack::empty()
{
return n==0;
}
void stack::display()
{
int s=0;
while (!empty())
{
cout<< top();
if (n!=1) cout<< "+";
s=s+top();
pop();
}
cout<< "="<< s;
cout<< endl;
}


Благодаря за вниманието Ви !