CPP-101: Класове и обекти

Пример: Стек

Нека като пример разгледаме дефинирането на клас Stack, моделиращ абстрактния тип стек. Основните операции, които могат да се извършват с един стек са:

• добавяне на нов елемент в стека – push();
• изваждане на последния добавен елемент от стека – pop().

Поради тази причина, често стекът се нарича FILO (First In, Last Out) – първи влязъл, последен излязъл.

Възможните начини за реализиране на стек са няколко. Най-простият вариант е да се използва масив, като ако е необходимо стекът да е динамичен (максималният брой на елементите, които могат да се поберат в стека да не е фиксиран по време на компилацията на програмата) може да се използва динамичен масив. Друг вариант за реализирането на стека е да се използва списък – например едносвързан или двусвързан списък. Независимо от начина на реализация операциите които могат да се извършват със стека са едни и същи – push() и pop().

Като пример ще разгледаме възможно най-простата реализация на класа Stack, която използва масив с фиксиран размер. Предложената реализация на класа Stack има две член-променливи: член-променливата data_, която е масивът в който се съхраняват елементите на стека, и член-променлива top_, която е индексът на следващия свободен елемент на
масива.

const int STACK_SIZE=10;

class Stack {
    int data_[STACK_SIZE];
    int top_;
public:
    Stack() {
        top_=0;
    }
    void push(int val) {
        if(top_0) {
            return data_[--top_];
        }
        return 0;
    }
    bool is_empty() {
        return top_==0;
    }
    bool is_full() {
        return top_==STACK_SIZE;
    }
};

Основните операции със стека са операциите push и pop. Операцията push добавя нов елемент в стека, като го поставя в масива data_ на мястото сочено от индекса top_. След това индексът top_ се увеличава с единица, за да сочи към следващия свободен елемент. Обърнете внимание, че ако стекът е пълен, т.е. top_>=STACK_SIZE, то операцията push не прави нищо.

Операцията pop връща стойността на следващия елемент от стека и го изтрива. За тази цел първо се намалява стойността на top_ с единица и след това се връща стойността на елемента от масива с индекс новата стойност на top_. Обърнете внимание, че ако стекът е празен, операцията pop() връща нула без да дава съобщение за грешка.

Към реализацията на стека са добавени две допълнителни операции, които проверяват дали стекът е празен is_empty() или е пълен – is_full().

Като пример за използване на класа Stack нека разгледаме програма, която обръща стрингове:

int main(int arch, char* argv[]) {
    char* msg="Hello!";
    char buff[10];
    
    Stack st;
    
    for(char* p=msg;*p!='\0';p++)
        st.push(*p);

    char* p=buff;
    while(!st.is_empty())
        *p++=st.pop();
        
    *p='\0';
    return 0;
}

В ред 2 е дефиниран стрингът msg="Hello!". Целта на програмата е да се получи нов стринг, в който буквите са подредени в обратен ред. Новият стринг ще се конструира в буфера buff. За обръщането на реда на символите се използва стекът Stack st, дефиниран в ред 4. Цикълът в редовете 5–6 обхожда всички букви от стринга msg и ги слага в стека, като използва операцията st.push(). След изпълнението на този цикъл, всички символи от оригиналния стринг msg са вкарани в стека. Следващия цикъл 8–9 изважда всички букви от стека като използва операцията st.pop() и ги подрежда в буфера buff. Тъй като стекът е LIFO (Last In First Out) структура, първият символ, който ще извадим от стека е последният символ, който е поставен в стека, т.е. последният символ от стринга msg, и т.н. Накрая трябва да добавим терминираща '\0', за да могат символите в буфера buff да се интерпретират като стринг.