Scribd
Upload
3 views3 pages

Stack

The document presents two implementations of a stack: one using linked lists and the other using arrays, detailing their respective methods for push, pop, and peek operations. It also compares the time complexities of these operations, indicating that both implementations have O(1) complexity for push, pop, and peek. Additionally, it mentions that Java's 'java.util.Stack' is considered legacy and recommends using 'java.util.ArrayDeque' for better performance.

Uploaded by

adistrasser350
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
3 views3 pages

Stack

The document presents two implementations of a stack: one using linked lists and the other using arrays, detailing their respective methods for push, pop, and peek operations. It also compares the time complexities of these operations, indicating that both implementations have O(1) complexity for push, pop, and peek. Additionally, it mentions that Java's 'java.util.Stack' is considered legacy and recommends using 'java.util.ArrayDeque' for better performance.

Uploaded by

adistrasser350
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

3.

Stack
1. Linked List Implementation
The following code demonstrates the implementation using Linked Lists.

public class Node {


private int data;
private Node next;
public int getData() { return data; }
public void setData(int data) { [Link] = data; }
public Node getNext() { return next; }
public void setNext(Node next) { [Link] = next; }
}

public class Stack {


private Node top;
private int size;

public Node getTop() { return top; }


public void setTop(Node top) { [Link] = top; }
public int getSize() { return size; }
public void setSize(int size) { [Link] = size; }

public void push(int data) {


Node newNode = new Node();
[Link](data);
if (top != null) {
[Link](top);
}
top = newNode;
size++;
}

public Node pop() {


if (top == null) return null;
Node temp = top;
top = [Link]();
[Link](null);
size--;
return temp;
}

public Node peek() { return top; }


public boolean isEmpty() { return size == 0; }
}
2. Array Implementation
The following code demonstrates the implementation using Arrays.

public class ArrayStack {


private int[] data;
private int top;
private static final int DEFAULT_CAPACITY = 10;

public ArrayStack() {
data = new int[DEFAULT_CAPACITY];
top = -1;
}

private void ensureCapacity() {


if (top == [Link] - 1) {
int[] newData = new int[[Link] * 2];
[Link](data, 0, newData, 0, [Link]);
data = newData;
}
}

public void push(int value) {


ensureCapacity();
data[++top] = value;
}

public int pop() {


if (isEmpty()) throw new RuntimeException("Stack is empty");
return data[top--];
}

public int peek() {


if (isEmpty()) throw new RuntimeException("Stack is empty");
return data[top];
}

public boolean isEmpty() {


return top == -1;
}
}

3. Time Complexities
Operation Linked List Array

Push O(1) O(1) amortized

Pop O(1) O(1)


Peek O(1) O(1)

4. JDK Details
Java provides '[Link]' which extends Vector and is synchronized (thread-safe), but it
is generally considered legacy. The recommended Deque interface and its implementation
'[Link]' should be used for Stack behavior (LIFO). ArrayDeque is faster than
Stack when used as a stack.

You might also like