Stack 두 개(First In First Out)로 Queue(Last In First Out) 구현하기

 

스택 두 개를 다음과 같은 용도로 분리하여 사용.

inStack : 데이터를 저장

outStack : 데이터를 꺼낼 때 임시 버퍼로 사용

 

[Queue.class]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
package algo_datastructure.stack.queuebystack;
 
import java.util.Stack;
 
class Queue <T> {
    
    private Stack<T> inStack;
    private Stack<T> outStack;
    
    public Queue(){
        inStack = new Stack<T>();
    }
    
    public boolean add(T input) {
        return inStack.add(input);
    }
    
    public T poll() {
        if(!inStack.isEmpty()) {
            outStack = new Stack<T>();
        }
        while(!inStack.isEmpty()) {
            outStack.add(inStack.pop());
        }
        T topItem = outStack.pop();
        while(!outStack.isEmpty()) {
            inStack.add(outStack.pop());
        }
        return topItem;
    }
    
    public T peek() {
        if(!inStack.isEmpty()) {
            outStack = new Stack<T>();
        }
        while(!inStack.isEmpty()) {
            outStack.add(inStack.pop());
        }
        T topItem = outStack.peek();
        while(!outStack.isEmpty()) {
            inStack.add(outStack.pop());
        }
        return topItem;
    }
    
    public boolean isEmpty() {
        return inStack.isEmpty();
    }
    
}
 
 cs

[poll() 메소드 설명]

1. 데이터 입력

add(1);

add(2);

add(3);

inStack
3
2
1

2. poll(); 호출

if(!inStack.isEmpty()) {
   outStack = new Stack();
}

inStack outStack
3  
2  
1  

while(!inStack.isEmpty()) {
   outStack.add(inStack.pop());
}

inStack outStack
  1
  2
  3

T topItem = outStack.pop();   //1

inStack outStack
   
  2
  3

while(!outStack.isEmpty()) {
   inStack.add(outStack.pop());
}

inStack outStack
   
3  
2  

 

[사용]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package algo_datastructure.stack.queuebystack;
 
public class Main {
 
    public static void main(String[] args) {
        
        Queue<Integer> q = new Queue<>();
        q.add(1);
        q.add(2);
        q.add(3);
        System.out.println("peek : "+q.peek());
        System.out.println("poll : "+q.poll());
        
        q.add(4);
        System.out.println("peek : "+q.peek());
        while(!q.isEmpty()) {
            System.out.println("poll : "+q.poll());
        }
        
    }
    
}
 
 cs

[실행결과]

peek : 1
poll : 1
peek : 2
poll : 2
poll : 3
poll : 4

기술면접에서 단골 문제라고 하길래, 이렇게 구현하면 되지 않을까 하고 구현해보았습니다..

반응형
저작자표시 비영리

'Computer Science > data structure' 카테고리의 다른 글

[Data Structure] Queue 큐, array로 구현하기 (java)  (0) 2020.01.05
[Data Structure] Stack 스택, array 로 구현하기 (java)  (0) 2020.01.05
[Data Structure] HashSet, LinkedHashSet, TreeSet  (0) 2019.12.22
[Data Structure] ArrayList, LinkedList, Vector  (0) 2019.12.20
[Data Structure] HashMap, HashTable, LinkedHashMap, TreeMap  (0) 2019.12.20

Queue

FIFO(First In First Out : 선입선출) 형태를 갖는 자료구조.

일상생활에서 Queue와 가장 밀접한 예로 줄을 서는 행위를 들 수 있다. 

보통 줄을 설 때 줄을 가장 먼저 선 사람이 가장 먼저 처리되므로 Queue와 같다.(Queue 라는 단어 자체가 줄을 서다 라는 뜻을 갖는 동사, 대기줄이라는 뜻을 갖는 명사 이다)

 

[java.util.Queue 의 기본적인 사용예]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
package algo_datastructure.queue.queuebyarray;
 
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class Main {
    public static void main(String[] args) {
        
        System.out.println("Queue---------");
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(1);
        q.add(2);
        System.out.println(q.peek());
        while(!q.isEmpty()) {
            System.out.print(q.poll() + " ");
        }
        
        System.out.println("\nPriorityQueue (default : ascending)---------");
        Queue<Integer> q2 = new PriorityQueue<Integer>();
        q2.add(1);
        q2.add(3);
        q2.add(2);
        System.out.println(q2.peek());
        while(!q2.isEmpty()) {
            System.out.print(q2.poll() + " ");
        }
        
        System.out.println("\nPriorityQueue (Descending)---------");
        Queue<Integer> q3 = new PriorityQueue<Integer>((o1, o2)->o2-o1);
        q3.add(1);
        q3.add(3);
        q3.add(2);
        System.out.println(q3.peek());
        while(!q3.isEmpty()) {
            System.out.print(q3.poll() + " ");
        }
    }
}
 
 cs

[실행결과]

Queue---------
1
1 2
PriorityQueue (default : ascending)---------
1
1 2 3
PriorityQueue (Descending)---------
3
3 2 1

Queue 는 입력된 순서대로 저장 및 출력되는(LinkedList 를 구현체로 사용) Queue 와

입력된 데이터들을 특정 기준에 의해 정렬된 상태로 저장 및 출력하는 PriorityQueue 가 있다.

위와 같이 PriorityQueue는 Comparator 인터페이스를 파라미터로 넘겨 정렬순서를 원하는대로 선택할 수 있다. (위 예제에선 람다로 처리)

Comparator 인터페이스를 넘겨주지 않을 경우, 오름차순 정렬(default)로 처리된다.

 

두가지 queue 모두 공통적으로 아래와 같은 메소드를 갖는다.

add() : queue 에 값을 넣는다. (값 넣기 실패시 exception 을 뱉는다)

offer() : add()와 같이 queue에 값을 넣는다. (값 넣기 실패시 false 를 리턴한다)

peek() : queue 내에서 가장 앞에 위치한 데이터를 꺼낸다.(데이터는 그대로 둔다)

poll() : queue 내에서 가장 앞에 위치한 데이터를 꺼낸다.(데이터를 꺼내고 지운다)

 

[Array로 구현한 Queue]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package algo_datastructure.queue.queuebyarray;
 
public class Queue {
    
    private int[] array = new int[100];
int lastIdx = 0;
    
    public void add(int input) {
        array[lastIdx] = input;
        lastIdx++;
    }
    
    public int peek() {
        return array[0];
    }
    
    public int poll() {
        int rs = array[0];
        
        for(int i=1; i<=lastIdx; i++) {
            array[i-1] = array[i];
        }
        lastIdx--;
        
        return rs;
    }
    
    public boolean isEmpty() {
        return lastIdx==0?true:false;
    }
}
 
 cs

[사용]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
package algo_datastructure.queue.queuebyarray;
 
public class Main {
    public static void main(String[] args) {
        
        Queue q = new Queue();
        q.add(1);
        q.add(2);
        q.add(3);
        System.out.println(q.peek());
        while(!q.isEmpty()) {
            System.out.print(q.poll() + " ");
        }
    }
}
 
 cs

 

반응형
저작자표시 비영리

'Computer Science > data structure' 카테고리의 다른 글

[Data Structure] Stack 두 개로 Queue 구현하기  (0) 2020.01.06
[Data Structure] Stack 스택, array 로 구현하기 (java)  (0) 2020.01.05
[Data Structure] HashSet, LinkedHashSet, TreeSet  (0) 2019.12.22
[Data Structure] ArrayList, LinkedList, Vector  (0) 2019.12.20
[Data Structure] HashMap, HashTable, LinkedHashMap, TreeMap  (0) 2019.12.20

Stack

LIFO (Last In First Out : 후입선출) 형태를 갖는 자료구조.

임시로 자료를 저장하고 꺼내서 사용하는 임시 버퍼와 같다.

java 메모리구조에서 new 연산자로 생성된 인스턴스 등이 Stack 으로 관리된다.

 

일상생활에서 Stack과 가장 밀접한 예로 장독대를 들 수 있다.

김치를 넣고 꺼낼 때 가장 나중에 넣은 김치를 가장 먼저 꺼내야 하는 구조이므로 Stack과 같다.

 

[java.util.Stack 의 기본적인 사용예]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package algo_datastructure.stack;
 
import java.util.Stack;
 
public class BasicUsageOfStack {
    public static void main(String[] args) {
 
        Stack<Integer> s = new Stack<>();
        s.add(1);
        s.add(2);
        s.add(3);
 
        System.out.println(s.peek());
 
        while(!s.isEmpty()) {
            System.out.println(s.pop());;
        }
        
    }
}
 
 cs

 

add로 stack에 값을 넣는다. (push와 같음)

peek으로 stack 내에서 가장 위에 위치한 데이터를 꺼낸다.(데이터는 그대로 둔다)

pop으로 stack 내에서 가장 위에 위치한 데이터를 꺼낸다.(데이터를 꺼내고 지운다)

 

 

[Array로 구현한 Stack]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
package algo_datastructure.stack.stackbyarray;
 
public class Stack {
    private int[] array = new int[100];
    private int lastIdx = 0;
    
    public Stack () {
    }
    
    public void add(int input) {
        array[lastIdx] = input;
        lastIdx++;
    }
    
    public int pop() {
        lastIdx--;
        int top = array[lastIdx];
        array[lastIdx] = 0;
        
        return top;
    }
    
    public int peek() {
        return array[lastIdx-1];
    }
    
    public boolean isEmpty() {
        return lastIdx==0?true:false;
    }
}
 
 cs

[사용]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
package algo_datastructure.stack.stackbyarray;
 
public class Main {
    public static void main(String[] args) {
        Stack s = new Stack();
        s.add(1);
        s.add(2);
        s.add(3);
        System.out.println(s.peek());
        while(!s.isEmpty()) {
            System.out.println(s.pop());
        }
    }
}
 
 cs

 

 

반응형
저작자표시 비영리

'Computer Science > data structure' 카테고리의 다른 글

[Data Structure] Stack 두 개로 Queue 구현하기  (0) 2020.01.06
[Data Structure] Queue 큐, array로 구현하기 (java)  (0) 2020.01.05
[Data Structure] HashSet, LinkedHashSet, TreeSet  (0) 2019.12.22
[Data Structure] ArrayList, LinkedList, Vector  (0) 2019.12.20
[Data Structure] HashMap, HashTable, LinkedHashMap, TreeMap  (0) 2019.12.20

[Set]

중복을 허용하지 않는 자료구조로, 모든 데이터가 Unique 하다.

Set Interface 를 구현하는 HashSet, LinkedHashSet, TreeSet 은 위와 같은 성질을 따른다.

 

[HashSet]

내부적으로 HashMap 을 사용

순서 보장 X

null 입력은 가능하나 null도 한 번만 저장 가능하며 중복될 수 없다

 

[LinkedHashSet]

내부적으로 LinkedHashMap을 사용

순서 보장 O (입력한 순서)

null 입력은 가능하나 null도 한 번만 저장 가능하며 중복될 수 없다

 

[TreeSet]

내부적으로 TreeMap을 사용

인자값으로 받은 Comparator 를 기준으로 정렬, 인자값이 없는 경우 오름차순 정렬

null 입력 불가

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
Set<Integer> set = new HashSet<>();
set.add(null);
set.add(null); //중복허용X
set.add(3);
set.add(2);
set.add(1);
set.add(1);    //중복허용X
 
System.out.print("HashSet: ");
 
Iterator<Integer> si = set.iterator();
while(si.hasNext()) {
    System.out.print(si.next()+" ");
}
System.out.println();
 
 
Set<Integer> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add(3);
linkedHashSet.add(2);
linkedHashSet.add(1);
linkedHashSet.add(1); //중복허용 X
 
System.out.print("linkedHashSet: ");
for(int i : linkedHashSet) {
    System.out.print(i+" ");
}
System.out.println();
 
 
Set<Integer> treeSet = new TreeSet<>();
treeSet.add(3);
treeSet.add(2);
treeSet.add(1);
treeSet.add(1); //중복허용X
 
System.out.print("TreeSet: ");
for(int i : treeSet) {
    System.out.print(i+" ");
}
System.out.println();
 
 
Set<Integer> treeSetDescending = new TreeSet<>(new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        //내림차순
        return o2-o1;
    }
});
 
System.out.print("TreeSetDescending: ");
try {
    treeSetDescending.add(null);    //null 허용 X
}catch(NullPointerException ne) {
    System.out.println("exception:"+ne.getMessage());
}
treeSetDescending.add(3);
treeSetDescending.add(2);
treeSetDescending.add(1);
treeSetDescending.add(1); //중복허용X
 
for(int i : treeSetDescending) {
    System.out.print(i+" ");
}
 cs

 

[실행 결과]

HashSet: 1 2 3
linkedHashSet: 3 2 1
TreeSet: 1 2 3
TreeSetDescending: 3 2 1

 

[시간복잡도]

HashSet 이 LinkedHashSet, TreeSet보다 성능이 좋으며 메모리를 적게 사용.

   HashSet LinkedHashSet TreeSet
performance Θ(1) Θ(1) Θ(log(n))

 

참고 :

https://javaconceptoftheday.com/hashset-vs-linkedhashset-vs-treeset-in-java/

 

반응형
저작자표시 비영리

'Computer Science > data structure' 카테고리의 다른 글

[Data Structure] Queue 큐, array로 구현하기 (java)  (0) 2020.01.05
[Data Structure] Stack 스택, array 로 구현하기 (java)  (0) 2020.01.05
[Data Structure] ArrayList, LinkedList, Vector  (0) 2019.12.20
[Data Structure] HashMap, HashTable, LinkedHashMap, TreeMap  (0) 2019.12.20
트리 순회  (0) 2019.11.26

[List]

순서가 있는 데이터의 집합, 데이터 중복을 허용

List Interface 를 구현하는 ArrayList, LinkedList, Vector 는 모두 위 성질을 따름

 

[사용법]

ArrayList, LinkedList, Vector 모두 사용법이 동일하다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
List<Integer> al = new ArrayList<>();
al.add(1);
al.add(2);
al.add(2);    //중복허용, 순서보장
//al.remove(0);
 
System.out.print("ArrayList: ");
for(int i:al) {
    System.out.print(i+" ");
}
System.out.println();
 
List<Integer> ll = new LinkedList<>();
ll.add(1);
ll.add(2);
ll.add(2);    //중복허용, 순서보장
//ll.remove(0);
 
System.out.print("LinkedList: ");
for(int i:ll) {
    System.out.print(i+" ");
}
System.out.println();
 
List<Integer> v = new Vector<>();
v.add(1);
v.add(2);
v.add(2);    //중복허용, 순서보장
//v.remove(0);
 
System.out.print("Vector: ");
for(int i:v) {
    System.out.print(i+" ");
}
 cs

[실행 결과]

ArrayList: 1 2 2
LinkedList: 1 2 2
Vector: 1 2 2

 

[차이점]

ArrayList

배열과 동일하나 저장되는 자료크기에 따라 내부적으로 배열의 크기가 늘었다 줄었다 하는 resizable array.

조회 수행속도가 빠르다.

데이터 삽입이 발생하면 삽입된 데이터 뒤에 위치하는 모든 데이터의 인덱스를 하나씩 증가시킨다(한 칸씩 민다)

데이터 삭제가 발생하면 삭제된 데이터 뒤에 위치하는 모든 데이터의 인덱스를 하나씩 감소시킨다(한 칸씩 당긴다).

 

LinkedList

자료의 주소값을 기준으로 데이터들이 연결된 형태.

삽입과 삭제의 수행속도가 빠르다.

데이터 삽입이 발생하면 삽입될 데이터 앞의 데이터는 삽입될 데이터의 주소값을,

삽입될 데이터는 삽입될 데이터 뒤에 위치한 데이터의 주소값을 참조하게 한다.

 

Vector

Thread Safe 한 ArrayList (Synchronized)

 

[ArrayList vs LinkedList 성능 비교]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
private static long START_TIME = 0;
    private static long END_TIME = 0;
    
    public static void main(String[] args) {
        
        List<Integer> ArrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();
        
        setStartTime();
        for(int i=0; i<10000; i++) {
            ArrayList.add(0);
        }
        setEndTime();
        System.out.print("ArrayList add: ");
        printDuration();
 
        
        setStartTime();
        for(int i=0; i<10000; i++) {
            linkedList.add(0);
        }
        setEndTime();
        System.out.print("LinkedList add: ");
        printDuration();
        
        System.out.println("-------------------------------------------------");
        
        setStartTime();
        for(int i=0; i<10000; i++) {
            ArrayList.get(i);
        }
        setEndTime();
        System.out.print("ArrayList get: ");
        printDuration();
        
        
        setStartTime();
        for(int i=0; i<10000; i++) {
            linkedList.get(i);
        }
        setEndTime();
        System.out.print("LinkedList get: ");
        printDuration();
        
        System.out.println("-------------------------------------------------");
        
        setStartTime();
        Iterator<Integer> ai = ArrayList.iterator();
        while(ai.hasNext()) {
            ArrayList.remove(0);
        }
        setEndTime();
        System.out.print("ArrayList remove: ");
        printDuration();
        
        
        setStartTime();
        Iterator<Integer> li = linkedList.iterator();
        while(li.hasNext()) {
            linkedList.remove(0);
        }
        setEndTime();
        System.out.print("LinkedList remove: ");
        printDuration();
        
    }
    
    private static void setStartTime() {
        START_TIME = System.nanoTime();
    }
    
    private static void setEndTime() {
        END_TIME = System.nanoTime();
    }
    
    private static void printDuration() {
        System.out.println(END_TIME - START_TIME);
    }
 cs

[실행 결과]

ArrayList add: 1049700
LinkedList add: 1224800
-------------------------------------------------
ArrayList get: 861200
LinkedList get: 42666800
-------------------------------------------------
ArrayList remove: 6322100
LinkedList remove: 1229300

 

조회(get)는 ArrayList가 상대적으로 뛰어난 성능을 보여준다.

삽입(add)/삭제(remove)는 LinkedList가 상대적으로 뛰어난 성능을 보여준다.

[ArrayList vs LinkedList 시간복잡도]

   ArrayList LinkedList
Indexing Θ(1) Θ(n)
Insert/delete at beginning Θ(n) Θ(1)
Insert/delete at end Θ(1) Θ(n)-last element is unknown
Θ(1)-last element is known
Insert/delete in middle Θ(n) search time + Θ(1)
Wasted space (average) Θ(n) Θ(n)

 

 

참고 :

https://dzone.com/articles/arraylist-vs-linkedlist-vs

http://www.nextree.co.kr/p6506/

반응형
저작자표시 비영리

'Computer Science > data structure' 카테고리의 다른 글

[Data Structure] Queue 큐, array로 구현하기 (java)  (0) 2020.01.05
[Data Structure] Stack 스택, array 로 구현하기 (java)  (0) 2020.01.05
[Data Structure] HashSet, LinkedHashSet, TreeSet  (0) 2019.12.22
[Data Structure] HashMap, HashTable, LinkedHashMap, TreeMap  (0) 2019.12.20
트리 순회  (0) 2019.11.26

Map은 키와 값이 한 쌍으로 이루어지는 데이터의 집합

값은 중복을 허용하나 키는 중복될 수 없음(키는 중복될 경우 덮어 씀)

Map Interface 를 구현한 HashMap, HashTable, LinkedHashMap, TreeMap 은 모두 위 규칙을 따름.

 

 

[HashMap]

순서가 보장되지 않는다.

Null을 허용한다.

Thread Safe 하지 않다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//순서를 보장하지 않음
//key, value 에 Null 허용
//Thread safe X
 
Map<Integer, Integer> map = new HashMap<>();
 
map.put(1, 180);
map.put(3, 175);
map.put(2, 160);
map.put(4, 190);
map.put(3, 170);
 
try {
    map.put(0, null);
} catch(NullPointerException ne) {
    System.out.println(ne.getMessage());
}
 
for(int s : map.keySet()) {
    System.out.println("person : " + s + ", height : " + map.get(s));
}
 cs

[실행결과]

person : 0, height : null
person : 4, height : 190
person : 3, height : 170
person : 2, height : 160
person : 1, height : 180

1, 3, 2, 4, 3, 0 의 Key 를 순서대로 입력하였지만 순서는 지켜지지 않았다.

(혹여 정렬된 것 처럼 값이 출력된다 해도 정렬이 되어 나온게 아니다)

14번 라인에 null 값을 넣어봤지만 exception 이 찍히지 않았다 : null 허용

 

 

[HashTable]

순서가 보장되지 않는다

Null을 허용하지 않는다

Thread Safe 하다

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//순서를 보장하지 않음
//key, value 에 Null 허용
//Thread safe
 
Map<Integer, Integer> map = new Hashtable<>();
 
map.put(1, 180);
map.put(3, 175);
map.put(2, 160);
map.put(4, 190);
map.put(3, 170);
 
try {
    map.put(0, null);
} catch(NullPointerException ne) {
    System.out.println(ne.getMessage());
}
 
for(int s : map.keySet()) {
    System.out.println("person : " + s + ", height : " + map.get(s));
}
 cs

[실행결과]

null
person : 4, height : 190
person : 3, height : 170
person : 2, height : 160
person : 1, height : 180

HashMap 과 마찬가지로 순서가 보장되지 않았다.

14번라인에서 NullPointerException 이 발생하여 null 이라는 에러메시지를 찍고 있다.

 

 

[LinkedHashMap]

입력한 순서가 보장된다

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//입력한 순서가 보장됨
//Thread safe X
 
Map<Integer, Integer> map = new LinkedHashMap<>();
 
map.put(1, 180);
map.put(3, 175);
map.put(2, 160);
map.put(4, 190);
map.put(3, 170);
 
for(int s : map.keySet()) {
    System.out.println("person : " + s + ", height : " + map.get(s));
}
 cs

[실행결과]

person : 1, height : 180
person : 3, height : 170
person : 2, height : 160
person : 4, height : 190

put 을 한 순서(1, 3, 2, 4)대로 결과가 출력되었다.

 

 

[TreeMap]

데이터가 내부적으로 정렬되어 존재한다. (RedBlackTree 구조)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//KEY를 기준으로 정렬함(내부적으로 RedBlackTree 구조로 정렬)
//Thread safe X
 
Map<Integer, Integer> map = new TreeMap<>();
 
map.put(1, 180);
map.put(3, 175);
map.put(2, 160);
map.put(4, 190);
map.put(3, 170);
 
for(int s : map.keySet()) {
    System.out.println("person : " + s + ", height : " + map.get(s));
}
 
 cs

[실행 결과]

person : 1, height : 180
person : 2, height : 160
person : 3, height : 170
person : 4, height : 190

오름차순 기준으로 key값을 정렬하여 출력되었다.

 

 

※ 정렬 순서를 바꾸고 싶다면?

Comparator 를 인자값으로 넘겨준다. Comparator 에 대한 설명은 이곳을 참고

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Map<Integer, Integer> map2 = new TreeMap<>(new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
}); 
 
map2.put(1, 180);
map2.put(3, 175);
map2.put(2, 160);
map2.put(4, 190);
map2.put(3, 170);
 
for(int s : map2.keySet()) {
    System.out.println("person : " + s + ", height : " + map2.get(s));
}
 cs

[실행결과]

person : 4, height : 190
person : 3, height : 170
person : 2, height : 160
person : 1, height : 180

내림차순 기준으로 key값을 정렬하여 출력되었다.

 

반응형
저작자표시 비영리

'Computer Science > data structure' 카테고리의 다른 글

[Data Structure] Queue 큐, array로 구현하기 (java)  (0) 2020.01.05
[Data Structure] Stack 스택, array 로 구현하기 (java)  (0) 2020.01.05
[Data Structure] HashSet, LinkedHashSet, TreeSet  (0) 2019.12.22
[Data Structure] ArrayList, LinkedList, Vector  (0) 2019.12.20
트리 순회  (0) 2019.11.26

트리 구조에서 각각의 노드를 단 한 번만, 체계적인 방법으로 방문하는 과정

 

전위 순회(=깊이 우선 순회) : F, B, A, D, C, E, G, I, H (root, left, right)

중위 순회(=대칭 순회) : A, B, C, D, E, F, G, H, I (left, root, right)

후위 순회 : A, C, E, D, B, H, I, G, F (left, right, root)

레벨 순서 순회(=너비 우선 순회) : F, B, G, A, D, I, C, E, H

 

 

 

 

 

 

반응형
저작자표시 비영리

'Computer Science > data structure' 카테고리의 다른 글

[Data Structure] Queue 큐, array로 구현하기 (java)  (0) 2020.01.05
[Data Structure] Stack 스택, array 로 구현하기 (java)  (0) 2020.01.05
[Data Structure] HashSet, LinkedHashSet, TreeSet  (0) 2019.12.22
[Data Structure] ArrayList, LinkedList, Vector  (0) 2019.12.20
[Data Structure] HashMap, HashTable, LinkedHashMap, TreeMap  (0) 2019.12.20

+ Recent posts

티스토리툴바