Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
PAGE 2
Лекция 14
4.9.3.2. Стеки
Стек – это некоторый вариант однонаправленного списка, в котором добавление и выборка элементов выполняются с одного конца, называемого вер шиной стека. Другие операции со стеком не определены. При выборке элемент исключается из стека. Говорят, что стек реализует принцип обслуживания LIFO (last – in, first – out). Стек можно проиллюстрировать вертикальной стопкой тарелок, если они складываются и извлекаются по одной сверху.
Стеки широко применяют ся в системном программном обеспечении, компиляторах, в различных рекур сивных алгоритмах.
Ниже приведена программа, которая формирует стек из пяти целых чисел (1, 2, 3, 4, 5) и выводит его на экран. Функция помещения в стек по традиции называ ется push, функция выборки – pop. Указатель для работы со стеком (top) всегда ссылает ся на его вершину.
#include <iostream.h>
struct Node
{
int d:
Node *p;
};
// Объявления функций
Node *first (const int d);
void push (Node **top, const int d);
int pop (Node **top);
const int N = 5;
int main ()
{
Node *top = first (l);
for (int i = 2; i <= N; i++) push (&top, i);
while (top) cout << pop (&top) << ' ';
return 0;
}
Результат работы программы: 5 4 3 2 1.
/*** Определения функций ***/
// Начальное формирование стека
Node *first (const int d)
{
Node *pv = new Node;
pv->d = d; pv->p = 0;
return pv;
}
// Запись в стек
void push (Node **top, const 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;
}
4.9.3.3. Очереди
Очередь – вариант однонаправленного списка, добавление элементов в который производится с одного конца, а выборка – с другого конца. Другие опе рации с очередью не определены. При выборке элемент исключается из очереди. Говорят, что очередь реализует принцип обслуживания FIFO (first – in, first – out). Эту структуру данных можно сравнить с очередью в магазине. В программировании очереди применяются в мо делировании, диспетчеризации задач операционной системой, буферизованном вводе/выводе и т.д.
Ниже приведена программа, которая формирует очередь из пяти целых чисел и выводит ее на экран. Функция записи в очередь называется add, вы борки – del. Указатель начала очереди называется pbeg, указатель конца – pend.
#include <iostream.h>
struct Node
{
int d;
Node *p;
};
// Объявления функций
Node *first (const int d);
void add (Node **pend, const int d);
int del (Node **pbeg);
const int N = 5;
int main ()
{
Node *pbeg = first (l);
Node *pend = pbeg;
for (int i = 2; i <= N; i++) add (&pend, i);
while (pbeg) cout << del (&pbeg) << ' ';
return 0:
}
Результат работы программы: 1 2 3 4 5.
/*** Определения функций ***/
// Начальное формирование очереди
Node *first (const int d)
{
Node *pv = new Node;
pv->d = d; pv->p = 0;
return pv;
}
// Запись в очередь
void add (Node **pend, const int d)
{
Node *pv = new Node:
pv->d = d; pv->p = 0;
(*pend)->p = pv; *pend = pv;
}
// Выборка из очереди
int del (Node **pbeg)
{
int temp = (*pbeg)->d;
Node *pv = *pbeg;
*pbeg = (*pbeg)->p;
delete pv;
return temp;
}