스택 & 큐

Stack

괄호 문제({[}]) , UNDO, DFS 등에 사용

Complexity

• pushing O(1)
• pop O(1)
• Peeking O(1)
• Searching O(n)
• Size O(1)

링크드 리스트 사용한 STACK 구현

public class Stack<T> implements Iterable<T> {
    private LinkedList<T> list = new LinkedList<T>();

    public Stack(){}

    public Stack(T elem){
        push(elem);
    }

    public void push(T elem){
        list.addLast(elem);
    }

    public T pop(){
        if(isEmpty())
            throw new EmptyStackException();
        return list.removeLast();
    }

    public int size(){
        return list.size();
    }

    public boolean isEmpty(){
        return size() == 0;
    }

    public T peek(){
        if(isEmpty())
            throw new EmptyStackException();
        return list.peekLast();
    }

    @Override
    public Iterator<T> iterator() {
        return list.iterator();
    }
}

QUEUE

줄서기, BFS 등에 사용

COMPLEXTITY

• Enqueue O(1)
• Dequeue O(1)
• Peeking O(1)
• Contains O(n)
• Removal O(n)
• IsEmpty O(1)

링크드 리스트를 사용해 큐 구현

public class Queue<T> implements Iterable<T> {

    private LinkedList<T> list = new LinkedList<>();

    public Queue(){}

    public Queue(T elem){
        offer(elem);
    }

    public boolean offer (T elem) {
        return list.offerLast(elem);
    }

    public int size(){
        return list.size();
    }

    public boolean isEmpty(){
        return size() == 0;
    }

    public T peek(){
        //if(isEmpty())
         //   throw new RuntimeException("Queue empty");
        return list.peekFirst();
    }

    public T poll(){
        //if(isEmpty())
         //   throw new RuntimeException("Queue empty");
        return list.pollFirst();
    }

    @Override
    public Iterator<T> iterator() {
        return list.iterator();
    }
}

peek, offer, poll 메소드를 통해 null인 경우 예외처리가 아닌 null 리턴