자바(Java) 스택(Stack)과 큐(Queue) 정리

자바(Java) 스택(Stack)과 큐(Queue)에 대한 정리

▶ 스택(Stack)

- 데이터를 일시적으로 저장하기 위해 사용하는 구조

- 데이터의 입력과 출력 순서 : 후입선출(LIFO, Last In First Out)

  가장 마지막에 넣은 데이터를 가장 먼저 꺼낸다.

- 데이터를 넣는 작업을 푸쉬(push)라 하고, 꺼내는 작업을 팝(pop)이라고 한다.

- 푸쉬와 팝을 하는 위치를 꼭대기(top)라 하고, 스택의 가장 아랫부분을 바닥(bottom)이라 한다.

- 스택에는 배열을 사용하는 것이 효율적이다.(끝 인덱스부터 순차적으로 삭제하기 때문이다.)

- 스택을 사용하려면 Stack이라는 클래스를 사용하면된다. Stack st = new Stack();

 Stack 클래스의 메서드

  boolean empty() : Stack이 비어있는지 알려준다.

  Object peek() : Stack의 맨 위에 저장된 객체를 반환한다. (객체를 꺼내지 않는다.)

                      (만약 비어있으면 EmptyStackException 발생)

  Object pop() : Stack의 맨 위에 저장된 객체를 꺼낸다.

  Object push(Object item) : Stack에 객체(item)를 저장한다.

  in search(Object o) : Stack에서 주어진 객체를 찾아서 그 위치를 반환(못찾으면 -1반환)

                             (indexOf()랑 비슷하지만 0이 아닌 1부터 시작.) 

-> 사용예시)        Stack st = new Stack();

st.push("0");

st.pop("0");

▶ 큐(Queue)

- 데이터를 일시적으로 저장하기 위해 사용하는 구조

- 데이터의 입력과 출력 순서 : 선입선출(FIFO, First In First Out)

  제일 먼저 넣은 데이터를 가장 먼저 꺼낸다.

- 데이터를 넣는 작업을 오퍼(offer)라 하고, 꺼내는 작업을 폴(poll)이라 한다.

- 데이터를 꺼내는 쪽은 프론트(front), 넣는 쪽을 리어(rear)라 한다.

- 큐는 링크드리스트를 사용하는 것이 효율적이다.

  (맨 앞 인덱스부터 순차적으로 삭제하기 때문에 인덱스 0,1,2에서 0에 데이터값을 삭제하면

   1,2에 있던 값들이 앞으로 옮겨와야하기때문에 링크드리스트가 적합하다.

   링크드리스트는 요소만 삭제하면되기때문에 자리이동이 필요없다.)

- 큐를 사용하려면 Queue라는 인터페이스를 사용하면 된다.

  Queue의 메서드

  boolean add(Object o) : 지정된 객체를 Queue에 추가함. 성공시 true를 반환한다.

                                  저장공간이 부족하면 IllegalStateException 발생

  Object remove() : Queue에서 객체를 꺼내 반환, 비었으면 NoSuchElementException 발생

  Object element() : 삭제없이 요소를 읽어온다. 비어있으면 NoSuchElementException 발생

  boolean offer(Object o) : Queue에 객체를 저장, 성공시 true, 실패시 false 반환

  Object poll() : Queue에서 객체를 꺼내 반환, 비어있으면 null을 반환(예외 발생 x)

  Object peek() : 삭제없이 요소를 읽어온다. Queue가 비어있으면 null을 반환(예외 발생 x)

-> 사용예시) Queue q = new LinkedList();

q.offer("0");

q.remove("0");

- 자바에서 Queue는 인터페이스이다.(인터페이스는 객체생성 x)

  1. Queue를 직접구현한다.

  2. Queue를 구현한 클래스를 사용함 -> Java API에서 Queue를 구현한 클래스를 사용해라.