Day 18: Queues and Stacks

https://www.hackerrank.com/challenges/30-queues-stacks/problem

스택과 큐를 이용해서 앞뒤가 똑같은 문자열을 확인하는 문제이다.

하루에 한문제씩 풀 예정이였는데, 한번 더 복습하려고 생각했던 자료구조 문제가 나와서

복습진도를 맞추느라 좀 늦어지게 되었다.

문제 자체는 자바에 구현되있는 스택과, 큐를 구현한 컬렉션을 사용해서 간단하게 풀 수 있지만

실제로 스택과 큐가 어떤 코드로 동작하는지 추가적인 공부를 하였다.

지금의 이해도와, 나중에 더 학습하고 나서의 이해도를 비교하기 위해 내용정리를 해봐야 겠다.

Stack은 jvm에 있는 콜스택등을 구현할때 쓰는, 선입후출방식의, 카드더미같은 자료구조이다.

사용할 만한 곳은 콜스택도 있고 할일 뭉터기 카드나, 인터넷 브라우져에서 뒤로, 앞으로등도 스택으로 구현할 수 있다.

그리고 재귀함수등도 스택으로 처리할테고, 어떤 길을 지나간뒤, 다시 돌아오는 등의 형태에서도 사용할 수 있을듯 하다.

큐는 파이프, 혹은 대기줄같은 선입선출방식의 자료구조이다.

순서대로 처리해야 하는 일들, 음식주문이나 고객센터 문의사항 처리, 대기표 발급이나 게임이나 프로그램의 예약명령어등이 있겠다.

내가 공부했던 자바책에선, 스택과 큐 둘다 linkedlist로 구현했다고 한다.

linkedlist는 순서가 없고, 각 노드가 이전이나 다음노드를 가지고 있는 연결된 줄같은 자료구조인데

뒤로만 연결되있는 형태가 기본형 LinkedList이고

앞의 노드도 가지고 있어서 앞뒤로 이동할 수 있는 형태가 doubleLinkedList이며

제일 처음과 끝을 연결한 형태는 CircularLinkedList라고 한다.

자바는 그중 doubleLinkedList로 LinkedList를 구현하였고, 처음과 끝을 모두 바로 접근할 수 있어서 Stack과 Queue 양쪽에 적합하다고 한다.