JAVA 자료구조 : Queue 와 Stack

스터디사이트 : https://www.hackerrank.com

JAVA 자료구조 : Queue 와 Stack

※ 조건

입력된 단어가 palindrome (회문) 인지 판단하는 코딩을 하시오.

palindrome - 회문

- 단어, 숫자 등의 문자열이 데칼코마니처럼 단어의 앞과 뒤가 똑같은 단어를 일컫는 말

- 앞으로 읽어도 뒤로 읽어도 똑같은 말.

ex) madam, nurses run

• 주어진 단어 각각의 문자를 queue에 더해야 한다.
• 또한 stack에도 push 해야 한다.
• 이러한 step이 완료되면, 완료된 문자는 queue에서 빠져나오게 하고, stack에서 pop시킨다.
• 그리고 두 문자를 비교해서 같은지 비교한다.
• 두 문자가 일치할 때까지 dequeue와 pop, 비교하는 작업을 queue와 stack이 비워질 때까지 계속한다.

다음의 조건을 따라야 한다.

1. stack과 queue 인스턴스 변수를 선언한다.

2. void pushCharacter(char ch) 메소드는 문자를 stack으로 push시킨다.

3. void enqueueCharacter(char ch) 메소드는 queue 인스턴스 변수에 enqueue(queue에 더해야) 한다.

4. char popCharacter() 메소드는 stack에서 pop하고 stack 인스턴스변수의 가장 상단에 위치한 문자를 리턴한다.

5. char dequeueCharacter() 메소드는 queue에서 dequeue(queue에서 빠져나오게)하고 queue 인스턴스변수에서 첫번째 문자를 리턴한다.

Queue ( 큐 )

 : FIFO ( First In First Out ) - 처음 들어간 데이터가 처음 나온다. ( 가로로 눕힌 통 )

Stack ( 스택 )

 : LIFO ( Last In First Out ) - 맨 나중에 들어간 데이터가 처음 나온다. ( 세로로 세워진 통 )

※ 주어진 코드

: 아래 표시된 영역 안에서만 코딩 할 것.

public class Solution {
    // Write your code here.
     /* 이곳에 코딩. */
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String input = scan.nextLine();
        scan.close();
        // Convert input String to an array of characters:
        char[] s = input.toCharArray();
        // Create a Solution object:
        Solution p = new Solution();
        // Enqueue/Push all chars to their respective data structures:
        for (char c : s) {
            p.pushCharacter(c);
            p.enqueueCharacter(c);
        }
        // Pop/Dequeue the chars at the head of both data structures and compare them:
        boolean isPalindrome = true;
        for (int i = 0; i < s.length/2; i++) {
            if (p.popCharacter() != p.dequeueCharacter()) {
                isPalindrome = false;                
                break;
            }
        }
        //Finally, print whether string s is palindrome or not.
        System.out.println( "The word, " + input + ", is " 
                           + ( (!isPalindrome) ? "not a palindrome." : "a palindrome." ) );
    }
}

입력

racecar

출력

The word, racecar, is a palindrome.

결과 - LinkedList 클래스

LinkedList 클래스만을 이용하였는데 잘 된다.

STACK

.push(ch) : 스택에 삽입

.pop() : 스택에 있는 가장 위에 것 추출

QUEUE

.addLast(ch) : 큐의 맨 마지막 자리에 삽입

.removeFirst() : 큐의 맨 첫번째자리 추출.

or

.addFirst(ch) : 큐의 맨 첫번째자리에 삽입

.removeLast() : 큐의 맨 마지막자리 추출.

public class Solution { LinkedList<Character> queue = new LinkedList<Character>(); LinkedList<Character> stack = new LinkedList<Character>(); /* Stack : LIFO (push, pop) , Queue : FIFO (enqueue, dequeue) */ void pushCharacter(char ch){ stack.push(ch); } //end pushCharacter char popCharacter(){ return stack.pop(); } //end popCharacter void enqueueCharacter(char ch){ queue.addLast(ch); } //end enqueueCharacter char dequeueCharacter(){ return queue.removeFirst(); } //end dequeueCharacter public static void main(String[] args) { Scanner scan = new Scanner(System.in); String input = scan.nextLine(); scan.close(); // Convert input String to an array of characters: char[] s = input.toCharArray(); // Create a Solution object: Solution p = new Solution(); // Enqueue/Push all chars to their respective data structures: for (char c : s) { p.pushCharacter(c); p.enqueueCharacter(c); } // Pop/Dequeue the chars at the head of both data structures and compare them: boolean isPalindrome = true; for (int i = 0; i < s.length/2; i++) { if (p.popCharacter() != p.dequeueCharacter()) { isPalindrome = false; break; } } //Finally, print whether string s is palindrome or not. System.out.println( "The word, " + input + ", is " + ( (!isPalindrome) ? "not a palindrome." : "a palindrome." ) ); } }

결과 :  The word, racecar, is a palindrome.

결과 - LinkedList(queue) & Stack 클래스

LinkedList(queue) & Stack 클래스를 이용한 결과이다.

Queue 는 인터페이스인데, Queue queue = new Queue(); 형식으로 만들 수가 

public class Solution { LinkedList<Character> queue = new LinkedList<Character>(); Stack<Character> stack = new Stack<>(); /* Stack : LIFO (push, pop) , Queue : FIFO (enqueue, dequeue) */ void pushCharacter(char ch){ stack.push(ch); } //end pushCharacter char popCharacter(){ return stack.pop(); } //end popCharacter void enqueueCharacter(char ch){ queue.addLast(ch); } //end enqueueCharacter char dequeueCharacter(){ return queue.removeFirst(); } //end dequeueCharacter public static void main(String[] args) { Scanner scan = new Scanner(System.in); String input = scan.nextLine(); scan.close(); // Convert input String to an array of characters: char[] s = input.toCharArray(); // Create a Solution object: Solution p = new Solution(); // Enqueue/Push all chars to their respective data structures: for (char c : s) { p.pushCharacter(c); p.enqueueCharacter(c); } // Pop/Dequeue the chars at the head of both data structures and compare them: boolean isPalindrome = true; for (int i = 0; i < s.length/2; i++) { if (p.popCharacter() != p.dequeueCharacter()) { isPalindrome = false; break; } } //Finally, print whether string s is palindrome or not. System.out.println( "The word, " + input + ", is " + ( (!isPalindrome) ? "not a palindrome." : "a palindrome." ) ); } }

결과 :  The word, racecar, is a palindrome.

다른 사람이 한 코딩 1 - Queue & LinkedList & Stack

Queue 객체를 만들 때, Queue 인터페이스를 구현한 클래스로 인스턴스화하는 방법이 있었다..

public class Solution { Stack<Character> stack = new Stack<>(); Queue<Character> queue = new LinkedList<>(); void pushCharacter(Character ch) { stack.push(ch); } void enqueueCharacter(char ch) { queue.add(ch); } char popCharacter(){ return stack.pop(); } char dequeueCharacter() { return queue.remove(); } public static void main(String[] args) { Scanner scan = new Scanner(System.in); String input = scan.nextLine(); scan.close(); // Convert input String to an array of characters: char[] s = input.toCharArray(); // Create a Solution object: Solution p = new Solution(); // Enqueue/Push all chars to their respective data structures: for (char c : s) { p.pushCharacter(c); p.enqueueCharacter(c); } // Pop/Dequeue the chars at the head of both data structures and compare them: boolean isPalindrome = true; for (int i = 0; i < s.length/2; i++) { if (p.popCharacter() != p.dequeueCharacter()) { isPalindrome = false; break; } } //Finally, print whether string s is palindrome or not. System.out.println( "The word, " + input + ", is " + ( (!isPalindrome) ? "not a palindrome." : "a palindrome." ) ); } }

결과 :  The word, racecar, is a palindrome.