자료구조_스택(Stack) / 큐(Queue)_JAVA

스택(Stack)이란?

데이터를 임시 저장할 때 사용하는 자료구조

후입선출(FILO) 방식

어떤 문제에서 스택을 써야할까?

➡️ **기호 짝 맞추기**

괄호의 짝이 맞는지 확인하는 문제

➡️ **히스토그램, 주가 스팬, 트리 순회, 하노이의 타워와 같은 알고리즘**
➡️ **백트래킹이 필요한 문제**

만약 길이 효율적이지 않다면 다시 이전 상태로 돌아와 다른 길로 가기 위해 이전 상태가 저장되어 있는 스택을 사용
ex) 체스, 미로찾기, Knight-Tour 문제, N-Queen 문제

스택 관련 코드

• [기본]

  public class Main {
  
  	public static void main(String[] args) {
  		
          Stack<String> stack = new Stack<String>();
          
          // 데이터 추가
          stack.push("0");
          stack.push("1");
          stack.push("2");
          stack.push("3");
          stack.push("4");
          stack.push("5");
          
          // 가장 상위(마지막에 추가된 원소)값 리턴
          stack.peek();
          
          // 데이터 위치 검색 - 가장 상위 위치 1 기준으로 +1씩 증가 
          stack.search("4"); // 출력: 2
          
          // 크기
          stack.size();
          
          // 데이터 꺼내기(삭제) - 최상위부터 꺼냄  
          stack.pop(); // 출력:5
          
          // 비어있는지 검사 - true|false
          stack.empty(); 
  
  				// 출력 - 1
  				Iterator iter = stack.iterator();
  				while(iter.hasNext()) {
  					System.out.println(iter.next());
  				}
  				
  				// 출력 - 2
  				stack.stream().forEach(S -> System.out.println(S));
          
  				// 출력 -3
  				stack.forEach(System.out::println);
  	}
  	
  
  }

큐(Queue)란?

데이터를 임시 저장할 때 사용하는 자료구조

선입선출(FIFO) 방식

큐의 종류

🔄 순환 큐

front와 rear가 연결되어 계속 순환하는 큐
인덱스를 원형으로 돌려서 7이 0으로 가도록 %연산을 통해 구현

🥇 우선순위 큐

우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조

보통의 큐와 같이 구현하면 데이터를 삽입하기 힘들다는 단점이 있어 주로 힙 자료구조를 사용해 구현

큐 관련 코드

• 큐의 주요 메서드

• [기본]

public class Main {

	public static void main(String[] args) {
		
		Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언
		
		// 데이터 추가  add | offer
		queue.add(1);    
		queue.add(2);   
		queue.offer(3);
		queue.offer(2);
		queue.offer(4);
        
    // 가장 상위(가장 먼저 추가된 원소)값 리턴 element | peek
		queue.element();
		queue.peek();
        
		// 큐 데이터 삭제 remove | poll
		queue.remove(); // 가장 먼저 들어온 값 삭제
		queue.remove(2); // 동일한 값 중 가장 먼저 들어온 값 하나를 삭제 
		queue.poll(); 
		//queue.poll(2); // 원하는 값 삭제 불가능 
		
		// 큐 초기화 
		//queue.clear();
		
		// 출력 - 1
		Iterator iter = queue.iterator();
		while(iter.hasNext()) {
			System.out.println(iter.next());
		}
		// 출력 - 2
		queue.stream().forEach(S -> System.out.println(S));

		// 출력 - 3
		queue.forEach(System.out::println);
    
	}
	

}