[Algorithms] Stack, Deque, ArrayList, LinkedList
[Algorithms] Stack, Deque, ArrayList, LinkedList
안녕하세요. 정리하는 개발자 워니즈입니다. 이번시간에는 알고리즘을 공부하면서, 필수적으로 알아야될 내용인 자료 구조에 대해서 정리를 해보고자 합니다.
단순한 자바프로그램에서는 데이터를 관리하고 효율적으로 사용하기 위해서는 자료구조를 잡고, 그 공간을 활용해야 합니다. 크게는 List, Set, Map으로 구분을 할 수 있습니다.
크게는 순서나, 집합을 표현하는 Collection과 키, 밸류 쌍으로 표현이 가능한 Map의 자료구조가 있습니다. 위의 그림에서는 표현이 되지 않았지만, Queue라는 자료구조형도 Collection Framework에 포함이 됩니다.
따라서, 자바의 자료구조는 다음과 같이 크게 4개로 나뉩니다.
- List
- Set
- Queue
- Map
1. Interface 소개
1-1. Collection
Collection 인터페이스는 java.util 패키지에 선언이 되어 있습니다. 여러개의 객체를 하나의 객체에 담아 처리할 때 공통으로 사용되는 여러 메소드들을 선언해 놓습니다.
1-2. List
List 인터페이스를 구현한 자료구조에는 ArrayList, Vector, Queue 클래스가 있습니다. 다른클래스도 있지만 제일 많이 사용되는 클래슨는 3가지 입니다.
필자가 알고리즘 문제를 풀이할 때, Vector를 사용했습니다. Vector와 ArrayList의 차이점을 인지하지 못한 상태에서 사용을 하였습니다. Vector같은 경우는 자원에 대한 동기화 처리를 하고, ArrayList같은 경우는 동기화 처리를 하지 않습니다.
위의 말의 의미는 멀티 쓰레드 환경에서 Vector를 사용하는것이 유리하고, 싱글 쓰레드 환경에서는 ArrayList를 사용하는 것이 유리합니다.
- ArrayList
- Vector
- LinkedList
1-3. Set
집합적인 개념의 Collection 입니다. 순서에 대한 의미가 전혀 없습니다. Data를 중복해서 저장하지 않습니다. 즉, 같은 데이터에 대해서는 한개의 데이터로 처리를 합니다.
- HashSet
- TreeSet
1-4. Map
자바에서 제공하는 HashMap과 Hashtable은 Map 인터페이스를 상속받아 구현되는 데이터를 키와 값으로 관리하는 자료 구조입니다.
키를 통해서 추출하려는 데이터를 검색하고, 이는 리스트 인터페이스와 같은 자료구조보다 탐색에 있어 더 높은 효율을 기대할 수 있습니다.
- HashMap
- Hashtable
1-5. Queue
자바에서 LinkedList 클래스를 이용하여 스택과 큐를 구현하는데에 자주 사용합니다. queue는 FIFO(First In, First out)방식을 채택하고 있습니다. 따라서, offer(); 메소드를 사용하여 Queue에 요소를 삽입하고 출력했을 땐, 들어간 순서대로 출력이 됩니다.
2. 관련 알고리즘 문제
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class stack_10828 {
private static int n;
private static String c;
private static int m;
private static Stack inteStack;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
inteStack = new Stack<>();
for (int i = 1; i <= n ; i++) {
st = new StringTokenizer(br.readLine());
c = st.nextToken();
//1. 커맨드 작성
if("push".equals(c)){
m = Integer.parseInt(st.nextToken());
inteStack.push(m);
}
else if("top".equals(c))
if (inteStack.size() > 0) {
System.out.println(inteStack.peek());
} else {
System.out.println(-1);
}
else if("size".equals(c)) System.out.println(inteStack.size());
else if("empty".equals(c))
if (inteStack.size() > 0) {
System.out.println(0);
} else {
System.out.println(1);
}
else if("pop".equals(c)){
if (inteStack.size() > 0) {
System.out.println(inteStack.pop());
} else {
System.out.println(-1);
}
}
}
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class queue_10845 {
private static int n;
private static String c;
private static int m;
private static Deque intergerDequeue;
private static Queue integerQueue;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
intergerDequeue = new LinkedList<>();
for (int i = 1; i <= n ; i++) {
st = new StringTokenizer(br.readLine());
c = st.nextToken();
//1. 커맨드 작성
if("push".equals(c)){
m = Integer.parseInt(st.nextToken());
intergerDequeue.add(m);
}
else if("front".equals(c)){
if (intergerDequeue.size() > 0) {
System.out.println(intergerDequeue.getFirst());
} else {
System.out.println(-1);
}
}
else if("back".equals(c)){
if (intergerDequeue.size() > 0) {
System.out.println(intergerDequeue.getLast());
} else {
System.out.println(-1);
}
}
else if("size".equals(c)) System.out.println(intergerDequeue.size());
else if("empty".equals(c))
if (intergerDequeue.size() > 0) {
System.out.println(0);
} else {
System.out.println(1);
}
else if("pop".equals(c)){
if (intergerDequeue.size() > 0) {
System.out.println(intergerDequeue.poll());
} else {
System.out.println(-1);
}
}
}
}
}
2번째 문제는 dequeue를 활용해서 문제를 해결했습니다. 양쪽에서 element를 넣고 빼고 하는 방식에 있어서 dequque를 사용할 수 있습니다.
3. 마치며…
알고리즘을 떠나서, 자바를 공부하면서 가장 중요한게 어떠한 자료구조를 사용하고, 어떻게 활용하느냐에 따라서 프로그램의 질이 달라진다고 생각합니다. 주니어 시절에는 Eclipse에서 다른사람의 코드를 보고 복사 붙여넣기해서 넣는 경우가 많았습니다. 하지만, 이제는 프로그래밍을 할 때, 활용도에 따라서(검색이 용이한지, 삽입 혹은 삭제가 용이한지) 적합한 알고리즘을 사용하는것이 중요하다고 생각하게 되었습니다.
다음시간에는 자료구조에 계속해서 이어서, Priority Queue에 대해서 정리를 해보도록 하겠습니다.
