Algorithm - Stack and Queue CodingTest Tip

• Java로 코딩테스트를 준비하며 부족한 부분을 공부하기 위해 정리하였음.
• 코딩테스트 Stack 과 Queue와 관련된 정리내용임.

Stack

• Stack 의 주요 메서드

  • init(): 스택을 초기화한다.

  • isEmpty(): 스택이 비어있으면 true를 아니면 false를 반환한다.

  • isFull(): 스택이 가득 차 있으면 true를 아니면 false를 반환한다.

  • size(): 스택 내의 모든 요소들의 개수를 반환한다.

  • push(x): 스택 맨 위에 있는 요소를 삭제하고 반환한다.

  • pop(): 스택 맨 위에 있는 요소를 삭제하고 반환한다.

  • peek(): 스택 맨 위에 있는 요소를 삭제하지 않고 반환한다.

• 후위식 계산법

  • 숫자를 넣다가, 연산식이 들어오면 2개를 pop 하여 계산하고, 다시 스택에 담는다.

  • 이 때 먼저 pop 된게 rt이고, 그 다음에 pop 된게 lt이다. 그래서 lt (연산) rt 를 해줘야 한다.

  • 또한 숫자가 char 형으로 들어와있기 때문에 isDigit(c) 이후, 아스키코드이므로 -48을 해줘야 한다.

   public static int postfix(String str) {
       Stack<Integer> stack = new Stack<>();
       for ( char c : str.toCharArray() ) {
           if ( Character.isDigit(c) ) {
               stack.push((int)c -48);
           } else {
               int rt = stack.pop();
               int lt = stack.pop();
               if ( c == '+' ) {
                   stack.push(lt + rt);
               } else if ( c == '-' ) {
                   stack.push(lt - rt);
               } else if ( c == '*' ) {
                   stack.push(lt * rt);
               } else if ( c == '/' ) {
                   stack.push(lt / rt);
               }
           }
       }
       return stack.get(0);
   }
  

Queue

• Queue 는 일반적으로 LinkedList<> 의 형식으로 구현한다.

• 주요 메서드는 다음과 같다.

  • add(n) : n을 추가한다. 성공 시 true를 반환하고 큐가 꽉 차면 예외를 반환한다.

  • offer(n) : n을 추가한다.성공 시 true를 반환하고 큐가 꽉 차면 false를 반환한다.

  • remove() : 맨 앞의 value를 삭제하고 반환한다. 반환할 게 없으면 예외를 반환한다.

  • remove(n) : 해당 큐에 n가 있을 시 삭제하고 true를 반환한다. 없으면 false를 반환한다.

  • poll(); : 맨 앞의 value를 삭제하고 반환한다. 없으면 null을 반환한다.

  • element() : 삭제하지 않고 맨 앞의 value를 반환한다. 없으면 예외가 발생한다.

  • peek() : 삭제하지 않고 맨 앞의 value를 반환한다. 없으면 null을 반환한다.

  • clear(); 큐 초기화

  • size(); 큐 크기 반환

  • contains(n) : 큐에 n이 있는지 없는지 확인해서 삭제는 하지 않고 true, false로 반환한다.

  • isEmpty() : true false를 통해 해당 큐가 비어있는지 아닌지를 알려준다.