Data Structure Specification
Uploaded by
NắngChoMànĐêmData Structure Specification
Uploaded by
NắngChoMànĐêmPresentation: Design Specification for Data Structures
Objective
This presentation explains how to create a design specification for data
structures by describing the valid operations on: - A Stack ADT - A concrete
FIFO Queue - Two Sorting Algorithms - Two Network Shortest Path Algorithms
1. Stack ADT (LIFO)
Definition:
A stack is a Last In First Out (LIFO) data structure where elements are added
and removed from the top.
Specification Table:
Paramet Return
Operation Description ers Type
push(item Adds an item to the top item: T void
)
pop() Removes and returns the top item None T
peek() Returns top item without removing None T
isEmpty() Checks if the stack is empty None boolean
size() Returns number of items in the stack None int
Implementation (Without using built-in Stack):
public class MyStack<T> {
private List<T> elements;
public MyStack() {
elements = new ArrayList<>();
}
public void push(T item) {
elements.add(item);
}
public T pop() {
if (isEmpty()) throw new EmptyStackException();
return elements.remove(elements.size() - 1);
}
public T peek() {
if (isEmpty()) throw new EmptyStackException();
return elements.get(elements.size() - 1);
}
public boolean isEmpty() {
return elements.isEmpty();
}
public int size() {
return elements.size();
}
}
Example Usage:
MyStack<Integer> stack = new MyStack<>();
stack.push(10);
stack.push(20);
System.out.println(stack.pop()); // Output: 20
System.out.println(stack.peek()); // Output: 10
System.out.println(stack.isEmpty()); // Output: false
System.out.println(stack.size()); // Output: 1
2. FIFO Queue (Concrete Data Structure)
Definition:
A queue is a First In First Out (FIFO) structure where elements are added at
the rear and removed from the front.
Specification Table:
Paramet Return
Operation Description ers Type
enqueue(it Adds an item to the rear of the queue item: T void
em)
dequeue() Removes and returns the front item None T
peek() Returns front item without removing None T
isEmpty() Checks if the queue is empty None boolean
size() Returns number of items in the queue None int
Implementation (Without using built-in Queue):
public class MyQueue<T> {
private List<T> elements;
public MyQueue() {
elements = new ArrayList<>();
}
public void enqueue(T item) {
elements.add(item);
}
public T dequeue() {
if (isEmpty()) throw new NoSuchElementException();
return elements.remove(0);
}
public T peek() {
if (isEmpty()) throw new NoSuchElementException();
return elements.get(0);
}
public boolean isEmpty() {
return elements.isEmpty();
}
public int size() {
return elements.size();
}
}
Example Usage:
MyQueue<String> queue = new MyQueue<>();
queue.enqueue("A");
queue.enqueue("B");
System.out.println(queue.dequeue()); // Output: A
System.out.println(queue.peek()); // Output: B
System.out.println(queue.isEmpty()); // Output: false
System.out.println(queue.size()); // Output: 1
3. Two Sorting Algorithms
1. Bubble Sort
Simple, iterative algorithm.
Time complexity: O(n^2)
void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
Example:
int[] arr = {5, 3, 8, 4};
bubbleSort(arr);
System.out.println(Arrays.toString(arr)); // [3, 4, 5, 8]
2. Merge Sort
Divide and conquer method.
Time complexity: O(n log n)
void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; ++i)
L[i] = arr[left + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
Example:
int[] arr = {9, 2, 7, 1};
mergeSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr)); // [1, 2, 7, 9]
4. Two Shortest Path Algorithms
1. Dijkstra’s Algorithm (With Implementation)
class Edge {
int to, weight;
public Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
int[] dijkstra(List<List<Edge>> graph, int start) {
int n = graph.size();
int[] dist = new int[n];
boolean[] visited = new boolean[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
PriorityQueue<int[]> pq = new
PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.offer(new int[]{start, 0});
while (!pq.isEmpty()) {
int[] current = pq.poll();
int u = current[0];
if (visited[u]) continue;
visited[u] = true;
for (Edge edge : graph.get(u)) {
int v = edge.to;
int weight = edge.weight;
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.offer(new int[]{v, dist[v]});
}
}
}
return dist;
}
Example:
List<List<Edge>> graph = new ArrayList<>();
for (int i = 0; i < 3; i++) graph.add(new ArrayList<>());
graph.get(0).add(new Edge(1, 4));
graph.get(0).add(new Edge(2, 1));
graph.get(2).add(new Edge(1, 2));
int[] distances = dijkstra(graph, 0);
System.out.println(Arrays.toString(distances)); // [0, 3, 1]
2. Bellman-Ford Algorithm (With Implementation)
class EdgeBF {
int src, dest, weight;
public EdgeBF(int s, int d, int w) {
src = s; dest = d; weight = w;
}
}
int[] bellmanFord(List<EdgeBF> edges, int V, int start) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
for (int i = 1; i < V; i++) {
for (EdgeBF e : edges) {
if (dist[e.src] != Integer.MAX_VALUE && dist[e.src] +
e.weight < dist[e.dest]) {
dist[e.dest] = dist[e.src] + e.weight;
}
}
}
for (EdgeBF e : edges) {
if (dist[e.src] != Integer.MAX_VALUE && dist[e.src] + e.weight
< dist[e.dest]) {
throw new RuntimeException("Graph contains a negative
weight cycle");
}
}
return dist;
}
Example:
List<EdgeBF> edges = Arrays.asList(
new EdgeBF(0, 1, 4),
new EdgeBF(0, 2, 1),
new EdgeBF(2, 1, 2)
);
int[] result = bellmanFord(edges, 3, 0);
System.out.println(Arrays.toString(result)); // [0, 3, 1]
Summary
Stack and Queue ADTs should clearly define operations with
parameters and return types.
Use examples and code snippets for clarity.
Sorting and pathfinding algorithms should include use cases and
performance.
Recommendation for Presentation Slides
Use tables to describe operations
Include diagrams for stack and queue
Add code and real-life examples