Глава 11. Структуры данных

Стек

Со стеком определены только операции добавления и выборки элементов из вершины стека. При осуществлении выборки элемент исключается из стека. В стеке осуществляется принцип LIFO. Возможен также принцип FIFO. Стеки широко применяются в системном программировании при написании компиляторов и различных рекурсивных алгоритмов.

Пример 1

Пример программы, которая формирует стек из пяти целых чисел, и выводит его на экран:

#include <iostream>

Struct Node

{

int d;

Node *p;

}

Node *first(int d);

void push(Node **top, int d);

void pop(Node **top);

Int main()

{

Node *top = first(1);

for(int i=2; i<6; i++) push(&top, i);

While(top)

cout<<pop(&top)<<" ";

return 0;

}

/* начальное формирование стека */

Node *first (int d)

{

Node *Pv = new Node;

Pv->d=d;

Pv->d=0;

return Pv;

}

/* занесение в стек */

void push(Node **top, int d)

{

Node *Pv = new Node;

Pv -> d = d;

Pv -> p = *top;

*top = Pv;

}

/* выборка из стека */

int pop(Node **top)

{

int temp = (*top) -> d;

Node *Pv = *top;

*top = (*top) -> p;

delete Pv;

return temp;

}

/* вывод: 5 4 3 2 1 */

Очереди

Очередь – абстрактная структура данных, реализует принцип обслуживания FIFO. Это частный случай однонаправленного списка, добавление элементов в который выполняется в один конец, а выборка идет из другого конца. Таким образом, в структуре «очередь» определены две операции: добавление элементов и выборка. При выборке элемент из очереди исключается. В системном программировании очереди используются для диспетчеризации задач моделирования.

Пример 1

Пример программы, реализующей линейную очередь из пяти элементов, выводя их на экран

Struct Node

{

int d;

Node *p;

}

Node *first(int d);

void add(Node **pend, int d);

int del(Node **pbeg);

Int main()

{