3-й семестр / Лекции / 6 - Презентация 2 - Дженерики, Абстрактные типы данных, Стек

Центр дистанционного обучения

Абстрактные типы данных (ADT)

Другая реализация стека на основе односвязного списка:

вершина стека

online.mirea.ru

Центр дистанционного обучения

Стек на основе связанного списка

•Мы можем реализовать стек в виде односвязного списка

•Верхний элемент (верхушка стека) хранится в первом узле списка

•Используемое пространство - O(n) и каждая операция стека

над ATД занимает время O(1)

nodes

t

Центр дистанционного обучения

Абстрактные типы данных (ADT)

class Node<E> {

final Node<E> prev; final E value;

Node(Node<E> prev, E value) { this.prev = prev;

this.value = value;

}

}

online.mirea.ru

Центр дистанционного обучения

Абстрактные типы данных (ADT)

public class LinkedStack<E> implements MyStack<E> { private Node<E> top = null;

private int size = 0;

public void push(E element) {

top = new Node<>(top, element); size++;

}

public E pop() {

if (isEmpty()) throw new IllegalStateException("Stack is empty: cannot pop"); E result = top.value;

top = top.prev; size--;

return result;

}

public E peek() {

if (isEmpty()) throw new IllegalStateException("Stack is empty: cannot peek"); return top.value;

}

public int size() { return size;

}

public boolean isEmpty() { return top == null;

}

}

online.mirea.ru