네이버 클라우드 캠프 39일차 230620
#1 교육정리
1) Java Stack 구현하기
2) Java Queue 구현하기
#2 Java Stack 구현하기
스택은 제한적으로 접근할 수 있는 나열된 구조입니다. 후입선출(LIFO: Last In First Out)의 자료구조이며, 접근이 목록의 끝(Top 또는 Top Pointer)에서만 일어나기 때문에 Pushdown List 라고도 합니다. 스택에서 입력은 push, 출력은 pop, Top 위치의 데이터 확인은 peek 를 사용합니다.
스택은 추상자료형(Abstract Data Type)으로 수학적 모델을 가졌으며 구현 방법을 따로 명시하고 있지 않다는 점에서 자료구조와 차이를 보입니다. 이러한 특징은 다양한 방법으로 구현될 수 있음을 의미합니다.
- 운영체제(OS: Operating System)
프로그램에서 사용되는 함수들을 스택 자료형에 저장하여 사용합니다. - 컴파일러(Compiler)
수학 기호들을 기계어로 변환시 사용합니다. (괄호 등을 매칭하는 경우) - 자바 가상 머신(JVM: Java Virtual Machine)
JVM 내에서 메서드가 실행, 종료될 때 스택 프레임을 이용하여 관리합니다.
push 메소드 구현)
다음은 일반적으로 스택에 사용되는 필수적인 메서드들입니다.
- pop
스택의 가장 최상위(마지막)에 위치한 데이터를 추출한 후에 스택에서 삭제합니다.
java api : Removes the object at the top of this stack and returns that object as the value of this function.
- push
스택의 가장 최상위(마지막)에 데이터를 삽입합니다.
java api : Pushes an item onto the top of this stack.
- isEmpty
스택이 empty 상태인지 확인합니다.
java api : Tests if this stack is empty. - boolean
- clear
스택에 저장된 모든 데이터를 삭제하고 스택을 초기화합니다. - search(Object o)
java api : Returns the 1-based position where an object is on this stack. - int
- peek
스택의 가장 최상위(마지막)에 위치한 데이터를 추출합니다.
pop 메서드와는 달리 스택에서 데이터를 삭제하지 않습니다.
java api : Looks at the object at the top of this stack without removing it from the stack.
Stack의 push는 항상 최상단(맨 위)에 데이터를 추가해야하므로 한 종류밖에 없습니다. 리스트로 치면 add(E value)와 같은 역할입니다.
- 가장 마지막 부분(최상단)에 추가 - push(E item)
물론 현재 자바에 내장되어있는 Stack에서는 Vector을 상속받다보니 중간 삽입같은 특정 위치의 삽입도 가능합니다. 이는 가장 마지막에 다룰 ArrayList를 상속하여 구현하는 파트에서 볼 것이고, 지금은 Stack 자료구조 특징에 좀 더 집중하기 위해 push 단일 메소드만 구현 할 것입니다.
push의 경우 아까 위의 그림에서 보았듯 가장 마지막 위치에 데이터를 추가하는 것입니다. 그림으로 다시 보자면 아래와 같습니다.
코드로 구현)
- Stack 클래스 사용법
// Stack 클래스 사용법
package com.eomcs.basic.ex05;
import java.util.Stack;
public class Exam0110 {
public static void main(String[] args) {
Stack<String> stack = new Stack<>();
// push() - 스택의 맨 마지막에 값을 추가한다.
stack.push("aaa");
stack.push("bbb");
stack.push("ccc");
//stack.push(new Date()); // 타입 파라미터에 전달한 타입과 일치하지 않으면 오류!
// pop() - 스택의 맨 마지막에 입력된 값부터 꺼낸다.
// => 그래서 스택은 LIFO(Last In First Out) 방식으로 데이터를 다룬다.
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
// 값이 없는데 꺼내려 하면 EmptyStackException 예외가 발생한다.
System.out.println(stack.pop());
}
}
- empty() 사용법
// Stack 클래스 사용법 - empty()
package com.eomcs.basic.ex05;
import java.util.Stack;
public class Exam0120 {
public static void main(String[] args) {
Stack<String> stack = new Stack<>();
// push() - 스택의 맨 마지막에 값을 추가한다.
stack.push("aaa");
stack.push("bbb");
stack.push("ccc");
while (!stack.empty()) {
System.out.println(stack.pop());
}
}
}
ccc
bbb
aaa
- empty() 사용법2
또 다른 방법으로는 아래와 같습니다.
empty() 메소드는 단어 그대로 Stack이 비어있는지, 즉 요소가 한 개도 남아있지 않은지를 true 또는 false로 반환해주는 메소드 입니다. 만약 요소가 하나도 없다면 true, 하나라도 존재한다면 true가 됩니다.
그렇다고 모든 요소들을 하나씩 검사해줄 필요는 없습니다. size 변수가 0이면 데이터가 없다는 뜻이므로 size 값에 따라 반환만 다르게 해주면 됩니다.
@override
public boolean empty() {
return size == 0;
- peek() 사용법
// Stack 클래스 사용법 - peek()
package com.eomcs.basic.ex05;
import java.util.Stack;
public class Exam0130 {
public static void main(String[] args) {
Stack<String> stack = new Stack<>();
// push() - 스택의 맨 마지막에 값을 추가한다.
stack.push("aaa");
stack.push("bbb");
stack.push("ccc");
// peek() - 맨 위의 값을 꺼낸다. 단 pop()과는 달리 제거하지 않는다.
// pop() 메소드에서 삭제과정만 없는 것이 peek() 이다.
System.out.println(stack.peek());
System.out.println(stack.peek());
System.out.println(stack.peek());
}
}
ccc
ccc
ccc
- search() 사용법
// Stack 클래스 사용법 - search()
package com.eomcs.basic.ex05;
import java.util.Stack;
public class Exam0140 {
public static void main(String[] args) {
Stack<String> stack = new Stack<>();
// push() - 스택의 맨 마지막에 값을 추가한다.
stack.push("aaa");
stack.push("bbb");
stack.push("ccc");
// search() - 스택의 맨 위에서부터 해당 값을 찾는다. 위치는 맨 위가 1이다.
System.out.println(stack.search(new String("ccc"))); // 1
System.out.println(stack.search(new String("bbb"))); // 2
System.out.println(stack.search(new String("aaa"))); // 3
System.out.println(stack.search(new String("xxx"))); // -1
}
}
- size() 활용법
// Stack 클래스 사용법 - size()
package com.eomcs.basic.ex05;
import java.util.Stack;
public class Exam0150 {
public static void main(String[] args) {
Stack<String> stack = new Stack<>();
// push() - 스택의 맨 마지막에 값을 추가한다.
stack.push("aaa");
stack.push("bbb");
stack.push("ccc");
for (int i = 0; i < stack.size(); i++) {
System.out.println(stack.get(i));
}
}
}
aaa
bbb
ccc
- Iterator() 활용
// Stack 클래스 사용법 - Iterator 사용
package com.eomcs.basic.ex05;
import java.util.Iterator;
import java.util.Stack;
public class Exam0160 {
public static void main(String[] args) {
Stack<String> stack = new Stack<>();
// push() - 스택의 맨 마지막에 값을 추가한다.
stack.push("aaa");
stack.push("bbb");
stack.push("ccc");
// Iterator : ArrayList, HashSet과 같은 컬렉션을 반복하는 데 사용할 수 있는 객체다.
// iterator는 반복의 기술 용어기 때문에 반복자라고 한다
// 복자는 객체 지향적 프로그래밍에서 배열이나 그와 유사한 자료구조의 내부요소를 순회하는 객체다
Iterator<String> iterator = stack.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
}
aaa
bbb
ccc
- Iterator() 활용2
// Stack 클래스 사용법 - Iterator 사용
package com.eomcs.basic.ex05;
import java.util.Stack;
public class Exam0170 {
public static void main(String[] args) {
Stack<String> stack = new Stack<>();
// push() - 스택의 맨 마지막에 값을 추가한다.
stack.push("aaa");
stack.push("bbb");
stack.push("ccc");
// Stack도 Iterable 구현체이기 때문에
// 다음과 같이 for( : ) 문을 사용할 수 있다.
// => 내부적으로는 iterator()를 호출하여 Iterator를 얻는 후에
// 이 Iterator를 통해서 값을 꺼낸다.
// => 결국 Exam0160 과 같다.
// 즉 Exam0160 처럼 개발자가 직접 Iterator를 사용할 것인지,
// 아니면 다음과 같이 for(:) 문을 통해 간접적으로 처리할 것인지 선택하면 된다.
for (String s : stack) {
System.out.println(s);
}
}
}
aaa
bbb
ccc
- Stack 과 Deque()
// 스택과 Deque
package com.eomcs.basic.ex05;
import java.util.ArrayDeque;
public class Exam0210 {
public static void main(String[] args) {
// Deque 인터페이스
// - "Double ended queue"의 약자이다.
// 즉 앞, 뒤 모두 양방향에서 값을 넣고 꺼낼 수 있다.
// - 그래서 큐로도 사용할 수 있고 스택으로도 사용할 수 있다.
// - 큐, 스택 둘 다 사용할 수 있도록 queue와 stack 사용법을 모두 정의한 인터페이스다.
// 다음은 Dequeue 구현체 중의 하나이다.
ArrayDeque<String> stack = new ArrayDeque<>();
// 다음과 같이 스택으로서 사용할 수 있다.
stack.push("aaa");
stack.push("bbb");
stack.push("ccc");
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
}
}
ccc
bbb
aaa
- Stack의 Iterator와 Deque의 Iterator 차이점
// Stack의 Iterator와 Deque의 Iterator 차이점
package com.eomcs.basic.ex05;
import java.util.ArrayDeque;
import java.util.Iterator;
public class Exam0220 {
public static void main(String[] args) {
ArrayDeque<String> stack = new ArrayDeque<>();
stack.push("aaa");
stack.push("bbb");
stack.push("ccc");
// Stack 클래스와는 다르게
// Deque 구현체의 Iterator는 스택 방식(LIFO)으로 데이터를 꺼낸다.
// 결론!
// - Iterator 를 통해 데이터를 꺼낼 때 스택의 특성을 그대로 유지하고 싶다면,
// Stack 클래스 대신 ArrayDeque 클래스를 사용하라!
Iterator<String> iterator = stack.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
// 여기서 잠깐!
// Iterator 설계 기법의 목적
// - 데이터 조회 방식(LIFO, FIFO)에 상관없이
// 일관된 방법으로 데이터를 조회할 수 있게 도와준다.
// - 즉 스택처럼 입력 역순으로 꺼내든,
// 큐처럼 입력 순으로 꺼내든 상관없이
// 개발자는 hasNext(), next() 라는 동일한 메서드를 사용하여 데이터를 조회한다.
}
}
ccc
bbb
aaa
- Deque의 Iterator 와 for(:) 문
// Deque의 Iterator 와 for(:) 문
package com.eomcs.basic.ex05;
import java.util.ArrayDeque;
public class Exam0230 {
public static void main(String[] args) {
ArrayDeque<String> stack = new ArrayDeque<>();
stack.push("aaa");
stack.push("bbb");
stack.push("ccc");
// Iterator 를 통해 데이터를 조회하고 싶다면,
// 다음과 같이 for(:) 문을 사용하는 것이 더 낫다.
for (String s : stack) {
System.out.println(s);
}
}
}
ccc
bbb
aaa
#3 Java Queue 구현하기
Queue 구현에 앞서 먼저 자바 컬렉션 프레임워크에 대해서 학습하고나서 Queue에 대해서 정리해보겠습니다.
자바 컬렉션 프레임워크)
건물을 지으려면 구조를 잘 잡아야 하듯이 프로그램을 개발할 때도 사용하는 자료를 어떤 구조로 관리할 것인지가 중요합니다. 그래야 프로그램의 기능을 효과적으로 구현할 수 있기 때문입니다. 이 때 사용하는 것이 자료구조(data structure) 입니다.
자료구조는 프로그램 실행 중 메모리에 자료를 유지, 관리하기 위해 사용합니다. 자바에서는 자료 구조를 미리 구현하여 java.util 패키지에서 제공하고 있는데 이를 컬렉션 프레임워크(collection framework)라고 합니다.
자료구조는 개발자가 필요할 때 직접 만들어 사용할 수도 있습니다. 하지만 자바 컬렉션 프레임워크를 사용하면 직접 개발하는 수고를 덜 수 있을 뿐만 아니라 잘 만들어진 자료 구조 클래스를 활용할 수 있습니다.
자바 컬렉션 프레임워크에는 여러 인터페이스가 정의되어 있고, 그 인터페이스를 구현한 클래스가 있습니다. 각 인터페이스의 특성과 클래스 활용법을 알면 개발 목적에 맞게 잘 활용 할 수 있습니다.
컬렉션 프레임워크의 전체 구조는 Collection 인터페이스와 Map 인터페이스 기반으로 이루어져 있습니다.
- Collection 인터페이스
점선은 구현 관계이고, 실선은 확장 관계다. (인터페이스끼리는 다중 상속이 가능하다) 또한 Collection을 구현한 클래스 및 인터페이스들은 모두 java.util 패키지에 있다.
Vector나 Hashtable과 같은 컬렉션 클래스는 예전부터 사용해 왔으므로, 기존 코드와의 호환을 위해 아직도 남아 있습니다.
하지만 기존에 사용하던 컬렉션 클래스를 사용하는 것보다는 새로 추가된 ArrayList나 HashMap 클래스를 사용하는 것이 성능 면에서도 더 나은 결과를 얻을 수 있습니다.
- Map 인터페이스
검정색은 인터페이스, 파랑색은 클래스, 실선 화살표는 상속, 점선 화살표는 구현을 의미한다.
Map 인터페이스는 Collection 인터페이스와는 다른 저장 방식을 가집니다.
Map 인터페이스를 구현한 Map 컬렉션 클래스들은 키와 값을 하나의 쌍으로 저장하는 방식(key-value 방식)을 사용합니다.
여기서 키(key)란 실질적인 값(value)을 찾기 위한 이름의 역할을 합니다.
Map 인터페이스를 구현한 모든 Map 컬렉션 클래스는 다음과 같은 특징을 가집니다.
1. 요소의 저장 순서를 유지하지 않습니다.
2. 키는 중복을 허용하지 않지만, 값의 중복은 허용합니다.
대표적인 Map 컬렉션 클래스에 속하는 클래스는 다음과 같습니다.
1. HashMap<K, V>
2. Hashtable<K, V>
3. TreeMap<K, V>
Queue)
큐 메모리 구조는 선형 메모리 공간에 데이터를 저장하면서 선입선출(FIFO : first-in-first-out)의 시멘틱을 따르는 자료 구조입니다.
- Queue 주요 메서드
- resize()는 크기를 늘려주는 메소드입니다.
- 일반 Queue도 동적할당이기 때문에 여기서도 동적할당을 구현하기 위해서 크기가 64를 넘었을 때, 크기를 2배 더 늘려주는 메소드입니다.
- offer()는 원소를 넣어주는 메소드입니다.
- array가 가득찼을 때, 크기를 늘려주기 위해서 resize(array.length * 2); 메소드를 실행시킵니다.
- 일반적인 경우에는 rear에 값을 넣어주고 size를 증가시켜줍니다.
- E poll()은 앞의 원소를 꺼내서 Queue에서 제거하는 메소드이다.
- 원소를 꺼내고 array의 front자리의 값을 null로 바꿔주고 size를 하나 줄입니다.
- remove()는 원소 하나를 제거합니다.
- 앞서 설명한 것과 같이 poll()과 차이점은 size가 0일 때, NoSuchElementException가 발생합니다.
- peek()은 가장 앞에 있는 원소를 확인합니다. 제거가 되지는 않습니다.
- size가 0일 때 null을 반환합니다.
- element()는 peek과 같이 가장 앞의 원소를 확인합니다.
- size가 0일 때는 NoSuchElementException가 발생합니다.
que는 추가, 제거, 꺼내보기의 메소드가 각각 2개씩 있다.
- add는 사이즈를 넘어설 경우, 예외로 오류가 발생하지만, offer는 false를 반환한다.
- remove는 삭제할 요소가 없으면 즉, isEmpty이면, NosuchElementException예외가 발생한다. 하지만, poll의 경우는 null을 반환한다.
- element도 remove와 마찬가지로 비었을 경우 NosuchElementException이 발생한다. 하지만, peek은 null을 반환한다.
- Queue 구현 코드
// Queue 구현과 사용
package com.eomcs.basic.ex06;
import java.util.concurrent.ArrayBlockingQueue;
public class Exam0110 {
public static void main(String[] args) {
String s1 = new String("aaa");
String s2 = new String("bbb");
String s3 = new String("ccc");
String s4 = new String("ddd");
String s5 = new String("eee");
ArrayBlockingQueue queue = new ArrayBlockingQueue(10);
queue.offer(s1); // aaa,
queue.offer(s2); // aaa, bbb,
queue.offer(s3); // aaa, bbb, ccc,
print(queue);
// Queue
// - FIFO(First In First Out) 방식으로 데이터를 꺼낸다.
//
System.out.println("==>" + queue.poll()); // bbb, ccc,
System.out.println("==>" + queue.poll()); // ccc,
print(queue);
queue.offer(s4); // ccc, ddd,
queue.offer(s5); // ccc, ddd, eee,
print(queue);
System.out.println("------------------------");
String value;
while ((value = (String) queue.poll()) != null) {
System.out.println(value);
}
}
static void print(ArrayBlockingQueue queue) {
Object[] arr = queue.toArray();
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + ", ");
}
System.out.println();
}
}
aaa, bbb, ccc,
==>aaa
==>bbb
ccc,
ccc, ddd, eee,
------------------------
ccc
ddd
eee
- Queue 구현과 사용 : for(:)
// Queue 구현과 사용 : for(:)
package com.eomcs.basic.ex06;
import java.util.concurrent.ArrayBlockingQueue;
public class Exam0120 {
public static void main(String[] args) {
String s1 = new String("aaa");
String s2 = new String("bbb");
String s3 = new String("ccc");
String s4 = new String("ddd");
String s5 = new String("eee");
ArrayBlockingQueue<String> queue = new ArrayBlockingQueue<String>(10);
queue.offer(s1); // aaa,
queue.offer(s2); // aaa, bbb,
queue.offer(s3); // aaa, bbb, ccc,
queue.offer(s4); // aaa, bbb, ccc, ddd,
queue.offer(s5); // aaa, bbb, ccc, ddd, eee,
for (String s : queue) {
System.out.println(s);
}
}
}
aaa
bbb
ccc
ddd
eee