Стеки и Очереди

1. Стеки и Очереди

2. Стек

СТЕК - ТАКОЙ ПОСЛЕДОВАТЕЛЬНЫЙ СПИСОК С ПЕРЕМЕННОЙ
ДЛИНОЙ, ВКЛЮЧЕНИЕ И ИСКЛЮЧЕНИЕ ЭЛЕМЕНТОВ ИЗ
КОТОРОГО ВЫПОЛНЯЮТСЯ ТОЛЬКО С ОДНОЙ СТОРОНЫ
СПИСКА, НАЗЫВАЕМОГО ВЕРШИНОЙ СТЕКА. ПРИМЕНЯЮТСЯ
И ДРУГИЕ НАЗВАНИЯ СТЕКА - МАГАЗИН И ОЧЕРЕДЬ,
ФУНКЦИОНИРУЮЩАЯ ПО ПРИНЦИПУ LIFO (LAST - IN - FIRSTOUT - "ПОСЛЕДНИМ ПРИШЕЛ - ПЕРВЫМ ИСКЛЮЧАЕТСЯ").
ПРИМЕРЫ СТЕКА: ВИНТОВОЧНЫЙ ПАТРОННЫЙ МАГАЗИН,
ТУПИКОВЫЙ ЖЕЛЕЗНОДОРОЖНЫЙ РАЗЪЕЗД ДЛЯ СОРТИРОВКИ
ВАГОНОВ.

3.

ОСНОВНЫЕ ОПЕРАЦИИ НАД СТЕКОМ - ВКЛЮЧЕНИЕ
НОВОГО ЭЛЕМЕНТА (АНГЛИЙСКОЕ НАЗВАНИЕ PUSH ЗАТАЛКИВАТЬ) И ИСКЛЮЧЕНИЕ ЭЛЕМЕНТА ИЗ СТЕКА
(АНГЛ. POP - ВЫСКАКИВАТЬ).
ПОЛЕЗНЫМИ МОГУТ БЫТЬ ТАКЖЕ ВСПОМОГАТЕЛЬНЫЕ
ОПЕРАЦИИ:
ОПРЕДЕЛЕНИЕ ТЕКУЩЕГО ЧИСЛА ЭЛЕМЕНТОВ В
СТЕКЕ;
ОЧИСТКА СТЕКА;
НЕРАЗРУШАЮЩЕЕ ЧТЕНИЕ ЭЛЕМЕНТА ИЗ ВЕРШИНЫ
СТЕКА, КОТОРОЕ МОЖЕТ БЫТЬ РЕАЛИЗОВАНО, КАК
КОМБИНАЦИЯ ОСНОВНЫХ ОПЕРАЦИЙ :
X:=POP(STACK);
PUSH(STACK,X);

4.

Рассмотрим небольшой пример, демонстрирующий принцип включения элементов
в стек и исключения элементов из стека. На рис. 1 (а,б,с) изображены состояния
стека:
а). пустого;
б-г). после последовательного включения в него элементов с именами 'A', 'B', 'C';
д, е). после последовательного удаления из стека элементов 'C' и 'B';
ж). после включения в стек элемента 'D'.
Рисунок 1-Работа со стеком

5.

КА К ВИ Д Н О И З Р И С 1 , СТ Е К МОЖ Н О П Р Е Д СТА ВИ ТЬ , Н А П Р И МЕ Р,
В ВИ Д Е СТО П КИ КН И Г ( ЭЛЕМЕН ТОВ), ЛЕЖ А ЩЕЙ Н А СТОЛЕ.
П Р И СВО И М КА Ж Д О Й КН И Г Е СВО Е Н АЗ ВА НИ Е , Н А П Р И МЕ Р
A , B, C, D . ..
ТО ГД А В МО МЕ Н Т В Р Е МЕ Н И , КО ГД А Н А С ТОЛ Е К Н И Г Н Е Т, П Р О
СТ Е К А Н А ЛО Г И ЧН О МОЖ Н О СКАЗ АТ Ь , Ч ТО О Н П УСТ, Т. Е . Н Е
СОД Е РЖИ Т Н И ОД Н О ГО ЭЛЕ МЕ Н ТА .
Е СЛИ Ж Е МЫ Н АЧ Н Е М П О СЛЕ Д О ВАТ ЕЛЬ НО КЛАСТ Ь КН И Г И ОД НУ
Н А Д РУГ УЮ, ТО П ОЛУЧ ИМ СТО П КУ КН И Г ( ДО П УСТИМ, И З N
КН И Г ) , И ЛИ П ОЛУЧ И М СТ Е К, В КО ТО Р О М СОД Е РЖИ ТСЯ N
ЭЛЕ МЕ Н ТО В, П Р И Ч Е М ВЕ Р ШИ Н О Й Е ГО БУД Е Т ЯВЛЯТ ЬСЯ
ЭЛЕ МЕ Н Т N +1 .
УД А ЛЕ Н И Е ЭЛЕ МЕ Н ТО В И З СТ Е КА О СУЩЕ СТ ВЛЯЕ Т СЯ
А Н А ЛО Г И ЧН ЫМ О Б РАЗ ОМ Т. Е . УД А ЛЯЕ Т СЯ П О СЛЕ Д О ВАТ ЕЛЬ НО
П О ОД Н О МУ ЭЛЕ МЕ Н Т У, Н АЧ И Н АЯ С ВЕ Р ШИ Н Ы , И ЛИ П О ОД Н О Й
КН И Г Е И З СТО П КИ .

6. Создание стека

typedef struct node{
char val; //значение эл-та стека
struct node *next;// указатель на след. узел
}NODE, *pNODE;
typedef struct stack{ // создание структуры стек
pNODE top;
int len;
}STACK, *pSTACK;

7. Функция создания нового стека

pSTACK CreateStack()
{
pSTACK pS;
pS = (pSTACK)malloc(sizeof(STACK));
pS->top = NULL;
pS->len = 0;
return pS;
}

8. Функция проверки наполненности стека

int isEmpty(pSTACK pS)
{
if (pS->top&&pS->len) return 0;
return 1;
}

9. Функция добавления элемента в стек

int push(pSTACK pS, char value){
pNODE p = (pNODE)malloc(sizeof(NODE));
if(p){
p->val = value;
p->next = pS->top;
pS->top = p;
pS->len++;
return 1;
}
return 0;
}

10. Функция извлечения элемента из стека

CHAR pop(pSTACK pS)
{
pNODE p = pS->top;
char c = p->val;
pS->top = p->next;
free(p);
pS->len--;
return c;
}

11. Функция вывода линейного списка (стека) на экран

void show(pSTACK pS)
{
pNODE p = pS->top;
if (isEmpty(pS)) puts(“Stack empty");
else
while (p)
{
printf("%c ", p->val);
p = p->next;
}
}

12. Функция очистки стека

void clearStack(pSTACK pS)
{
pNODE p = pS->top;
while (!isEmpty(pS)) pop(pS);
}

13. Тело программы

int _tmain()
{
pSTACK ps = CreateStack();
char c;
for (c='a'; c<='z'; c++)
push(ps, c);
while(!isEmpty(ps))
{
show(ps);
pop(ps);
printf_s("\n");
}
show(ps);
_getch();
return 0;
}

14. Очередь

ОЧЕРЕДЬ
Очередь – это линейный список, доступ к элементам которого
происходит по принципу F I F O (First In and First Out – первым
пришел и первым ушел).
Для очереди характерны две операции – занесение элемента в очередь
и извлечение (считывание) элемента из очереди. В простой очереди
для работы с данными доступны две позиции – начало (из этой
позиции происходит извлечение) и конец (в эту позицию заносится
входящий элемент) или "голова" и "хвост". Произвольный доступ к
элементам, в отличии от массивов, формально не допускается.
Операция извлечения (считывания) формально является
разрушающей. Это означает, что считанные данные становятся
недоступными. Возможно, явного разрушения (уничтожения) данных
и не происходит, но к ним нет доступа, используя стандартные
операции работы с очередью.

15.

ОБЛАСТИ ПРИМЕНЕНИЯ ОЧЕРЕДЕЙ МОГУТ БЫТЬ РАЗДЕЛЕНЫ
НА ДВЕ ГРУППЫ – СИСТЕМНОЕ ПРИМЕНЕНИЕ И ПРИКЛАДНОЕ.
К ПРИМЕНЕНИЮ ОЧЕРЕДЕЙ В СИСТЕМНЫХ ЦЕЛЯХ
ОТНОСЯТСЯ:
ДИСПЕТЧЕРИЗАЦИЯ ЗАДАЧ ОПЕРАЦИОННОЙ СИСТЕМОЙ;
БУФЕРИЗАЦИЯ ВВОДА/ВЫВОДА ;
ПРИКЛАДНОЕ ПРИМЕНЕНИЕ:
МОДЕЛИРОВАНИЕ ПРОЦЕССОВ (НАПРИМЕР, СИСТЕМ
МАССОВОГО ОБСЛУЖИВАНИЯ);
ИСПОЛЬЗОВАНИЕ ОЧЕРЕДЕЙ КАК ВСПОМОГАТЕЛЬНЫХ
СТРУКТУР ДАННЫХ В КАКИХ-ЛИБО АЛГОРИТМАХ
(НАПРИМЕР, ПРИ ПОИСКЕ В ГРАФАХ).

16. Реализация очереди

typedef struct node
{
int val;
// значение эл-та стека
struct node *next; // указатель на сл. узел
}*pNODE, NODE;
typedef struct queue // Создание структуры очередь
{
NODE *beg, *end;
int len;
}QUEUE, *pQUEUE;

17. Функция создания очереди

pQUEUE create()
{
pQUEUE pQ;
pQ=(pQUEUE)malloc(sizeof(QUEUE));
pQ->beg=pQ->end=NULL;
pQ->len=0;
return pQ;
}

18. Функция проверка очереди на пустоту

int isEmpty(pQUEUE pQ)
{
if (pQ->beg&& pQ->end) return 0;
return 1;
}

19. Функция добавления элемента

void put(pQUEUE pQ, int value)
{ pNODE p;
p=(pNODE)malloc(sizeof(NODE));
p->next=NULL;
p->val=value;
if (pQ->end) pQ->end->next=p;
else pQ->beg=p;
pQ->end=p;
pQ->len++;
}

20. Функция вывода очереди на экран

void show(pQUEUE pQ){
pNODE p=pQ->beg;
if (isEmpty(pQ)) printf (“Queue empty");
while(p){
printf("%d ", p->val);
p=p->next;
}
printf("\n");
}

21. Функция изъятия элемента из очереди

int take(pQUEUE pQ)
{
pNODE p=pQ->beg;
int c=p->val;
pQ->beg=p->next;
free(p);
pQ->len--;
return c;
}

22. Функция очистки очереди

void ClearQueue(pQUEUE pQ){
pNODE p=pQ->beg;
while(p) take(pQ);
free (pQ);
}

23. Тело программы

int _tmain(int argc, _TCHAR* argv[])
{ pQUEUE pQ=createQueue();
char c;
for(c='0'; c<'9'; c++) put(pQ, c);
showQ(pQ);
ClearQueue(pQ);
pQ=createQueue();
for(c='0'; c<'9'; c++) put(pQ, c);
while (!isEmptyQueue(pQ)){
take(pQ);
showQ(pQ);
}
ClearQueue(pQ);
return 0;
}