스택(Stack), 큐(Queue)

스택 (Stack)

스택이란?

• 후입선출(LIFO)
• 한쪽 방향에서만 데이터 삽입과 삭제 가능
• 용어
  • top(peek) : 가장 최근에 저장된 데이터이자 먼저 삭제될 데이터
  • push : 데이터를 삽입. 삽입된 데이터는 삭제시 가장 먼저 삭제될 데이터
  • pop : 데이터를 삭제. 가장 최근에 저장된 데이터가 삭제
  • isEmpty : 비어있는지 확인
  • isFull : 꽉차있는지 확인
• 사용 예
  • 브라우저의 뒤로가기
  • 실행 취소
  • 재귀 함수
  • 역순 문자열(문자열 거꾸로 뒤집기)
• 시간 복잡도
  • 삽입 및 삭제 : O(1)
  • 탐색 : O(n)

스택 사용법(Java)

Stack<Integer> st = new Stack<>();
st.push(1);
st.push(2);
while (!st.empty())
	System.out.println(st.pop());

큐 (Queue)

• 선입선출(FIFO)
• 한쪽에서는 데이터 삽입, 다른 한쪽에서는 데이터의 삭제만 가능
• 용어
  • enqueue : 데이터 삽입
  • dequeue : 데이터 삭제
  • front : dequeue시 삭제되는 데이터, 가장 먼저 저장된 데이터
  • rear : 추가될 새로운 요소의 위치를 가리킴
  • isEmpty : 비어있는지 확인
  • isFull : 꽉차있는지 확인
• 사용 예
  • BFS 알고리즘
  • 프로세스 관리(JS의 콜백 큐)
  • 프린터의 대기열
• 시간 복잡도
  • 삽입 및 삭제 : O(1)
  • 탐색 : O(n)

큐 사용법(Java)

Queue<Integer> q = new LinkedList<>();
q.offer(1);
q.offer(2);
while (!st.empty())
	System.out.println(q.poll());

큐의 다른 종류

• 우선순위 큐

  • 우선순위 큐의 각 요소는 값과 우선순위, 총 2개의 데이터를 가지고 있음
  • 우선순위가 높은 요소일수록 먼저 삭제되는 특징
  • 우선순위 같으면 삽입 순서를 따름
  • 삽입 및 삭제 시 우선순위에 따라 요소들을 정렬해야 하므로 주로 힙이라는 자료 구조로 구현
  • 힙으로 구현시 삽입 및 삭제에는 O(logn), 우선순위 높은 요소 탐색시에는 O(1)의 시간 복잡도를 가짐

• 원형 큐

  • 선형 큐 단점 보완을 위해 나옴
  • 선형 큐의 경우 삽입 및 삭제가 반복되며 앞의 빈공간 활용이 어려워짐. 이 공간 활용을 위해서 요소들을 앞으로 재배치하는 작업 필요
  • front, rear가 순환하기에 빈 공간 사용 위한 별도 작업 필요치 않음

스택 큐 직접 구현

https://hongjw1938.tistory.com/21
(실제로 쓸 일은 많지 않을 것 같아 링크로 남김)

관련 예상 면접 질문

• Stack과 Queue의 구조에 대해 설명해주세요
  Stack과 Queue는 선형 자료구조의 일종이며, Array와 LinkedList로 구현할 수 있습니다. Stack은 후입선출 방식 즉, 나중에 들어간 원소가 먼저 나오는 구조이고 Queue는 선입선출 방식 즉, 먼저 들어간 원소가 먼저 나오는 구조를 갖습니다.
• Stack와 Queue의 실사용 예를 들어 간단히 설명해주세요.
  Stack같은 경우에는 자바의 Stack 메모리 영역을 예로 들 수 있습니다. 지역변수와 매개변수 데이터 값이 저장되는 공간이며, 메소드 호출시 메모리에 할당되고 종료되면 메모리가 해제되며, 후입선출 구조를 갖습니다.
  Queue같은 경우에는 OS의 스케쥴러를 예로 들 수 있습니다. 자원의 할당과 회수를 하는 스케쥴러 역할을 큐가 할 수 있습니다. 메모리에 적재된 다수의 프로세스 중 어떤 프로세스에게 자원을 할당할 것인가 그 순서를 결정하는 것이 자원이 효율적인 사용에 있고, 가장 단순한 형태의 스케쥴링 정책이 선입선처리 즉 큐라고 볼 수 있습니다.
• 우선순위 큐(Priority Queue)에 대해서 설명해주세요. 동작원리도 말씀해주세요.
  우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터를 먼저 꺼내기 위해 고안된 자료구조입니다. 일반적으로 힙을 이용하여 구현합니다. 힙으로 구현된 이진 트리는 모든 정점이 자신의 자식 요소보다 우선순위가 높다는 성질을 가지고 있습니다. 이 성질을 이용하여 삽입과 삭제 연산을 모두 O(logN)으로 수행할 수 있습니다.