저희 스터디는 이번 한 주 동안 큐(Queue) / 스택(Stack) 강의를 들었습니다.
큐(Queue)
큐애 대해서 간략하게 설명하자면, 가장 먼저 삽입된 것이 가장 먼저 삭제되는 FIFO(First-In, First-Out) 방식의 자료구조 입니다.
비유해서 설명하자면, 저희가 학생 시절, 매점에서 줄 서 있는 경우 또는 신호등이 바뀌기를 기다리며 대기 중인 차들 등을 큐 구조라고 볼 수 있습니다.
이런 특징을 갖는 큐는 JAVA에서 큐 클래스를 제공하고 있는데, 여기서 알고리즘 문제를 풀 때, 저 같은 경우에 데이터를 저장하기 위해 LinkedList를 사용했습니다.
Queue<Integer> queue = new LinkedList<>();하지만, 다른 그룹원 분은 저와는 다르게 ArrayDeque 클래스를 사용하여 알고리즘 문제를 해결하였는데, 이게 메모리와 속도 차이가 많이 났습니다.
ArrayDeque를 사용했을 때의 성능이 LinkedList 사용 했을 때의 메모리와 속도가 각각 1/10, 1/2로 줄었습니다. 즉, ArrayDeque가 더 효율적이라는 의미입니다.
같은 그룹원 분이 큐 구현이 어느 것이 적당할까? LinkedList vs ArrayDeque 라는 정말 친절하게 설명해주신 게시글을 공유주셨습니다.
메모리와 속도차이가 나는 이유?
JAVA API Document에 따르면 큐를 구현할 때, LinkedList보다 ArrayDeque로 구현하는 것이 더 빠르다고 설명이 되어있다고 합니다.
그렇다면 왜 메모리와 속도가 차이가 나는 걸까요?
일단, ArrayDeque는 LinkedList와는 다르게 Array에 의해 지원되기 때문에, 캐시 지역성이 좀 더 친숙하여 속도 면에서 더 성능이 좋고 다음 노드에 대한 추가 참조가 필요 없기 때문에 메모리가 효율적입니다.
큐를 구현할 때는 좀 더 효율적인 메모리와 속도를 위해 LinkedList보다 ArrayDeque를 사용하는 것이 더 낫다는 것을 배운 시간이였습니다.
또한, 밑에서 설명할 스택 문제를 Leecode에서 풀었는데, 큐를 이용하여 스택의 push()나 pop() 메서드 등을 구현하는 문제였습니다.
그 과정에서, deque를 사용하여 풀었는데, deque는 양방향에서 삽입과 삭제를 할 수 있는 자료구조입니다. 거기서 저는 top() 메서드를 deque.peekLast()를 사용하여 덱의 가장 위에 있는 데이터를 출력하였고 어떤 그룹원분은 deque.peek() 메서드를 사용하였습니다.
peekLast() 메서드는 가장 뒤에 있는 데이터를 출력하고 peek() 메서드는 가장 앞에 있는 데이터를 출력하는데, 문제 결과는 성공적으로 해결했습니다. 차이점은 값을 저장했던 부분에서 있었던 것 같습니다.
저 같은 경우는 add() 메서드를 사용하여 값을 저장했는데, 이는 덱의 마지막에 데이터를 삽입하고, 다른 그룹원분은 push() 메서드를 사용하여 값을 저장했습니다. push() 메서드는 덱의 앞에 데이터를 삽입하는 방식이였기 때문에 값을 반환하는 다른 메서드들을 사용했지만 결과는 성공이라고 생각합니다.
deque를 처음 사용해본 것은 아니였는데, 이번에 값을 삽입하는 add() 함수와 push() 함수의 차이에 대해서 알게되었습니다.
스택(Stack)
스택이라는 의미는 쌓아올린 더미를 말합니다.
가장 나중에 삽입된 데이터가 가장 먼저 삭제되는 LIFO(Last-In, First-Out) 방식의 구조입니다.
학생 때, 급식을 먹고 쌓아놓은 식판, 책상 위에 쌓아놓은 책 등을 스택 구조라고 비유해서 설명할 수 있습니다.
큐는 위의 설명대로면, 양쪽 끝에서 삽입과 삭제가 일어나는데, 그와 다르게 스택은 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조로 되어있습니다.
JAVA에서 Stack 클래스를 제공하고 있기 때문에 편리하게 사용할 수 있습니다.
Stack<Integer> stack = new Stack<>();느낀점
어쩌다보니 큐 문제만을 풀었기 때문에 스택의 개념에 대해서만 배웠던 것 같습니다. 다음에 알고리즘을 풀면서 스택에 대해서 더 알게될 좋은 기회가 있을 것이라 생각합니다.
그리고 이번에 알고리즘을 풀면서 저한테는 정말 쉽지 않은 문제들이였는데, 그래도 일단 풀었다는 점에서 긍정적이지만 아직은 너무나도 부족하다는 것을 알게되었습니다.
앞으로 더 발전했으면 좋겠습니다.
