[Data Structure (Java)] Stack

https://crane206265.tistory.com/76

[Data Structure (Java)] SLL (Singly Linked List)

이번글과 다음글에는 Stack, Queue입니다. 이번글에서는 Stack과 Queue를 비교하고, 그중 Stack에 대해 집중적으로 다루겠습니다.

---

Stack VS Queue

	Stack	Queue
commonality	- value : collection of object - operation : add, remove, iterate, empty test
difference	LIFO (Last In First Out) : remove the item most recently added	FIFO (First In First Out) : remove the item least recently added

---

before implementation, some code with class

keyword this : 'second constructor' - to invoke another constructor in the same class

public class ArrayStack<E> implements Stack<E> {
...
}​

implements Stack<E>
: "this class implements the interface of stack"
if we didn't implements the operation of stack ==> Java compiler generates a message

---

Stack API

API of Stack<E> class

methods	explanation
void push(E e)	add an item to the collection (add to top)
E pop()	remove and return the item most recently added (remove from top)
E top()	return the top element
boolean isEmpty()	return if stack is empty
int size()	return the size of stack

---

Stack implementation - Fixed-capacity array

public class ArrayStack<E> implements Stack<E> {
    //----- setting & constructor -----
    public static final int CAPACITY = 1000; //default capacity
    
    private E[] data;
    private int t = -1;
    public ArrayStack() { this(CAPACITY); }
    public ArrayStack(int capacity) {
    	data = (E[]) new Object[capacity];
    }
    
    //----- methods -----
    public int size() { return (t+1); }
    
    public boolean isEmpty() { return (t == -1); }
    
    public void push(E e) throws IllegalStateException {
    	if(size() == data.length) throw new IllegalStateException("Stack is full");
        data[++t] = e;
    }
    
    public E top() {
    	if(isEmpty()) return null;
    	return data[t];
    }
    
    public E pop() {
    	if(isEmpty()) return null;
        E answer = data[t];
        data[t] = null;
        t--;
        return answer;
    }
    //avoid loitering
}

 

* throw, throws : about error occurtion -> 나중에 따로 다루겠습니다.

 

* loitering : holding a reference to an object when it's no longer needed

 

Properties about Fixed-capacity array stack
- running time analysis : O(1) for every operation
- memory use : fixed-capacity -> specify capacity appropriately not to waste the memory

---

Stack implementation : Linked Lists

public class StackNode<E> implements Stack<E> {
    //----- Nested Node Class -----
    private static Node<E> {
    	private E item;
        private Node<E> next;
    }
    
    //----- StackNode class instance variable & methods -----
    private Node<E> first;
    private int n;
    
    public StackNode<E>() {
    	first = null;
        n = 0;
    }
    
    public int size() { return n; }
    
    public boolean isEmpty() { return (n == 0); } //or first == null;
    
    public void push(E e) {
    	Node<E> oldfirst = first;
        first = new Node<E>();
        first.item = e;
        first.next = oldfirst;
        n++;
    }
    
    public E pop() {
    	if(isEmpty()) return null;
    	E answer = first.item;
        first = first.next;
        n--;
        return answer;
    }
    
    public E top() {
    	if(isEmpty()) return null;
    	return first.item;
    }
}

 

or we can use SLL class

public class LinkedStack<E> implements Stack<E> {
    private SinglyLinkedList<E> list = new SinglyLinkedList<>();
    
    public LinkedStack() {}
    
    public int size() { return list.size(); }
    public boolean isEmpty() { return list.isEmpty(); }
    public void push(E e) { list.addFirst(e); }
    public E pop() { return list.removeFirst(); }
    public E top() { return list.first(); }
}

 

Properties about Linked-List stack
- running time analysis : O(1) for every operation
- memory use : scalable