Главная » Java, Структуры данных и алгоритмы » Реализация стека с помощью массива

0

В этом параграфе рассмотрим реализацию стека путем хранения его элементов в виде массива. Так как длина массива должна быть задана при его создании, то одним из важных аспектов приводимой реализации стека является необходимость указания некоторого максимального размера N стека, например, N= 1000 элементов. Таким образом, полученный стек состоит из массива S, содержащего 7Vэлементов, плюс целочисленная переменная /, которая обозначает индекс последнего элемента массива S

Поскольку индекс массива в Java начинается с 0, переменной t первоначально присваивается значение, равное —1, которое показывает, что стек пуст. Эта же переменная может использоваться для определения числа элементов в стеке (t + 1). На данном этапе устанавливается новый тип исключения, а именно StackFullException, который означает ошибку, возникающую при попытке добавить новый элемент при полном заполнении массива S. Исключение StackFullException может проявиться только при данной реализации стека и не описано в АТД «стек». С учетом указанного исключения реализация методов АТД может быть проведена, как показано во фрагменте кода 4.3.

Algorithm size():                                                                                                    ,

return t +1 -

Algorithm isEmpty(): return (t < 0)

Algorithm top(): if isEmpty() then

вызов StackEmptyException return S[t] }

Algorithm push(o): if size() = N then

вызов StackFullException t <- t + 1 S[f\ о

Algorithm pop(): if isEmpty() then

вызов StackEmptyException’ e <- S[t] S[t] null t t – 1 return e

Фрагмент кода 4.3. Реализация стека с помощью массива

Правильность приведенной реализации следует из самого определения методов. Тем не менее особого внимания в ней заслуживает реализация метода pop. Обратите внимание, что можно повторно не присваивать null предыдущему S [t ], и тем не менее метод будет выполняться правильно. Однако такая возможность содержит как преимущества, так и недостатки. Это определяется существованием в Java механизма сбора мусора, который осуществляет поиск объектов, уже не вызываемых активными объектами, и освобождает занимаемое ими место для дальнейшего использования. Пусть е = S[t] является последним элементом перед обращением к методу pop. Присваивая S [t ] значение null, определяем, что в стеке больше не нужна ссылка на объект е. Действительно, если активных обращений к е нет, то пространство памяти, занимаемое е, будет очищено сборщиком мусора. Полная реализация Java представленного выше псевдокода в виде Java-ioiacca ArrayStack, реализующего интерфейс Stack, представлена фрагментами кода 4.4 и 4.5.

г

*               Реализация интерфейса Stack с использованием массива

*               определенной длины.

*               Генерирование исключения происходит при попытке вызова метода push

*               в случае равенства размера стека длине массива.

*               

*               автор Наташа Гелфанд

*               автор Роберто Тамассия

*               см. StackFullException 7

public class ArrayStack implements Stack {

*                     длина по умолчанию массива, используемого для реализации стека. 7

public static final int CAPACITY = 1000; !**

*                     длина массива, используемого для реализации стека. 7

private int capacity; Г

*                     массив, используемый для реализации стека. 7

private Object S[]; Г*

*       индекс последнего элемента стека в массиве.

7

private int top = -1;

*       первоначальное присвоение стеку длины массива по умолчанию

*       (CAPACITY).

7

public ArrayStack() { this(CAPACITY);

}

Г

*       первоначальное присвоение стеку массива определенной длины.

*        

* параметр cap длина массива. */

public ArrayStack(int cap) { capacity = cap; S = new Object[capacity];

}

Фрагмент кода} 4.4. Реализация интерфейса Stack на основе массива (см. продолжение во фрагменте кода 4.5)

*       время 0(1).

7

public int size() { return (top + 1);

} !**

*                            время 0(1). 7

public boolean isEmpty() { return (top < 0);

}

Г

*       время 0(1).

*                            исключение StackFullException, если массив уже заполнен. 7

public void push(Object obj) throws StackFullException { if (size() == capacity)

throw new StackFullExceptionfStack overflow."); S[++top] = obj;

} !**

*                            время 0(1). 7

public Object top() throws StackEmptyException { if (isEmptyO)

throW new StackEmptyExceptionfStack is empty.");

return S[top]; }

*       время 0(1).

7

public Object pop() throws StackEmptyException { Object elem; if (isEmptyO)

throw new StackEmptyExceptionfStack is Empty."); elem = S[top];

S[top—] = null; // отправляет S[top] для утилизации сборщиком мусора, return elem;

} }

Фрагмент кода 4.5. Реализация интерфейса Stack на основе массива (продолжение фрагмента кода 4.4). Обратите внимание, что комментарии Javadoc для методов интерфейса Stack содержат только специфичную для класса информацию (например, время выполнения метода), которая не была указана во фрагменте кода 4.1

6 Зак 2456

В табл. 4.1 представлено время выполнения методов при реализации стека с помощью массива. Каждый из методов стека, реализованного на основе массива, выполняет определенное число операций, в том числе арифметические операции, операции сравнения и операции присваивания. Таким образом, при данной5 реализации АТД «стек» время выполнения каждого метода постоянно и равно 0(1).

Метод

Время

size

0(1)

isEmpty

0(1)

top

0(1)

push

0(1)

pop

0(1)

Таблица 4.1. Выполнение стека, реализованного на основе массива. Размер используемого пространства составляет 0(N), где N— длина массива, определенная на этапе описания массива. Обратите внимание, что размер используемого пространства не зависит от числа п < N элементов, содержащихся в стеке

Реализация стека на основе массива является достаточно простой и удобной, благодаря чему широко используется в многочисленных приложениях. Тем не менее подобная реализация обладает некоторыми недостатками, один из которых —• необходимость указания верхнего предела N размера стека. Во фрагменте кода произвольно определен размер стека N= 1000. В действительности для выполнения приложения может потребоваться гораздо меньше места, то есть зря будет занята некоторая часть памяти. С другой стороны, для приложения может потребоваться больше места, ч$м было указано, в этом случае реализация стека приведет к ошибке в приложении при попытке добавить в стек элемент А^ + 1. В силу сказанного, несмотря на всю простоту и эффективность, реализацию стека на основе массива нельзя считать идеальной. Существуют и другие способы реализации, рассмотренные ниже, при которых нет необходимости устанавливать предельный размер — используемое пространство пропорционально действительному числу элементов, содержащихся в стеке. Однако в случаях, когда можно точно определить число элементов стека, оптимальным является все же реализация стека на основе массива. Стеки являются ключевыми составляющими многих приложений, таким образом, зачастую весьма удобно использовать простую и быструю реализацию данного АТД, например, на основе массива.

Приведение типа внутри общего стека

Одно из преимуществ указанной реализации стеков с помощью Java-KJiacca, реализующего интерфейс Stack, состоит в возможности хранения в стеке общих объектов, принадлежащих произвольному классу

(см. фрагменты кодов.4Л, 4.4 и 4.5).-р, частности, ArrayStack может содержать объекты класса Integer, класса. Student или даже объекты класса Planet.

Тем не менее следует обращать внимание на способ применения общих стеков, так,как содержащиеся в них элементы будут рассматриваться как экземпляр Java-KJiacca Object. Это не вызывает никаких сложностей при добавлении элементов в стек, так как любой класс в Java является наследником класса Object. В то же время при попытке извлечь элемент из стека (с помощью метода pop или метода top) всегда осуществляется ссылка типа Object, независимо от класса, к которому в действительности принадлежит объект. В силу этого, чтобы извлечь элемент, являющийся экземпляром определенного класса, необходимо выполнить приведение типов, при котором объект рассматривается как член определенного класса-наследника, а не общего суперкласса Object. (Приведение типов в языке Java подробно рассмотрено в разделе 2.5.)

На примере фрагмента кода 4.6 демонстрируется необходимость приведения типа внутри простого приложения, использующего стек.

public static lnteger[ ] reverse(lnteger[ ] a) { ArrayStack S = new ArrayStack(a.length); lnteger[ ] b = new Integerfe.length]; for (int i=0; i < a.length; i++)

S.push(a[i]); for (int i=0; i < a.length; i++)

b[i] = (Integer) (S.popO); return b;

}

Фрагмент кода 4.6. Представленный метод располагает элементы массива в обратном порядке, используя вспомогательный ArrayStack. Приведение типа необходимо для обеспечения типа Integer возвращаемому методом pop объекту. Обратите внимание; в Java массивы Имеют поле length, в котором записывается размер массива

Метод reverse, представленный фрагментом кода 4.6, представляет небольшое приложение со стековой структурой данных. Эта структура может быть использована и в более сложных приложениях. В сущности, стековая структура данных является важным элементом реализации самого языка Java.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии