Стек - це кінцева послідовність деяких однотипних елементів - скалярних перемінних, масивів, структур або об'єднань, серед яких можуть бути й однакові. Стік позначається у виді: S= і представляє динамічну структуру даних; її кількість елементів заздалегідь не вказується й у процесі роботи, як правило змінюється. Якщо в стеці елементів ні, то він називається порожнім і позначається S=<>.
Припустимими операціями над стеком є:
- перевірка стека на порожнечу S=<>,
- додавання нового елемента Sn+1 у кінець стека - перетворення < S1,...,Sn> у < S1,...,Sn+1>;
- вилучення останнього елемента зі стека - перетворення < S1,...,Sn-1,Sn> у < S1,...,Sn-1>;
- доступ до його останнього елемента Sn, якщо стік не порожній.
Таким чином, операції додавання і видалення елемента, а також доступу до елемента виконуються тільки наприкінці списку. Стік можна представити як стопку книг на столі, де додавання або узяття нової книги можливо тільки зверху.
Черга - це лінійний список, де елементи віддаляються з початку списку, а додаються наприкінці списку (як звичайна черга в магазині).
Двостороння черга - це лінійний список, у якого операції додавання і видалення елементів і доступу до елементів можливі як спочатку так і наприкінці списку. Таку чергу можна представити як послідовність книг на полку, так що доступ до них можливий з обох кінців.
Реалізація стеков і черг у програмі може бути виконана у виді послідовного або зв'язаного збереження. Розглянемо приклади організації стека цими способами.
Однієї з форм представлення виражень є польський інверсний запис, що задає вираження так, що операції в ньому записуються в порядку виконання, а операнди знаходяться безпосередньо перед операцією.
Наприклад, вираз
(6+8)*5-6/2у польському інверсному записі має вигляд
6 8 + 5 * 6 2 / -Особливість такого запису полягає в тому, що значення вираження можна обчислити за один перегляд запису ліворуч праворуч, використовуючи стек, що до цього повинний бути порожній. Кожне нове число заноситься в стек, а операції виконуються над верхніми елементами стека, заміняючи ці елементи результатом операції. Для приведеного вираження динаміка зміни стека буде мати вигляд
S = <>; <6>; <6,8>; <14>; <14,5>; <70>;<70,6>; <70,6,2>; <70,3>; <67>.Нижче приведена функція eval, що обчислює значення вираження, заданого в масиві m у формі польського інверсного запису, причому m[i]>0 означає ненегативне число, а значення m[i]<0 операції. Як кодування операцій додавання, вирахування, множення і розподіли обрані негативні числа 1, 2, 3, 4. Для організації послідовного збереження стека використовується внутрішній масив stack. Параметрами функції є вхідний масив a і його довжина l.
float eval (float *m, int l) { int p,n,i; float stack[50],c;for(i=0; i < l ;i++) if ((n=m[i])<0) { c="st[p--];" switch(n) { case 1: stack[p]+="c;" break; case 2: stack[p]-="c;" break; case 3: stack[p]*="c;" break; case 4: stack[p]/="c;" } } else stack[++p]="n;" return(stack[p]); }Розглянемо іншу задачу. Нехай потрібно ввести деяку послідовність символів, що закінчується крапкою, і надрукувати неї в зворотному порядку (тобто якщо на вході буде "ABcEr-1." те на виході повинне бути "1-rEcBA"). Представлена нижче програма спочатку уводить усі символи послідовності, записуючи них у стек, а потім уміст стека друкується в зворотному порядку. Це основна особливість стека - чим пізніше елемент занесений у стек, тим раніш він буде витягнутий зі стека. Реалізація стека виконана в зв'язаному збереженні за допомогою покажчиків p і q на тип, іменований ім'ям STACK.
#include typedef struct st /* оголошення типу STACK */ { char ch; struct st *ps; } STACK; main() { STACK *p,*q; char a; p=NULL; do /* заповнення стека */ { a=getch(); q=malloc(sizeof(STR1)); q->ps=p; p=q; q->ch=a; } while(a!='.'); do /* печатка стека */ { p=q->ps;free(q);q=p; printf("%c",p->ch); } while(p->ps!=NULL); }При збереженні великих обсягів інформації у формі лінійних списків небажано зберігати елементи з однаковим значенням, тому використовують різні методи стиску списків.
Стиснуте збереження. Нехай у списку B= кілька елементів мають однакове значення V, а список В'= виходить з B заміною кожного елемента Ki на пари Ki'=(і,Ki). Нехай далі B"= - підсписок В', що виходить викреслюванням усіх пар Ki=(і,V). Стиснутим збереженням У є метод збереження В", у якому елементи зі значенням V. Розрізняють послідовне стиснуте збереження і зв'язане стиснуте збереження. Наприклад, для списку B=, що містить кілька вузлів зі значенням Х, послідовного стиснутого і зв'язане стиснуте збереження, з умовчуванням елементів зі значенням Х, представлені на мал.22,23.
Достоїнство стиснутого збереження списку при великому числі елементів зі значенням V полягає в можливості зменшення обсягу пам'яті для його збереження.
Пошук i-го елемента в зв'язаному стиснутому збереженні здійснюється методом повного перегляду, при послідовному збереженні - методом бінарного пошуку.
Переваги і недоліки послідовного стиснутого і зв'язаного стиснутого аналогічні перевагам і недолікам послідовного і зв'язаного збереження.
Розглянемо наступну задачу. На вході задані дві послідовності цілих чисел M=, N=, причому 92% елементів послідовності М дорівнюють нулеві. Скласти програму для обчислення суми добутків Mi * Ni, і=1,2,...,10000.
Припустимо, що список М зберігається послідовно стисло в масиві структур m з оголошенням:
struct { int nm; float val; } m[10000];Для визначення кінця списку додамо ще один елемент із порядковим номером m[j].nm=10001, що називається стопером (stopper) і розташовується за останнім елементом стиснутого збереження списку в масиві m.
Програма для перебування шуканої суми має вигляд:
# include main() { int і,j=0; float inp,sum=0; struct /* оголошення масиву */ { int nm; /* структур */ float val; } m[10000]; for(i=0;i<10000;i++) /* читання списку M */ { scanf("%f",&inp); if (inp!="0)" { m[j].nm="i;" m[j++].val="inp;" } } m[j].nm="10001;" /* stopper */ for(i="0,j=0;" i<10000; i++) { scanf("%f",&inp); /* читання списку N */ if(i="=m[j].nm)" /* обчислення суми */ sum+="m[j++].val*inp;" } printf( "сума добутків Mi*Ni дорівнює %f",sum); }Індексне збереження використовується для зменшення часу пошуку потрібного елемента в списку і полягає в наступному. Вихідний список B = розбивається на трохи підсписків У1,У2, ...,Вм таким чином, що кожен елемент списку В попадає тільки в один з підсписків, і додатково використовується індексний список з М елементами, що вказують на початок списків У1,У2, ...,Ум.
Вважається, що список зберігається індексно за допомогою підсписків B1,B2, ...,Bm і індексного списку X = , де ADGj - адреса початку підсписка Bj, j=1,M.
При індексному збереженні елемент До підсписка Bj має індекс j. Для одержання індексного збереження вихідний список У часто перетвориться в список В' шляхом включення в кожен вузол ще і його порядкового номера у вихідному списку В, а в j-ий елемент індексного списку Х, крім ADGj, може включатися деяка додаткова інформація про підсписок Bj. Розбивка списку В на підсписки здійснюється так, щоб всі елементи В, що володіють визначеною властивістю Рj, попадали в один підсписок Bj.
Достоїнством індексного збереження є те, що для перебування елемента К с заданою властивістю Pj досить переглянути тільки елементи підсписка Bj; його початок знаходиться по індексному списку Х, тому що для кожного ДО, що належить Bi, при і не рівному j властивість Pj не виконується.
У розбивці В часто використовується індексна функція G(K), що обчислює по елементі До його індекс j, тобто G(K)=j. Функція G звичайно залежить від позиції ДО, що позначається поз.K, у підсписку В або від значення визначеної частини компоненти ДО - її ключа.
Розглянемо список B= з елементами
ДО1=(17,Y), K2=(23,H), K3=(60,I), K4=(90,S), K5=(66,T),K6=(77,T), K7=(50,U), K8=(88,W), K9=(30,S).Якщо для розбивки цього списку на підсписки як індексну функцію взяти Ga(K)=1+(поз.K-1)/3, то список розділиться на три підсписка:
B1a=<(17,Y),(23,H),(60,I)>,B2a=<(90,S),(66,T),(77,T)>,B3a=<(50,U),(88,W),(30,S)>.Додаючи усюди ще і початкову позицію елемента в списку, одержуємо:
B1a'=<(1,17,Y),(2,23,H),(3,60,I)>,B2a'=<(4,90,S),(5,66,T),(6,77,T)>,B3а'=<(7,50,U),(8,88,W),(9,30,S)>.Якщо як індексну функцію вибрати іншу функцію Gb(K)=1+(поз.K-1)%3, то одержимо списки:
B1b"=<(1,17,Y),(4,90,S),(7,50,U)>,B2b"=<(2,23,H),(5,66,T),(8,88,U)>,B3b"=<(3,60,I),(6,77,T),(9,30,S)>.Тепер для перебування вузла K6 досить переглянути тільки одну з трьох послідовностей (списків). При використанні функції Ga(K) це список B2а', а при функції Gb(K) список B3b".
Для індексної функції Gc(K)=1+K1/100, де K1 - перший компонент елемента ДО, знаходимо:
B1=<(17,Y),(23,H),(60,I),(90,S)>,B2=<(66,T),(77,T)>,B3=<(50,U),(88,W)>,B4=<(30,S)>.Щоб знайти тут вузол К с першим компонентом-ключем ДО1=77, досить переглянути список B2.
При реалізації індексного збереження застосовується методика А для збереження індексного списку Х (функція Ga(X) ) і методика C для збереження підсписків B1,B2,...,Bm (функція Gc(Bi)), тобто використовується, так називане, A-C індексне збереження.
У практиці часто використовується послідовно-зв'язане індексне збереження. Тому що звичайно довжина списку індексів відома, те його зручно зберігати послідовно, забезпечуючи прямій доступ до будь-якого елемента списку індексів. Підсписки B1,B2,...,Bm зберігаються пов'язано, що спрощує вставку і видалення вузлів(елементів). Зокрема, подібний метод збереження використовується в ЄС ЕОМ для організації, так званих, індексно-послідовних наборів даних, у яких доступ до окремих записів можливий як послідовно, так і за допомогою ключа.
Послідовно-зв‘язане індексне збереження для приведеного приклада зображене на мал.24, де X=.
Розглянемо ще одну задачу. На вході задана послідовність цілих позитивних чисел, що закінчується нулем. Скласти процедуру для введення цієї послідовності й організації її індексного збереження таким чином, щоб числа, що збігаються в двох останніх цифрах, містилися в один підсписок.
Виберемо як індексну функцію G(K)=K%100+1, а як індексний список Х - масив з 100 елементів. Наступна функція вирішує поставлену задачу: