Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
TA_last_u3.doc
Скачиваний:
2
Добавлен:
01.04.2025
Размер:
3 Мб
Скачать
☆

Абстрактні типи даних (атд) Інтерфейс абстрактного типу даних стека

Визначимо АТД стека через оголошення загальнодоступних функцій. При цьому передбачається, що представлення стека і будь-який інший код, що залежить від реалізації, є приватними, щоб можна було змінювати реалізації, не змінюючи код клієнтських програм. Крім того, у цьому інтерфейсі застосовується шаблон, що дозволяє програмам-клієнтам використовувати стеки, що містять об'єкти будь-яких класів, а в реалізаціях використовувати ключове слово Item як позначення типу об'єктів стека. Аргумент конструктора STACK задає максимальна кількість елементів, який можна помістити в стек.

template <class Item>

class STACK {

private: // програмний код, що залежить від реалізації

public:

STACK(int);

int empty() const;

void push(Item item);

Item pop();

}

Реалізація черги fifo на базі масиву

До вмісту черги відносяться всі елементи масиву, розташовані між індексами head і tail; при цьому враховується перехід з кінця на початок масиву. Якщо індекси head і tail рівні, черга вважається порожній, однак якщо вони стали рівними в результаті виконання операції put, черга вважається повною. Як звичайно, перевірка на такі помилкові ситуації не виконується, але розмір масиву робиться на 1 більше максимальної кількості елементів черги, очікуване програмою-клієнтом. При необхідності програму можна розширити, включивши в неї подібного роду перевірки.

template <class Item>

class QUEUE

{

private:

Item *q; int N, head, tail;

public:

QUEUE(int maxN)

{q = new ltem[maxN+l];

N = maxN+1; head = N; tail = 0;}

int empty () const

{return head % N = tail;}

void put(Item item)

{q[tail++] = item; tail = tail % N;}

Item get()

{head = head % N; return q[head++];}

}

Реалізація черги fifo на базі зв'язного списку

Розходження між чергою FIFO і стеком магазинного типу полягає в тому, що нові елементи вставляються в кінець списку, а не в його початок. Отже, у цьому класі зберігається покажчик tail на останній вузол списку, і, таким чином, функція put може додавати в список новий вузол, зв'язуючи його з вузлом, на який посилається покажчик tail, а потім обновляючи покажчик tail так, щоб він указував уже на новий вузол. Оскільки нові вузли завжди вставляються в кінець списку, конструктор вузлів може встановлювати в null поле покажчика кожного нового вузла й одержувати тільки один аргумент.

template <class Item>

class QUEUE {

private:

struct node

{ Item item; node* next;

node (Item x)

{

item = x; next = 0;

}

};

typedef node *link;

link head, tail;

public:

QUEUE(int)

{ head = 0; }

int empty () const

{ return head ==0; }

void put (Item x)

{ link t = tail;

tail = new node(x);

if (head == 0)

head = tail;

else t->next = tail;

}

Item get()

{Item v = head->item;

link t = head->next;

delete head; head = t; return v;

}

};

Перетворення з інфіксної форми в постфіксну

Ця програма є ще одним прикладом програми-клієнта для стека магазинного типу. У даному випадку стік містить символи. Для перетворення (А+В) у постфиксну форму АВ+ ліва дужка ігнорується, у вихідний потік записується А, у стеці запам'ятовується знак +, у вихідний потік записується В і потім при зустрічі правої дужки зі стека витягається знак + і він же записується у вихідний потік.

#include <iostream.h>

#include <string.h>

#include "STACK.cxx"

int main(int argc, char *argv[])

{char *a = argv[l] ; int N = strlen(a);

STACK<char> ops(N);

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

{

if (a[i] == ')')

cout << ops.pop () << " " ;

if ((a[i] == ' + ') || <a[i] = '*'))

ops.push(a[i]);

if <(a[i] >= '0') && (a[i] <= '9'))

cout << a[i] << " ";

}

cout << endl;

}

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]