부수 효과 (Side Effect), 참조 투명성 (Referential Transparency)

함수형 프로그래밍 (Functional Programming) 의 정의를 설명할 때, 중요하게 언급되는 2가지 개념을 설명하려고 한다. 바로 “부수 효과” 와 “참조 투명성” 이다.

먼저 “부수 효과” 는 함수 내의 실행으로 인해 함수 외부가 영향을 받는 것을 의미한다. 함수의 매개 변수의 값이 변경되어, 이로 인해 함수를 사용하는 코드에 영향을 주거나, 함수의 외부 세계인 데이터베이스, 파일 시스템, 네트워크로 데이터 이동이 함수 실행 중에는 발생하지 않아야 함수형 코드가 된다.

public static int add(int a, int b) {
  while (b > 0) {
    a++;
    b--;
  }
  return a;
}

위의 메쏘드는 함수적이다. 정수형 a, b 를 매개 변수로 받은 후, 그것들의 값을 변경하지 않고 결과를 반환한다. a, b 값을 변경한다고 해도 함수적이다. 왜냐하면 Java 에서는 원시 타입의 매개 변수는 pass by value 형태로 전달되기 때문에, 함수 내에서 값을 변경해도 함수를 벗어난 후에는 영향을 주지 않는다.

public static int div(int a, int b) {
  return a / b;
}

위의 함수는 함수적이지 않다. b의 값이 0인 경우 divide by zero 예외가 발생하는데, 예외를 발생시키는 것은 함수적이지 않다. 위의 코드는 아래와 같이 변경할 수 있다.

public static int div(int a, int b) {
  return (int) (a / (float) b);
}

b의 값이 0이어도 예외가 발생하지 않으며, 특별한 값이(2147483647) 반환된다. 이 값을 처리하는 것은 함수 사용자의 몫이다.

함수형 프로그래밍 (Functional Programming) 의 중요한 특징 중에서 2번째로 언급되는 것은 바로 “참조 투명성” 이다. “참조 투명성”은 함수 (또는 메쏘드) 가 함수 외부의 영향을 받지 않는 것을 의미한다. 다른 말로 하면, 함수의 결과는 입력 파라미터에만 의존하고, 함수의 외부 세계인 입력 콘솔, 파일, 원격 URL, 데이터베이스, 파일 시스템 등에서 데이터를 읽지 않는다. 함수 외부의 값을 변경하거나, 외부 세계의 의존적이지 않은 코드를 가리켜 “참조 투명성 있다” 라고 말한다.

참조 투명성을 가진 코드는 아래와 같은 특징들을 지닌다.

• 자기 충족적이다 (self-contained). 함수 외부에 의존하는 코드가 없고, 함수 사용자 입장에서는 유효한 매개변수만 전달하면 된다.
• 결정론적이다 (deterministic). 동일한 매개변수에 대해서는 항상 동일한 결과가 나온다.
• 예외 (Exception) 를 던지지 않는다. out of memory error 혹은 stack overflow error 는 발생할 수 있지만, 이러한 에러들은 버그로 취급되며, 함수의 사용자가 다룰 수 있는 것은 아니다.
• 다른 코드가 예기치 않게 실패하는 조건을 만들지 않는다. 예를 들어, 참조 투명성을 가진 함수는 매개 변수의 값을 변경하거나 함수 외부의 데이터를 변경하지 않는다.
• 데이터베이스, 파일 시스템, 네트워크 등의 외부 기기로 인해 동작이 멈추지 (hang) 않는다.

함수형 프로그래밍을 통해서 얻을 수 있는 이득은 아래와 같다.

• 함수형 프로그램은 결정론적이기 때문에, 원인을 찾기가 더 쉽다. 함수형 코드는 특정한 입력에 대해서 항상 동일한 결과를 반환한다. 많은 경우 프로그램을 광범위하게 테스트하는 대신 올바른 프로그램임을 증명할 수 있으며, 예기치 않은 상황에서 프로그램이 중단될지 여부를 여전히 확신하지 못할 수 있다.
• 함수형 프로그램은 테스트 하기가 쉽다. 부수 효과가 없기 때문에, mock 을 만들지 않아도 된다.
• 함수형 프로그램은 조립하기가 더 쉽다. 함수형 프로그램은 함수들의 조합으로 구성된다. 다루어야할 부수 효과가 없고, 예외가 없으며, 값의 변경이 일어나지 않는다. 동시성 문제도 발생하지 않는다.
• 함수형 프로그램은 구성, 재구성이 쉽다. 함수형 프로그램을 작성할 때, 기반이 되는 함수들을 먼저 작성한 후에, 상위 레벨에서 함수들을 조합한다. 원하는 함수를 가질 때까지 함수들을 조합한다. 모든 함수는 참조 투명하기 때문에, 다른 프로그램을 작성할 때도 코드의 변경없이 재사용하기가 쉽다.

위의 내용은 Functional Programming in Java: How functional techniques improve your Java programs 1st Edition 에서 발췌, 번역, 요약한 것입니다.

[Java] PriorityQueue

Java 에서 PriorityQueue(우선 순위 큐) 는 Heap 의 기능을 가진 Queue 이다.  기본적인 Queue 와 달리 Queue 에 값을 넣은 순서대로 처리되는 것이 아니라, 지정된 우선순위에 따라서 처리가 되는데, PriorityQue 에서는 기본으로 natural ordering(숫자의 오름 차순, 문자의 알파벳순 정렬 등) 을 기반으로 우선 순위가 지정된다.

예를 들어, 일반적인 Queue 에 아래의 순서대로 숫자 값을 넣고,

5 -> 3 -> 1 -> 2 -> 4

Queue 에서 값을 순서대로 꺼내면

5 -> 3 -> 2 -> 1 -> 4

이렇게 된다.

하지만, PriorityQueue 에 동일하게 값을 넣고 꺼내면,

1 -> 2 -> 3 -> 4 -> 5

와 같이 값이 정렬되어 나온다. 이것을 Min Heap 이라고 하는데 Queue 제일 처음(head)에 가장 장 작은 값이 위치한다. 아무런 정렬 방식을 정하지 않으면, 숫자의 경우에는 값을 넣을 때마다 오름 차순으로 PriorityQueue 내에서 정렬이 일어난다.

PriorityQueue 의 생성자 중에는 Comparator 인터페이스를 파라미터를 받는 것이 있는데, Comaprator 구현을 사용해서 정렬 방식을 바꿀 수 있다.

PriorptyQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

위의 코드는 숫자의 내림 차순으로 정렬한다. 즉 Max Heap 을 사용한다.

@Test
public void test() {
    // max heap
    PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
    pq.add(1);
    pq.add(3);
    pq.add(2);
    pq.add(4);

    assertEquals(4, (int)pq.poll());
    assertEquals(3, (int)pq.poll());
    assertEquals(2, (int)pq.poll());
    assertEquals(1, (int)pq.poll());
}

PriorityQueue를 활용한 알고리즘 문제

중앙값 (median) 찾기

주어진 일련의 숫자 배열에서 중앙값을 찾는 문제

입력) 10, 43, 56, 37, 19, 66, 74, 23, 41, 24

출력) (37 + 41) / 2 -> 39

힌트

Max Heap 과 Min Heap 을 각각 사용해서, 입력 값의 작은 쪽 절반은 Max Heap 에 넣고, 큰 쪽 절반은 Min Heap 에 넣는다. 그러면 Max Heap 의 제일 앞에는 작은 쪽 절반 값에서 가장 큰 값이 저장되고, Min Heap 의 제일 앞에서는 큰 쪽 절반 값 중에서 가장 작은 작은 값이 저장된다.

Max Heap:

37 -> 24 -> 23 -> 19 -> 10

Min Heap:

41 -> 43 -> 56 -> 66 -> 74

Answer

public class MedianFinder {
    private PriorityQueue<Integer> maxHeap;
    private PriorityQueue<Integer> minHeap;

    public MedianFinder() {
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        minHeap = new PriorityQueue<>();
    }

    public void addNumber(int num) {
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll());

        if(maxHeap.size() < minHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    public double findMedian() {
        if(maxHeap.size() == minHeap.size()) {
            return (double)((maxHeap.peek() + minHeap.peek()) / 2);
        }

        return maxHeap.peek();
    }
}

@Test
public void test() {
    // max heap
    PriorityQueue<Integer> pq = new PriorityQueue<>(10, (Integer a, Integer b) -> a <= b ? 1 : -1);
    pq.add(1);
    pq.add(3);
    pq.add(2);
    pq.add(4);

    assertEquals(4, (int)pq.poll());
    assertEquals(3, (int)pq.poll());
    assertEquals(2, (int)pq.poll());
    assertEquals(1, (int)pq.poll());
}

Find Median From Data Stream 참고

 

Spring Boot with Docker

최근에 Spring Boot 으로 만든  어플리케이션을 Docker 를 사용하여 배포를 할 일이 생겨서 Spring Boot with Docker 의 내용을 요약 정리해 봅니다.

1. Simple Spring Boot Application

Spring Boot을 사용하여 “Hello Docker World”를 출력하는 간단한 웹 어플리케이션을 다음과 같이 작성합니다.

@SpringBootApplication
@RestController
public class DockerApplication {

   @GetMapping
   public String home() {
      return "Hello Docker World";
   }

   public static void main(String[] args) {
      SpringApplication.run(DockerApplication.class, args);
   }
}

$ http localhost:8080

Hello Docker World

2. Dockerfile 작성

Docker 이미지를 생성하기 위해 Dockerfile을 작성합니다. 파일의 위치는 src/main/docker/Dockerfile 입니다.

FROM frolvlad/alpine-oraclejdk8:slim
VOLUME /tmp
ADD gs-spring-boot-docker-0.0.1-SNAPSHOT.jar app.jar
RUN sh -c 'touch /app.jar'
ENV JAVA_OPTS=""
ENTRYPOINT ["sh", "-c", "java $JAVA_OPTS -Djava.security.egd=file:/dev/./urandom -jar /app.jar"]

• FROM: jdk 를 컨테이너에 포함합니다.
• VOLUME: embedded tomcat 이 사용할 temp 디렉토리 입니다.
• ADD: artifact 이름을 버전과 함께 명시하고 app.jar 라는 이름으로 컨테이너에 포함합니다.
• RUN: app.jar 에 touch 명령을 실행시켜서 파일의 수정날짜를 변경합니다. 여기서는 큰 의미가 없지만, 파일의 수정 날짜가 요구되는 경우가 있습니다.
• ENV: Java의 실행 옵션을 지정합니다.
• ENTRYPOINT: Docker가 실행될 때 시작되는 명령입니다. 기본적으로  java -jar 과 다른 것이 없습니다. 시스템 환경 변수로 java.security.egd=file:/dev/./urandom 을 정의하고 있습니다. /dev/urandom 은 random number generator로 사용됩니다. tomcat의 startup 시간을 줄이는 효과가 있다고 합니다. 자세한 내용은 /dev/./urandom 을 참고하시기 바랍니다.

3. docker-maven-plugin 설정

docker-maven-plugin을 사용하여 Docker 이미지를 만들 수 있습니다.

<groupId>jade</groupId>
<artifactId>gs-spring-boot-docker</artifactId>
.....
<properties>
   <docker.image.prefix>jade</docker.image.prefix>
</properties>
......
<build>
.......
<plugins>
  <plugin>
   <groupId>com.spotify</groupId>
   <artifactId>docker-maven-plugin</artifactId>
   <version>0.4.14</version>
   <configuration>
      <imageName>${docker.image.prefix}/${project.artifactId}</imageName>
      <dockerDirectory>src/main/docker</dockerDirectory>
      <resources>
         <resource>
            <targetPath>/</targetPath>
            <directory>${project.build.directory}</directory>
            <include>${project.build.finalName}.jar</include>
         </resource>
      </resources>
   </configuration>
  </plugin>
 </plugins>
</build>

4. Docker Build & Run

4.1 Build

$ mvn package docker:build

다음과 같이 Maven이 빌드됩니다.

[INFO] --- docker-maven-plugin:0.4.14:build (default-cli) @ gs-spring-boot-docker ---
[INFO] Copying /Users/jadeim/Playground/gs-spring-boot-docker/target/gs-spring-boot-docker-0.0.1-SNAPSHOT.jar -> /Users/jadeim/Playground/gs-spring-boot-docker/target/docker/gs-spring-boot-docker-0.0.1-SNAPSHOT.jar
[INFO] Copying src/main/docker/Dockerfile -> /Users/jadeim/Playground/gs-spring-boot-docker/target/docker/Dockerfile
[INFO] Building image springio/gs-spring-boot-docker
Step 1/6 : FROM frolvlad/alpine-oraclejdk8:slim
---> 354831d86a05
Step 2/6 : VOLUME /tmp
---> Using cache
---> b209c9570887
Step 3/6 : ADD gs-spring-boot-docker-0.0.1-SNAPSHOT.jar app.jar
---> 143a9cb7b3a1
Removing intermediate container 40c57077703e
Step 4/6 : RUN sh -c 'touch /app.jar'
---> Running in f8789a71a32e
---> c9f46c427f78
Removing intermediate container f8789a71a32e
Step 5/6 : ENV JAVA_OPTS ""
---> Running in 4a9e5b610b76
---> fc0092b4459b
Removing intermediate container 4a9e5b610b76
Step 6/6 : ENTRYPOINT sh -c java $JAVA_OPTS -Djava.security.egd=file:/dev/./urandom -jar /app.jar
---> Running in db23115803ef
---> c80937db215d

4.2 Run

$ docker run -p 8080:8080 -t jade/gs-spring-boot-docker

이제 컨테이너로 어플리케이션 배포 및 실행이 되었습니다.
http://localhost:8080 을 실행하면 “Hello Docker World”가 출력됩니다.

@Autowired on a method

Spring Framework를 사용하면서 가장 많이 사용하는 어노테이션중에 하나인 @Autowired. @Autowired를 사용할 때, Field, Constructor, Setter  메쏘드에 많이 사용해왔습니다. 그런데 다음과 같은 코드를 보았습니다.

@Autowired
public void configGlobal(AuthenticationManagerBuilder auth) {
……..
}

보다시피 @Autowired가 선언된 곳은 Field, Constructor, Setter 메쏘드가 아닙니다. JavaDoc을 보니 다음과 같이 되어 있네요

Marks a constructor, field, setter method or config method as to be autowired by Spring’s dependency injection facilities.

@Autowired를 config method에 사용할 수 있습니다. 위의 코드에서 configureGlobal() 이라는 이름은 중요하지 않습니다. Spring Bean을 매개변수로 받는 모든 메쏘드에 사용할 수 있습니다. 그렇지만 대부분 매개 변수로 전달받은 Spring Bean의 설정에 사용된다고 볼 수 있습니다. 그리고 Setter 메쏘드는 단지 위의 특별한 경우라고 보면 됩니다.

[Java Generics] Bounded Wildcard

Java Generics 에서 가장 적용하기 까다로운 것이 바로 bounded wildcard 일 것입니다.

1. <? extednds T>
2. <? super T>

스택오버플로우에 아주 훌륭한 답변이 있어서 정리할 겸 번역을 해 봅니다. 원문은 http://stackoverflow.com/questions/4343202/difference-between-super-t-and-extends-t-in-java 입니다.

1. <? extends T> – upper bounded

List<? extends Number> 선언은 다음의 문장이 적합하다는 것을 의미합니다.

List<? extends Number> foo3 = new ArrayList<Number>();
List<? extends Number> foo3 = new ArrayList<Integer>();
List<? extends Number> foo3 = new ArrayList<Double>();

1.1 Reading

foo3로부터 값을 읽을 때, 우리는 그 값이 어떤 객체의 타입임을 보장할 수 있을까요?

1. Number 타입의 객체를 보장할 수 있습니다. 왜냐하면, foo3가 가리키는 리스트는 Number의 리스트이거나 Number의 서브클래스의 리스트이기 때문입니다.
2. Integer 타입의 객체는 보장할 수 없습니다. 왜냐하면 foo3가 가리키는 리스트는 Double의 리스트(List<Double>)일 수도 있기 때문입니다.
3. Double 타입의 객체는 보장할 수 없습니다. 왜냐하면 foo3가 가리키는 리스트는 Integer의 리스트(List<Integer>)일 수도 있기 때문입니다.

1.2 Writing

foo3에는 어떤 객체 타입을 추가(add)할 수 있을까요?

1. Integer는 추가할 수 없습니다. 왜냐하면 foo3가 Double의 리스트(List<Double>)을 가리키고 있을 수 있기 때문입니다.
2. Double은 추가할 수 없습니다. 왜냐하면 foo3가 Integer의 리스트(List<Integer>)을 가리키고 있을 수 있기 때문입니다.
3. Number도 추가할 수 없습니다. 왜냐하면 foo3가 Integer의 리스트(List<Integer>)을 가리키고 있을 수 있기 때문입니다.

List<? extends T> 에는 어떤 객체도 추가할 수가 없습니다. 왜냐하면 어떤 타입을 담은 리스트인지를 알 수가 없기 때문입니다. 단지 “보장”할 수 있는 것은 T 타입 또는 T의 서브타입을 읽는 것 뿐입니다.

2. <? super T> – lower bounded

List<? super Integer> 선언은 다음의 문장이 적합하다는 것을 의미합니다.

List<? super Integer> foo3 = new ArrayList<Integer>();
List<? super Integer> foo3 = new ArrayList<Number>();
List<? super Integer> foo3 = new ArrayList<Object>();

2.1 Reading

foo3에서 값을 읽을 때, 우리는 그 값이 어떤 객체 타입임을 보장할 수 있을까요?

1. Integer임을 보장할 수 없습니다. 왜냐하면 foo3는 Number일 수도 있기 때문입니다.
2. Number임을 보장할 수 없습니다. 왜냐하면 foo3는 Object일 수도 있기 때문입니다.
3. 보장할 수 있는 객체 타입은 Object 또는 Object의 서브 타입(하지만 구체적인 타입은 모름)입니다.

2.2 Writing

foo3에는 어떤 객체 타입을 추가(add)할 수 있을까요?

1. Integer를 추가할 수 있습니다. 왜냐하면, Integer는 Number와 Object의 서브 타입이기 때문입니다.
2. Integer의 서브 타입을 추가할 수 있습니다. 왜냐하면 Integer의 서브 타입도 Number와 Object의 서브 타입이기 때문입니다.
3. Double을 추가할 수 없습니다. 왜냐하면 foo3가 Integer의 리스트(List<Integer>)를 가리킬 수 있기 때문입니다.
4. Number를 추가할 수 없습니다. 왜냐하면 foo3가 Integer의 리스트(List<Integer>)를 가리킬 수 있기 때문입니다.
5. Object를 추가할 수 없습니다. 왜냐하면 foo3가 Integer의 리스트(List<Integer>)를 가리킬 수 있기 때문입니다.

3. PECS

“Producer Extends, Consumer Super” Joshua Bloch가 Effective Java 에서 정리한 것

1. Producer Extends: 만약에 T 타입의 값들을 생성하는(produce) 리스트가 필요하다면 (다른말로, 리스트에서 T 타입의 값을 읽으려 한다면) “extends”를 사용하라. 하지만 리스트에 값을 추가(add)할 수는 없다.
2. Consumer Super: 만약에 T 타입의 값들을 소비하는(consume) 리스트가 필요하다면 (다른말로, T 타입의 값을 리스트에 쓰려고 한다면) “super”를 사용하라. 하지만 리스트에 어떤 타입의 객체가 들어있는지는 알 수가 없다.
3. 리스트에 값 읽기/쓰기를 모두 해야한다면, 와일드 카드를 사용해서는 안되고 List<Integer>처럼 정확한 타입 파라미터를 사용해야 한다.

4. Example

public class Collections {
public static <T> void copy(List<? super T> dest, List<? extends T> src)
{
for (int i=0; i<src.size(); i++)
dest.set(i,src.get(i));
}
}

 

SpringBoot 1.4.x on Bluemix

Bluemix에서 Tomcat 어플리케이션을 선택하면, 기본적인 템플릿 어플리케이션을 만들어 줍니다. 템플릿 어플리케이션은 HttpServlet을 구현한 HelloWorld 입니다.

SpringBoot으로 작성한 어플리케이션이 Bluemix에서 잘 동작하는지 궁금해서 HelloWorld를 SpringBoot 1.4.1(현재 기준 최신 버전)로 작성하여 업로드 하였습니다. war를 업로드하고 실행하는 시점에서 ClassNotFoundError: ApplicationContextInitializer 에러가 발생합니다. 그래서 war 패키징할 때 Spring  관련 jar 파일들이 빠진것인지 여러번 확인해 보았으나 그것은 아니었습니다.

한참 구글링을 해보니 동일한 증상의 이슈가 StackOverflow에 있었습니다.

http://stackoverflow.com/questions/35712435/spring-boot-java-lang-classnotfoundexception-org-springframework-context-appl

문제의 원인은 SpringBoot가 버전 1.4로 업데이트 되면서 jar(war 도)의 패키지 레이아웃이 변경되었습니다.

https://github.com/spring-projects/spring-boot/wiki/Spring-Boot-1.4.0-M1-Release-Notes#executable-jar-layout

lib -> BOOT-INF/lib

classes -> BOOT-INF/classes

그런데 현재 Bluemix에서 사용하고 있는 CloudFoundry가 SpringBoot 1.4.x 버전의 레이아웃을 지원하지 않아서 클래스를 찾지 못한 것이었습니다.

SpringBoot 1.3.x를 사용하면 Bluemix에서 문제가 발생하지 않습니다.

 

 

Generic Json Parsing with ObjectMapper

REST API 사용이 대세가 되면서, 내부 시스템 또는 외부 시스템 호출에서 Json을 다루는 일은 아주 흔하다. Java 개발자들이 가장 많이 사용하는 Json Processor 중에 하나는 Jackson Json Processor이다. ObjectMapper 클래스는  직접  Json serialization/deserialization을 다룰 수 있도록 해준다. Serialization은 Java 객체를 문자열화된 Json으로 만드는 것을 뜻하고, deserialization은 반대로 문자열화된 Json을 파싱하여 Java 객체로 만드는 것이다.

오늘 일하면서 겪었던 문제는 Generic Json(내가 지어낸 말)이다. 보통 REST API에서는 응답 Json의 형태가 일정한 모양을 가지는데, 일종의 header 의미를 가지는 프로퍼티와 body의 의미를 가지는 프로퍼티로 나뉜다.

예를 들면, 고객(Customer)에 대한 정보를 보여주는 Json은 아래와 같고,

{
"result": "success",
"errorMessage": null,
"errorCode": 0,
"data": {
"name": "hong",
"email": "foo@bar.com",
"age": 30,
"gender": "M",
}

구매 항목 (Item) 대한 정보를 보여주는 Json은 다음과 같다.

{
"result": "success",
"errorMessage": null,
"errorCode": 0,
"data": {
"name": "TV",
"price": 500000,
"manufacturer": "Foo electronics"
}

여기서 header 에 해당하는 부분은  result, errorMessage, errorCode 이고, body 부분은 data이다. 그런데 이 data property는 요청에 따라 달라진다. 위의 예처럼 Customer가 되기도하고, Item에 해당하기도 한다. 이럴 경우 직관적으로 생각했을 때,  Generics를 사용하여 깔끔하게  POJO를 만들 수 있다.

public class Response<T> {
private String result;
private String errorMessage;
private String errorCode;

private T data;

// getters, setters
}

public class Customer {

}

public class Item {

}

그런데 문제는 Jackson Json의 ObjectMapper로 어떻게 data의 타입에 따라 deserialization하느냐가 남아있다.

ObjectMapper로 deserialization하는 가장 기본적인 메쏘드는 readValue()이다.

objectMapper.readValue(json, Response<Customer>.class)

이렇게하면 컴파일 오류가 난다. Response<Customer>.class라는 표현은 할 수가 없기 때문이다.

대신에 ObjectMapper는 다음과 같은 overloading 메쏘드를 제공한다.

objectMapper.readValue(json, objectMapper.getTypeFactory().constructParametricType(AdminResponse.class, clazz));

위에서 clazz는 타입 파라미터인 Customer.class, Item.class를 나타낸다. 즉, 동적으로 Response에서 T에 해당하는 타입 파라미터를 가진 타입을 만들수가 있는 것이다.
Generics를 제대로 이해하지 못하고 있어, 이부분에서 헤메었다. Generics는 컴파일 타임에서만 타입 파라미터 을 확인하고, 바이트 코드로 변환될 때에는 정해진 규칙에 따라 타입 파라미터는 변경되고, 필요에 따라서는 추가적으로 타입 캐스팅도 추가된다. 이것을 Type Erasure 라고 한다. 결과적으로 타입 파라미터는 사라지고 원래 클래스 타입만 남는다. Generics 정확한 이해가 있었다면, ObjectMapper API를 모두 알고 있지 않더라도, Generics 타입을 생성하는 어떤 것이 있을 것이라고 짐작이라도 했을텐데…
무엇이든 기본을 정확하게 이해하는 것이 중요하다.

2개의 큐로 1개의 스택 구현하기 (Stack Using 2 Queues)

최근에 나는 프로그래머다에서 임백준 작가가 코딩 인터뷰에 낸 적이 있었던 문제라고 해서 한번 구현해 보았다.

2개의 큐를 이용해서 1개의 스택 구현하기

import java.util.LinkedList;
import java.util.Queue;

public class StackUsing2Queues {
	private Queue<Object> queue1 = new LinkedList<>();
	private Queue<Object> queue2 = new LinkedList<>();
	// indicator which queue should be used
	// if flag is true, then queque1 should be used, false then queue2
	private boolean flag = true;
	
	public void push(Object obj) {
		if(flag) {
			while(!queue1.isEmpty()) {
				Object extracted = queue1.poll();
				queue2.offer(extracted);
			}
			queue1.offer(obj);
		}
		else {
			while(!queue2.isEmpty()) {
				Object extracted = queue2.poll();
				queue1.offer(extracted);
			}
			queue2.offer(obj);
		}
	}
	
	public Object pop() {
		Object ret = null;
		if(flag) {
			ret = queue1.poll();
			while(queue2.size() > 1) {
				Object extracted = queue2.poll();
				queue1.offer(extracted);
			}
		}
		else {
			ret = queue2.poll();
			while(queue1.size() > 1) {
				Object extracted = queue1.poll();
				queue2.offer(extracted);
			}
		}
		
		flag = !flag;
		return ret;
	}
}

테스트를 포함한 코드는 GitHub https://github.com/jinwooe/stack-using-2queues 에서도 볼 수 있다