[기술면접] 스택과 큐, 선택 정렬, 배열과 리스트

스택과 큐의 차이점

Stack
Stack은 후입선출(LIFO: Last In First Out)의 자료구조를 구현한 클래스로 나중에 넣은 객체가 먼저 빠져나가는 구조이다.

• 주요 메소드
  • push() : 주어진 객체를 스택에 넣는다.
  • peek() : 스택의 맨 위 객체를 반환하고, 객체를 스택에서 제거 X
  • pop() : 스택의 맨 위 객체를 반환하고, 객체를 스택에서 제거 O
  • empty() : 스택이 비었다면 true 반환, 그렇지 않다면 false를 반환
  • search() : 해당 스택에서 전달된 객체가 존재하는 위치의 인덱스 반환
    

// 스택 객체 생성
Stack<E> stack = new Stack<E>();

Queue
Queue는 선입선출(FIFO : First In First Out)의 자료구조를 구현한 인터페이스로 먼저 넣은 객체가 먼저 빠져나가는 구조이다.

• 주요 메소드
  • offer() : 주어진 객체를 넣는다.
  • peek() : 객체를 하나 반환하고, 객체를 큐에서 제거 X
  • poll() : 객체를 하나 반환하고, 객체를 큐에서 제거 O
  • remove() : 해당 큐의 맨 앞에 있는 요소를 제거
  • add() : 해당 큐의 맨 뒤에 전달된 요소 저장 후 저장이 성공하면 true 반환, 실패하면 IllegalStateException 발생
  • element() : 해당 큐의 맨 앞에 있는 요소 반환

Queue 인터페이스는 큐 메모리 구조를 표현하기 위해, Collection 인터페이스의 메소드만을 상속받아 사용한다.

Queue<E> queue = new LinkedList<E>();

---

선택 정렬

¹

선택 정렬은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.

1. 주어진 리스트 중에 최소값을 찾음
2. 그 값을 맨 앞에 위치한 값과 교체
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체
   

비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 (n²) 만큼의 시간이 걸린다. 선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다.

---

배열과 리스트의 정의와 차이점

배열(Array)
배열은 같은 타입의 데이터를 연속된 공간에 나열시키고, 각 데이터에 인덱스(index)를 부여해 놓은 자료구조이다. 만약 다른 타입의 값을 저장하려고 하면 타입 불일치(Type mismatch) 컴파일 오류가 발생한다. 그리고 한 번 생성된 배열은 길이를 늘리거나 줄이거나 할 수 없다.

리스트(List)
List는 객체를 일렬로 늘어놓은 구조를 가진다. 객체를 인덱스로 관리하기 때문에 객체를 저장하면 자동 인덱스가 부여되고 인덱스로 객체를 검색, 삭제할 수 있는 기능을 제공한다. List는 객체의 번지를 참조한다. null도 저장이 가능하며, 이 경우에는 해당 인덱스는 객체를 참조하지 않음을 의미한다.

차이점
배열은 배열의 길이를 변경할 수 없지만 리스트는 길이를 변경할 수 있으며 제네릭을 사용할 수 있다. 또한 배열은 다차원 배열을 생성할 수 있지만 리스트는 다차원 배열을 사용할 수 없다. 속도적인 측면에서는 배열은 초기화 시 메모리에 할당되어 속도가 빠르며, List는 추가 시 메모리를 재할당하기 때문에 속도가 느리다.

참고

• 위키백과
• TCP School

1. 출처 - 위키백과 ↩