Java 스택과 큐(Stack & Queue), 스택& 큐 활용

자료구조(datastructure)

• 어떤 식으로 저장해야하는지 정리해논 학문이다.
• 종류 : Stack, Queue,.. 등( 자료구조의 추가 정리는 아래 링크 참고)
• 2023.07.12 - [📚 자격증/정처기] - [정처기 필기] 자료구조, 스택, 큐, 데크, 트리, 이진트리

 

스택(Stack)

• LIFO(Last In first Out)구조이다.(= 마지막에 저장된 것을 제일 먼저 꺼낸다. =밑이 막힌 상자라고 생각하면 된다.)
• 저장(push), 추출(pop)한다.
• 배열로 구현하면 좋다.

 

큐(Queue)

• FIFO(First In First Out)구조이다.(= 제일 먼저 저장한 것을 제일 먼저 꺼낸다. = 양끝이 뚫린 상자 or 줄서기라 생각하면 된다.)
• 저장(offer), 추출(poll)한다.
• 링크드리스트로 구현하면 좋다. 큐로 만들면 삭제시 자리 이동이 없다.

 

그림으로 보는 Stack & Queue 자료 구조

 

Stack의 메서드

Stack st = new Stack(); // 사용시 객체생성후 사용하면된다.

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

 

• Object peek()
  Stack의 맨 위에 저장된 객체를 반환한다.
  pop()과 달리 Stack에서 객체를 꺼내지는 않는다.(비었을 때는 EmptyStackException 발생)

 

• Object pop()
  Stack의 맨 위에 저장된 객체를 꺼낸다.(비었을 때는 EmptyStackException 발생)

 

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

 

• int search(Object o)
  Stack에서 주어진 객체(o)를 찾아서 그 위치를 반환한다.(못찾으면 -1을 반환한다. 배열과 달리 위치는 0이 아닌 1부터 시작)

 

Queue의 메서드

Queue q = new LinkedList();

자바에서는 큐는 인터페이스 정의가 되어있다.

Queue q = new Queue(); // => 이렇게 사용불가. Queue는 인터페이스

따라서 Queue를 사용할려면

1. Queue를 직접 구현
2. Queue를 구현한 클래스를 사용

⇒ 2번 방법을 사용하면 된다.

구현한 클래스가 무엇인지 볼려면 Java API문서에서 Queue를 찾아보면 알 수 있다.

 

• boolean add(Object o)
  지정된 객체를 Queue에 추가한다. (성공하면 true를 반환하고, 저장공간이 부족하면 IllegalStateException발생)

 

• Object remove()
  Queue에서 객체를 꺼내 반환한다.(비어있으면 NoSuchElementException 발생)

 

• Object element()
  삭제없이 요소를 읽어온다.(peek와 달리 Queue가 비었을 때 NoSuchElementException 발생)

 

• boolean offer(Object o)
  Queue에 객체를 저장한다.(성공하면 true, 실패하면 false를 반환)

 

• Object poll()
  Queue에서 객체를 꺼내서 반환한다.(비어있으면 null을 반환)

 

• Object peek()
  삭제없이 요소를 읽어 온다.(Queue가 비어있으면 null을 반환)

 

예제 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class VarEx3 {
	public static void main(String[] args) {
		Stack st = new Stack();
		Queue q = new LinkedList();
		
		st.push("0");
		st.push("1");
		st.push("2");
		
		q.offer("0");
		q.offer("1");
		q.offer("2");
		
		System.out.println("Stack---");
		while(!st.empty()) {
			System.out.println(st.pop());
		}
		
		System.out.println();
		
		System.out.println("Queue---");
		while(!q.isEmpty()) {
			System.out.println(q.poll());
		}
		
	}
}

Stack---
2
1
0

Queue---
0
1
2

 

Stack, Queue의 활용

• 스택의 활용 예 : 수식계산, 수식괄호검사, 워드프로세서의 undo/redo, 웹브라우저의 뒤로/앞으로
• 큐의 활용 예 : 최근 사용문서, 인쇄작업 대기목록, 버퍼(buffer)