[ 자료구조 ] 스택 & 큐 (Stack & Queue)

 

스택이란? 

LIFO(Last In First Out, 후입 선출) : 마지막 데이터를 먼저 뺀다.

• 스택의 활용
  1. 인터럽트처리, 수식의 계산, 서브루틴의 복귀 번지 저장 등에 쓰임
  2. 그래프의 깊이 우선 탐색(DFS)에서 사용
  3. 재귀적(Recursion) 함수를 호출 할 때 사용
  4. Undo(실행취소, ctrl+Z), redo(되돌 리기, ctrl+Y), 웹브라우저 뒤로가기
  5. 역순 문자열 만들기 : abc >> Stack >> cba
  

/*
* Stack의 Method() : push(), peek(), pop(), clear(), size(), empty(), contains()
*/
Stack<Integer> stack = new Stack<>(); //int형 스택 선언

stack.push(1);     // stack에 값 1 추가
stack.push(2);     // stack에 값 2 추가
stack.push(3);     // stack에 값 3 추가
stack.peek();     // stack의 가장 상단의 값 출력
stack.pop();       // stack의 가장 상단의 값 제거
stack.clear();     // stack의 전체 값 제거 (초기화)

stack.size();      // stack의 크기 출력 : 2
stack.empty();     // stack이 비어있는제 check (비어있다면 true)
stack.contains(1) // stack에 1이 있는지 check (있다면 true)

 

 

 

큐란? 

FIFO(First IN First Out, 선입 선출)  : 먼저 들어간 데이터(old data)를 먼저 뺀다 

 

그림 그리
Enqueue : 큐 맨 뒤에 데이터 추가
Dequeue : 큐 맨 앞쪽의 데이터 삭제

• 큐의 활용
  1. 그래프의 넓이 우선 탐색(BFS)에서 사용
  2. 버퍼 : 처리되지 못하는 데이터들을 대상으로 버퍼(큐)를 만들어 대기 시킴
  3. 우선순위가 같은 작업 예약
  4. 은행업무, 콜센터 대기시간 
  5. 캐시(cache) 구현
  

import java.util.LinkedList; //import
import java.util.Queue; //import

// Queue인터페이스의 구현체인 LinkedList를 사용
Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언, linkedlist 이용
Queue<String> queue = new LinkedList<>(); //String형 queue 선언, linkedlist 이용

queue.add(1);     // queue에 값 1 추가
queue.add(2);     // queue에 값 2 추가
queue.offer(3);   // queue에 값 3 추가

queue.poll();       // queue에 첫번째 값을 반환하고 제거 비어있다면 null
queue.remove();     // queue에 첫번째 값 제거
queue.clear();      // queue 초기화

queue.peek();       // queue의 첫번째 값 참조

 

 

 

우선순위 큐란(Priority Queue)? 

저장순서와 상관없이 우선순위가 높은데이터를 먼저 뺀다. 우선순위 큐는 저장공간을 배열로 사용하며, 각 요소를 heap자료구조 형태로 저장한다.(heap : 최대, 최소값을 가장빠르게 찾을 수 있음)

• 우선순위 큐의 활용
  1. 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조 (큐에 들어가는 원소는 비교가 가능한 기준이 있어야함) 
  2. 내부 요소는 힙으로 구성되어 이진트리 구조로 이루어져 있음   
  3. 내부구조가 힙으로 구성되어 있기에 시간 복잡도는 O(NLogN) 
  4. 응급실과 같이 우선순위를 중요시해야 하는 상황에서 쓰임

import java.util.PriorityQueue; //import

//int형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
//int형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
//String형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(); 
//String형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());



priorityQueue.add(1);     // priorityQueue 값 1 추가
priorityQueue.add(2);     // priorityQueue 값 2 추가
priorityQueue.offer(3);   // priorityQueue 값 3 추가


priorityQueue.poll();       // priorityQueue에 첫번째 값을 반환하고 제거 비어있다면 null
priorityQueue.remove();     // priorityQueue에 첫번째 값 제거
priorityQueue.clear();      // priorityQueue에 초기화

// Priority Queue에서 우선순위가 가장 높은 값을 참조하고 싶다면 peek()라는 메서드를 사용
priorityQueue.peek();       // priorityQueue에 첫번째 값 참조 = 1