Стек в С++

СТЕК


1. Описание на структурата стек

Стекът е крайна редица от елементи от един и същи тип. Възможен е достъп само до елемента, който е на върха на стека, и той е пряк. Операциите включване и изключване на елемент са допустими само в началото /върха/.

Такава структура се нарича LIFO структура – „Last In, First Out” – Последен влязъл, първи излязъл. От английски “stack” означава купчина.

Можем да наподобим стека на кутия с топчета пинг-понг – поставяме ги и ги слагаме само от едно място и имаме достъп само до топката, която е най-отгоре.

Пример за приложение на тази структура в информатиката е команди Undo и Redo.










...



NULL


p

І елем. ІІ елемент последен елемент


Стекът се представя по два начина в ОП: последователно и свързано, като ние ще разглеждаме втория подход:

  • началото се указва с указател р

  • елементите се записват в произволни адреси в динамичната памет, всеки елемент съдържа указател към следващия, затова и тук всеки елемент се представя чрез 2 полета: информационно и адресно. Адресното поле на последния елемент съдържа константата NULL.


2. Дефиниране на стек

Дефинираме структурата глобално – преди всички функции, както дефинираме.

struct Stack

{

тип inf;

Stack *link;

};


3. Създаване на стек

Функция Create ще получи като параметър указател към стека, който в началото ще бъде неопределен. Тя ще го промени, затова трябва да го предадем като параметър-променлива, т.е. &р.

Първоначално ще създадем празен стек, т.е. указателят p ще сочи NULL.

След това, докато потребителя въвежда данни от клавиатурата, ще добавяме новия елемент в началото на стека.

Да опишем добавянето на новия елемент – създаваме нова динамична променлива, инициализираме полетата й inf и link и насочваме р към новия елемент:

р








...



NULL

q


х




void Create (Stack * &p)

{

p=NULL;

int x;

while(cin>>x)

{

Stack *q=new Stack;

q->inf=x;

q->link=p;

p=q;

}

}


Забележка: Ако типът на елементите е char, въвеждането става с while(cin.get(x))…


4. Извеждане на елементите на стека

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

void Izhod (Stack *&p)

{


Други реферати:
Древен Египет–Старо царство
Институцията исторически музей
Микенските маски
Музеите в Латинска Америка
Симбиозата между чужди и родни обреди в българския съвременен сватбен ритуал като културен феномен


Изтегли реферата



Симбиозата между чужди и родни обреди в българския съвременен сватбен ритуал като културен феномен - Facebook Image
Сайтът се поддържа от DH Studio | pomagalo1.com © 2012 | Общи условия