Data Structure & Algorithm/알고리즘(Algorithm)

05. 스택, 큐, 덱

jihyeon99 2024. 6. 20. 15:23

1. 스택 (Stack)

개념
  • 후입선출 구조(LIFO; Last In First Out)로, 먼저 들어간 데이터가 나중에 나오는 자료구조입니다.
  • 데이터가 들어가는 곳과 나가는 곳이 같습니다.
주요 형태와 연산
Stack<T> st = new Stack<>();
T는 스택 안에 들어갈 원소의 타입이며, reference type만 가능 (ex. int 불가, Integer 가능)
  • push(E) : E를 스택 맨 위에 추가합니다.
  • size() : 현재 스택에 들어있는 데이터의 개수를 반환합니다.
  • isEmpty() = empty() : 현재 스택 비어있다면 true, 비어있지 않다면 false를 반환합니다.
  • peek() : 스택의 맨 위에 있는 데이터를 반환합니다. 단, 스택에서 그 데이터를 제거하지는 않습니다.
  • pop() : 스택의 맨 위에 있는 테이터를 반환하고, 동시에 스택에서 그 데이터를 제거합니다. 

스택이 비어있는 경우, pop 또는 peek 연산을 시도하면 EmptyStackException이 발생합니다. 따라서, peek()과 pop()을 수행할때는 스택이 비어있는지에 주의해야합니다.

Stack<Integer> s = new Stack<>();   // 정수를 관리할 stack을 선언합니다. => 빈 스택

s.push(2);
s.push(5);

while(!s.isEmpty()){                // 가장 나중에 들어간 원소부터 순서대로 출력합니다.
    System.out.println(s.pop());    // 순서대로 5 2 출력됩니다.
}

 

시간 복잡도

맨 뒤에서 값을 넣고, 빼기 때문에 다른 값들의 이동이 발생하지 않습니다.

따라서, 삽입과 삭제 연산의 시간복잡도는 O(1)입니다.

 

배열을 스택처럼 사용하기

배열의 맨 뒤에서 데이터를 삽입하고 삭제한다면, 삽입과 삭제의 시간복잡도를 O(1)로 만들 수 있습니다.

일반적인 스택과 달리, 중간 데이터를 확인할 수 있다는 장점이 있지만, push()를 수행할때는 스택이 이미 가득찼는지(배열의 인덱스를 벗어나는지) 주의해야합니다.

 

배열 대신 연결리스트를 이용해서도 스택을 구현할 수 있으며, 이때의 삽입과 삭제의 시간복잡도 O(1)입니다.

 

스택의 응용
  • 쌍을 이루고 있는 것들이 올바르게 배치되어 있는지 확인할 때 유용하게 사용할 수 있습니다.
    • ex) 괄호 문제 : 제시된 괄호 문자열이 올바른지 확인
      • 여는 괄호가 나올 경우 스택에 넣고, 닫는 괄호가 나올 경우 스택에 있는 여는 괄호를 빼면 됩니다.
      • 만약, 닫는 괄호가 나왔는데 스택에 아무것도 없거나, 모든 글자를 다 처리하였음에도 스택에 괄호가 남아있다면 올바를 괄호 문자열이 아닙니다.
  • 재귀와 콜 스택
    • 콜 스택은 함수 실행과정(함수 중간 지점)을 저장하기 위해 사용하는 스택을 말합니다.
    • 재귀적으로 호출한 함수가 실행이 되고, 이후 종료가 되면 그 함수를 수행한 지점(맨 마지막에 저장했던 지점)으로 되돌아갑니다. 
    • 하나의 함수 안에서 여러개의 함수를 재귀적으로 호출하는 경우, 동시에 여러 개의 함수가 들어가는 것이 아니라, 순차적으로 첫 번째 함수 먼저 들어가서 다 계산을 한 다음 → 두 번째 함수 → .. 가 콜 스택에 들어가게 됩니다. 예를 들어, recur(n)함수 안에서 recur(n-1) + recur(n-2)를 호출하는 경우, recur(n-1)이 먼저 들어가서 종료되고 난 후 recur(n-2)를 호출하게 됩니다.

2. 큐 (Queue)

개념
  • 선입선출 구조(FIFO; First In First Out)로, 먼저 들어간 데이터가 먼저 나오는 자료구조입니다.
  • 데이터가 들어가는 곳과 나가는 곳이 다릅니다.
주요 형태와 연산
Queue<T> q = new LinkedList<>();
T는 큐 안에 들어갈 원소의 타입이며, reference type만 가능 (ex. int 불가, Integer 가능)
  • offer(E) : E를 큐 맨 뒤에 추가합니다.
  • size() : 현재 큐에 들어있는 데이터의 개수를 반환합니다.
  • isEmpty() : 현재 큐가 비어있다면 true, 비어있지 않다면 false를 반환합니다.
  • peek() : 큐의 맨 앞에 있는 데이터를 반환합니다. 단, 큐에서 해당 데이터를 제거하지는 않습니다.
  • poll() : 큐의 맨 앞에 있는 데이터를 반환하고, 동시에 큐에서 해당 데이터를 제거합니다.

add, remove, element는 각 연산이 실패했을 때 예외를 던지지만, offer, poll, peek은 각 연산이 실패했을 때 특정 값(null 또는 false)을 반환합니다.

Queue<Integer> q = new LinkedList<>(); // 정수를 관리할 queue를 선언합니다. => 빈 큐

q.add(3); 
q.add(5);

while(!q.isEmpty()){              // 가장 앞에 있는 원소부터 순서대로 출력합니다.
    System.out.println(q.poll()); // 순서대로 3 5가 출력됩니다.
}

 

시간 복잡도

비록 데이터의 삽입과 삭제가 동일한 장소에서 수행되지는 않지만, 다른 값들의 이동이 필요하지 않습니다.

따라서, 삽입과 삭제의 시간복잡도는 O(1)입니다.

 

연결리스트를 큐처럼 사용하기

배열 맨 앞에서 삽입을 하고 맨 뒤에서 삭제를 하거나, 맨 뒤에서 삽입을 하고 맨 앞에서 삭제를 해야할 것입니다. 그러나, 배열의 맨 앞에서 삭제나 삽입을 진행한다면, 무조건 O(N)의 시간복잡도를 갖게 됩니다. 따라서 배열을 큐처럼 사용하기에는 다소 무리가 있습니다.

 

배열 대신 연결리스트를 이용하여 큐를 구현한다면, 삽입과 삭제의 시간복잡도는 O(1)로 만들 수 있습니다.

 

큐의 응용
  • 큐에 들어간 데이터가 상황에 따라 다시 큐에 들어가야 한다면, 원형 큐 구조를 사용할 수 있습니다.
    • 원형 구조의 가운데를 잘라 펼쳐보면, 앞에서 설명했던 선형 구조가 됩니다. 따라서 원형 구조는 선형 구조로 바꾸어 생각할 수 있습니다.
    • ex) N명의 사람 중에 K번째 사람이 죽는 상황에서 최후 1인의 위치 구하기 (처음에는 1번에서 시작하여, 시계방향으로 계속 회전함)
      • K-1 번 반복하며 큐의 앞에서 꺼낸 사람을 큐의 맨 뒤에 집어넣습니다.
      • 큐의 맨 앞의 사람을 제거합니다.
      • 위의 과정을 큐의 크기가 1보다 클때까지 반복하며, 마지막으로 큐의 맨 앞의 사람이 최후의 1인입니다.
  • 큐를 스택처럼 사용하기
    • 새로운 큐를 하나 더 사용하여 큐를 스택처럼 사용할 수 있습니다.
    • push 연산의 경우에는 기존의 queue에 push를 수행합니다.
    • pop 연산의 경우에는 기존 queue에 있던 데이터를 마지막 하나를 제외하고 전부 새로운 큐에 옮겨준 뒤, 기존 큐를 새로운 큐로 대체해두고 마지막 원소를 반환합니다. 

3. 덱 (Deque)

개념
  • 맨 앞/뒤에서 삽입/삭제가 모두 가능한 스택과 큐의 장점을 합친 자료구조입니다.
주요 형태와 연산
 Deque<T> dq = new ArrayDeque<>();
T는 덱 안에 들어갈 원소의 타입이며, reference type만 가능 (ex. int 불가, Integer 가능)
  • offerFirst(E) : E를 덱 맨 앞에 추가합니다.
  • offerLast(E) : E를 덱 맨 에 추가합니다.
  • size() : 현재 덱에 들어있는 데이터의 개수를 반환합니다.
  • isEmpty() : 현재 덱이 비어있다면 true, 비어있지 않다면 false를 반환합니다.
  • peekFirst() : 덱의 맨 앞에 있는 데이터를 반환합니다. 단, 덱에서 해당 데이터를 제거하지는 않습니다.
  • peekLast() : 덱의 맨 뒤에 있는 데이터를 반환합니다. 단, 덱에서 해당 데이터를 제거하지는 않습니다.
  • pollFirst() : 덱의 맨 앞에 있는 데이터를 반환하고, 동시에 덱에서 해당 데이터를 제거합니다
  • pollLast() : 덱의 맨 뒤에 있는 데이터를 반환하고, 동시에 덱에서 해당 데이터를 제거합니다 .

앞/뒤에서 모두 삽입/삭제를 진행하므로, pollLast, offerLast, pollFirst, offerFirst 총 4가지의 삽입/삭제 연산이 있습니다.

addFirst, addLast, removeFirst, removeLast, getFirst, getLast는 각 연산이 실패했을 때 예외를 던지지만, offerFirst, offerLast, pollFirst, pollLast, peekFirst, peekLast는 각 연산이 실패했을 때 특정 값(null 또는 false)을 반환합니다.

Deque<Integer> dq = new ArrayDeque<>(); // 정수를 관리할 deque를 선언합니다. => 빈 덱

dq.addFirst(3);                         // 맨 앞에 3을 추가합니다.
dq.addFirst(5);                         // 맨 앞에 5를 추가합니다.
dq.addLast(9);                          // 맨 뒤에 9를 추가합니다.

System.out.println(dq.pollFirst()));    // 맨 앞에 적혀있는 숫자인 5가 출력됩니다.
System.out.println(dq.pollLast()));     // 맨 뒤에 적혀있는 숫자인 9가 출력됩니다.

 

시간 복잡도

연결리스트를 사용하여 덱을 구현하면, 양쪽 끝에서 삽입/삭제하는데 걸리는 시간이 O(1)이 됩니다.

따라서, 삽입과 삭제의 시간복잡도는 O(1)입니다.

저작자표시 (새창열림)