[DataStructure] Stack (Java)

Stack

참고링크

Module java.base
Package java.util
Class Stack<E>
java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractList<E>
java.util.Vector<E>
java.util.Stack<E>
All Implemented Interfaces:
Serializable, Cloneable, Iterable<E>, Collection<E>, List<E>, RandomAccess

public class Stack<E>
extends Vector<E>

설명

Stack은 데이터를 LIFO 방식을 사용하여 동작합니다
마지막으로 들어온 데이터가 첫번째로 나가는 방식 입니다.

Vector를 상속받아서 Vector의 메서드들을 사용합니다

사실 Vector를 먼저 알아야하는데 Vector는 ArrayList와 같은 인터페이스를 상속받고 순서를 기억하는 리스트 자료구조입니다.
ArrayList와 마찬가지로 자동으로 사이즈를 늘려갑니다.
ArrayList와 차이점은 set이나 get할 때 동기화가 걸려있어서 다중작업시 더 안전하지만 속도는 ArrayList보다 좋지 않습니다.

메서드

boolean    empty()    
데이터가 있는지 없는지 확인하는 메서드
E    peek()    
스택에서 데이터를 제거하지 않고 스택 제일 위에 있는 데이터를 반환하는 메서드
E    pop()    
스택에서 데이터를 제거하면서 스택 제일 위에 있는 데이터를 반환하는 메서드
E    push​(E item)    
스택 제일 위에 item 객체를 생성하는 메서드
int    search​(Object o)    
스택에서 o에 해당하는 데이터의 순서를 반환해주는 메서드

사용법

import java.util.Stack;

public class Test {
    public static void main(String[] args) {
        Stack stack = new Stack();
        stack.add("test1");
        stack.add("test2");
        stack.add("test3");
        System.out.println(stack.search("test1"));
        System.out.println(stack.peek());
        System.out.println(stack.pop());
        System.out.println(stack.search("test3"));
    }
}

/* 결과
3
test3
test3
-1
*/

시간복잡도

empty() – O(1)
peek() – O(1)
pop() – O(1)
push(E item) - 오버플로우 시 Arrays를 복사하여 사이즈를 늘리기 때문에 O(n)
search(Object o) - O(n)

공간복잡도

대부분의 Collection들은 O(n)
참고링크
참고링크