[자료구조] 큐, 스택

원문: https://blog.naver.com/qoxmfaktmxj/223750360943

큐(Queue)

데이터 저장 시, 삽입한 순서대로 데이터가 출력되는 자료구조

선입선출(FIFO - First in First out)

처음 들어간 데이터가 제일 먼저 나가는 특징

파이프라인처럼 들어오면 순서대로 나간다 (반대 : LIFO Last in First out , ex.스택)

인큐(Enqueue) - 큐에 데이터 삽입

디큐(Dequeue) - 큐에 데이터 출력 및 삭제

이전 학습한 LinkedList도 큐 구현체로 사용

생산자 람다식에서 10번 돌면서 10가지 정수를 인큐 합니다.

소비자 람다식에서 무한루프 돌면서 큐에서 데이터 디큐 합니다.

큐에 더이상 넣을 공간이 없을때는 대기하고 디큐할떄 공간이 비면 디큐 하기 위해

poll에 시간을 넣습니다. (큐에 데이터 들어올때까지 얼마나 기다릴수 있을까)

ex)프로듀서는 1초마다 한번씩 인큐하고 소비자는 데이터 생길때마다 디큐함

public class test3{ public static void main(String[] args) throws ExecutionException, InterruptedException {

// 큐 인터페이스 링크리스트 인스턴스 선언 Queue<String> queue = new LinkedList<>();

//넣기 queue.offer(“one”); queue.offer(“two”); queue.offer(“three”);

//갯수 확인 System.out.println(queue.size());

System.out.println(queue.poll()); System.out.println(queue.poll());

//갯수 확인 System.out.println(queue.size());

//두 스레드 실행하기 위한 익스큐터 생성 try(ExecutorService executor = Executors.newFixedThreadPool(2)) { runProducerConsumer(executor); } }

private static void runProducerConsumer(ExecutorService executor) throws ExecutionException, InterruptedException { //프로듀서 컨슈머로 데이터 보내기 위한 큐 자료구조 //멀티스레드 동시성(Concurrency) BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(1);

//프듀 생산자 Runnable producer = () -> { try{ for (int i = 0; i < 10; i++){ //데이터 생성 시뮬 1초 줌 Thread.sleep(1000);

//큐 데이터 전달(enqueue) queue.offer(1); System.out.println(i);

} }catch (InterruptedException e){ e.printStackTrace(); } };

//컨슈머 소비자 Runnable consumer = () -> { try{ Integer value;

//큐 데이터 추출(dequeue) , 큐 비면 2초 대기 while(true){ value = queue.poll(2,TimeUnit.SECONDS); System.out.println(value); } } catch (InterruptedException e) { e.printStackTrace(); } };

//프로듀서, 컨슈머 실행 Future<?> producerFuture = executor.submit(producer); Future<?> consumerFuture = executor.submit(consumer);

//프로듀서 실행끝날때까지 대기 producerFuture.get();

//컨슈머 종료 consumerFuture.cancel(true); } }

큐를 하나의 프로그램으로 만들어 버림 = > 메세지 브로커

위를 봤을 때, 트래픽 몰리면 데이터 유실 될 수 있음 (주문량 너무 많을 때)

주문 -> 결제 -> 배달 모든 곳에서 누락될 수 있음

누락되지 않고 순서대로 하기 위해서는 큐가 필요하다 ( 카프카 많이 씀)

스택(Stack)

	큐 Queue	스택 Stack
입출력 순서	선입선출(FIFO)	후입선출(LIFO)
삽입 연산	enqueue	push
출력(삭제) 연산	dequeue	pop
사용 예시	대기열순서작업예약너비우선탐색(BFS, Breadth-First Search)캐시	웹 브라우저 뒤로가기실행 취소깊이우선탐색(DFS, Depth-First Search)수식의 괄호와 연산 순서 검사

public class test4 { public static void main(String[] args) throws ExecutionException, InterruptedException { Stack<String> st = new Stack<>();

//스택 추가 st.push(“one”); st.push(“two”); st.push(“three”); System.out.println(st);

//스택 제거 String book = st.pop(); System.out.println(book); System.out.println(st);

//제거 안하고 조회 book = st.peek(); System.out.println(book); System.out.println(st);

String exp = “231+*9-”;

//아래 함수 결과 확인 System.out.println(evaluatePostfix(exp));

} public static int evaluatePostfix(String exp) { Stack<Integer> st = new Stack<>();

for(int i = 0; i <exp.length(); i++){ char ch = exp.charAt(i);

if(Character.isDigit(ch)){ st.push(ch - ‘0’); }else{ int val1 = st.pop(); int val2 = st.pop();

switch (ch){ case ‘+’: st.push(val2 + val1); break; case ‘-’: st.push(val2 - val1); break; case ‘*’: st.push(val2 * val1); break; case ‘/’: if(val1 != 0){ st.push(val2 / val1); }else{ throw new ArithmeticException(“0으로는 못나눔”); } break; } System.out.println(st); } } return st.pop(); } }

위 예제 결과

쓰이는 부분 예시