3.스택과큐

스택(Stack)

• 스택은 데이터를 일시적으로 저장하기 위한 자료구조

• 데이터의 입력과 출력 순서는 후입선출(Last In First Out)

스택 데이터 관리

• 데이터를 넣는 작업을 푸시(Push)

• 데이터를 꺼내는 작업을 팝(Pop)

• push와 pop을 하는 위치를 꼭대기(Top), 스택의 가장 아랫부분을 바닥(Bottom)이라 한다.

• 스택의 가장 최근에 입력된 데이터를 확인하는 peek

큐(Queue)

• 큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아 놓는 자료구조

• 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO: First In First Out)

큐 데이터 관리

• 큐에 데이터를 넣는 작업을 인큐(enqueue)

• 데이터를 꺼내는 작업을 디큐(dequeue)

• 데이터를 꺼내는 쪽을 프런트(front)

• 데이터를 넣는 쪽을 리어(rear)

일반 큐의 단점

• 인큐 작업을 하는 경우 처리 복잡도는 O(1)

• 디큐 작업을 하는 경우 맨 앞의 요소를 꺼낸 뒤에 남은 모든 요소를 맨 앞으로 옮기는 작업으로 처리하여 O(N)이므로 효율적이지 못하다.

큐의 단점을 해소하기 위한 링 버퍼(ring buffer)로 구현된 큐(queue)

• 배열의 요소를 앞쪽으로 옮기지 않는 큐

• 프런트(front)와 리어(rear)를 연결된 자료구조

자바에서 사용하는 Queue

• LinkedList 같은 일부 구현체는 null 삽입을 금지하지 않지만, Queue는 일반적으로 null 요소의 삽입을 허용하지 않는다.

• Queue에서 null의 의미가 Queue 내에 요소가 없음을 의미하기 때문이다.

면접문제

1. 한 개로 세 개

2. 스택은 단순히 가장 최근에 추가된 원소를 가장 먼저 제거하는 자료구조(LIFO)이다.

3. 배열을 사용해서 스택 하나를 흉내 낼 수 있겠는가? 이를 구현하는 방법은 다양하며, 각각 장단점이 있다는 사실을 명심하라.

4. 배열의 처음 1/3은 첫 번째 스택, 두 번째 1/3은 두 번째 스택, 세 번째 1/3 은 세 번째 스택으로 할당한다면 세 개의 스택을 흉내 낼 수 있다.

5. 하지만 스택 하나가 다른 스택보다 크기가 커지는 경우가 생길 수도 있다. 배열을 나누는 크기를 좀 더 유동적으로 정할 수 있을까?

6. 유동적인 분할을 허용하고 싶다면, 스택을 이동할 수 있다. 사용 가능한 모든 공간을 사용할 수 있는가?

7. 순환 배열을 생각해 보자. 순환 배열이란, 배열의 마지막과 앞부분이 연결 된 것을 말한다.

8. 스택 Min

9. 최소 원소는 자주 변하지 않는다는 사실에 주목하라.

10. 더 작은 원소가 추가되거나 최소 원소를 빼내야 할 때만 바뀐다.

11. 각각의 스택 노드에서 추가 데이터를 저장하고 있다면 어떨까?

12. 어떤 종류의 데이터를 갖고 있어야 문제를 풀기 쉬워지나?

13. 각각의 노드가 부분스택(자신을 포함해서 자신보다 아래에 있는 모든원소)의 최솟값을 알고 있다고 가정하자.

14. 접시 무더기

15. 각 부분스택의 크기를 알고 있어야한다. 스택이 꽉차면 새로운 스택을 만들어야 한다.

16. 특정 부분스택에서 원소를 빼낸다는 것은 일부스택이 꽉 차지않았다는 것을 의미한다.

17. 이게 문제가 되나? 정답이 있는 것은 아니다. 다만, 이런 경우를 어떻게 처리할지 생각해 보아야 한다.

18. 스택으로 큐

19. 큐와 스택의 가장 큰 차이점은 원소의 순서이다.

20. 큐는 오래된 원소부터 삭제하고 스택은 최근 원소부터 삭제한다.

21. 스택의 최근 원소에만 접근이 가능할 때, 스택에서 가장 오래된 원소를 삭제하려면 어떻게 해야 할까?

22. 원소가 하나 남을 때까지 스택에서 원소를 반복적으로 빼낸 뒤, 임시 스택에 잠시 넣어두면 가장 오래된 원소를 삭제할 수 있다.

23. 그 다음 최근 원소를 검색한 뒤 모든 원소를 다시 스택에 넣는다.

24. 이 방법의 문제점은 원소를 연속으로 빼내기 위해 O(N) 작업이 매번 필요하다는 점이다.

25. 원소를 연속으로 여러 개 빼내야 하는 이 상황을 최적화할 수 있겠는가?

26. 스택 정렬

27. 배열을 정렬하는 한 가지 방법은 배열을 순회하면서 모든 원소를 새로운 배열에 정렬된 순서로 삽입하는 것이다.

28. 스택을 사용해서 이 방법을 시도해 볼 수 있겠는가?

29. 두 번째 스택이 정렬되어 있다고 생각해 보자. 정렬된 스택에 새로운 원소 를 삽입할 수 있는가?

30. 추가 저장공간이 필요할지도 모른다. 추가 저장공간으로 무엇을 할 수 있는가?

31. 두번째 스택을 정렬된 상태로 유지하고, 가장 큰 원소를 위에 두라. 첫번째 스택을 추가 저장공간으로 사용하라.