Очереди

Стеки

Лекция 8. Динамические структуры данных. Стеки, очереди, деревья

Стек — это частный случай однонаправленного списка, добавление элементов в который и выборка из которого выполняются с одного конца, называемого вершиной стека. Другие операции со стеком не определены. При выборке элемент исключается из стека. Говорят, что стек реализует принцип обслуживания LIFO (last in — first out, последним пришел — первым ушел). Стек проще всего представить себе как закрытую с одного конца узкую трубу, в которую бросают мячи. Достать первый брошенный мяч можно только после того, как вынуты все остальные. Стеки широко применяются в системном программном обеспечении, компиляторах, в различных рекурсивных алгоритмах.

Ниже приведена программа, которая формирует стек из пяти целых чисел (1,2,3,4,5) и выводит его на экран. Функция помещения в стек по традиции называется push, а выборки – pop. Указатель для работы со стеком (top) всегда ссылается на его вершину.

#include <iostream.h>

struct Node{

int d;

Node *p;

};

Node * first(int d);

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

int 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->p = 0;

return pv;

}

//-------------------------------------

// Занесение в стек

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

Node *pv = new Node;

pv->d = d;

pv->p = *top;

*top = pv;

}

//-------------------------------------

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

int pop (Node *tор){

int temp = (*top)->d;

Node *pv = tор;

tор = (*top)->p;

delete pv;

return temp;

}

Результат работы программы:

5 4 3 2 1

Очередь — это частный случай однонаправленного списка, добавление элементов в который выполняется в один конец, а выборка — из другого конца. Другие операции с очередью не определены. При выборке элемент исключается из очереди. Говорят, что очередь реализует принцип обслуживания FIFO (first in — first out, первым пришел — первым ушел). Очередь проще всего представить себе, постояв в ней час-другой. В программировании очереди применяются, например при моделировании, диспетчеризации задач операционной системой, буферизованном вводе/выводе.

Ниже приведена программа, которая формирует очередь из пяти целых чисел и выводит ее на экран. Функция помещения в конец очереди называется add, а выборки — del. Указатель на начало очереди называется pbeg, указатель на конец — pend.

#include <iostream.h>

struct Node{

int d;

Node *p;

};

Node * first(int d);

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

int del(Node **pbeg);

// ---------------------------------------

int main(){

Node *pbeg = first(1);

Node *pend = pbeg;