스택, 큐에 대해 설명하시오(특징, 대표적인 예, 차이점)
스택 : 후입선출(LIFO), 함수 콜스택, 액티비티 기록, 연산자 후위표기, 문자열 역순 출력
큐 : 선입선출(FIFO), 운영체제 작업 관리, 안드로이드 메인 스레드, 컴퓨터 버퍼
공통점 : 데이터를 임시로 저장하거나 입출력 장치의 데이터를 일시적으로 저장할 때 사용
ArrayList와 LinkedList의 차이점을 설명하시오
ArrayList : 탐색 효율이 좋음 O(1), 삽입/삭제는 비효율 O(N)
LinkedList : 삽입/삭제 효율O(1), 탐색 비효율 O(N) 노드를 거쳐야 되기 때문에.
배열과 리스트 차이점 (접근속도(처리속도), 논리/물리적 저장 순서 등..)
접근속도 : 배열 > 리스트
논리/물리적 저장 순서 : 배열은 같음 / 리스트는 다름.
스택을 배열로 구현할 때 발생하는 단점은 무엇인가요?
할당한 배열 크기에 비해 데이터가 작은 경우 공간 낭비, 스택의 크기 변경이 비효율적
큐를 스택으로 구현하는 방법을 설명하시오
두 개의 스택을 사용하여, 출력하기 전 스택A의 데이터를 스택B에 옮긴 후 출력
배열과 ArrayList의 차이점을 설명하시오.
배열은 크기가 정해지지만 ArrayList는 동적으로 추가 할당이 가능함.
우선순위 큐에 대해 설명하시오.
FIFO가 아닌 데이터를 근거로 우선순위를 판단, 우선순위가 높은 것을 먼저 가져옴
구현방법(배열, 연결리스트, 힙)
단, 배열은 삽입/삭제시 비효율, 연결리스트는 탐색시 비효율로 인해 가장 효율적인 힙으로 구현이 일반적임.
큐 언더플로우에 대해 설명하시오.
큐가 비어있을 때 삭제를 하는 경우
배열과 연결리스트를 사용하는 경우 메모리 효율, 데이터 저장 위치 관련해서 설명하시오.
연결리스트가 메모리 효율 좋고, 배열은 연속적, 연결리스트는 중간 중간에 존재