알고리즘/Java 기초

자바 자료구조3 -자바에서 스택, 큐, 덱 사용법-

1. Stack

 

import java.util.Stack

 

Stack<(type)> (name) = new Stack<>();

 

여기서 (type)은 reference type으로 스택 안에 들어갈 원소의 타입

 

import java.util.Stack;

public class Main {
    public static void main(String[] args){
        Stack<Integer> s = new Stack<>();
    }
}

 

 

2. stack 핵심 메소드

 

2-1) push(E)

 

맨 위에 데이터 E를 추가

 

2-2) size()

 

stack에 들어있는 데이터 수를 반환

 

2-3) isEmpty()

 

stack이 비어있다면 true, 아니라면 false를 반환

 

2-4) peek()

 

stack의 가장 위에 있는 데이터를 반환

 

2-5) pop()

 

stack의 가장 위에 있는 데이터를 반환하며 동시에 그 데이터를 stack에서 제거한다.

 

import java.util.Stack;

public class Main {
    public static void main(String[] args){
    
        //정수를 관리할 stack을 선언(빈 스택)
        Stack<Integer> s = new Stack<>();
        
        s.push(2);
        s.push(5);
        s.push(9);
        
        //가장 나중에 들어온 원소 출력(9)
        System.out.println(s.peek());
        
        //가장 나중에 들어온 원소 제거
        s.pop();
        
        //원소의 개수 출력
        System.out.println(s.size());
        
        while(!s.isEmpty()){
        //가장 나중에 들어간 원소부터 순서대로 출력
            System.out.println(s.pop());
        }
   }
}

 

 

3. 연습문제1

 

  1. push A: 정수 A를 스택에 넣는 연산입니다. 새로 들어온 정수는 상단부터 차례대로 스택에 쌓입니다.
  2. pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력합니다.
  3. size: 스택에 들어있는 정수의 개수를 출력합니다.
  4. empty: 스택이 비어있으면 1, 아니면 0을 출력합니다.
  5. top: 스택의 가장 위에 있는 정수를 출력합니다.

 

import java.util.Stack;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        Stack<Integer> stack = new Stack<>();

        for(int i = 0; i< n; i++){
            
            String q = sc.next();

            if(q.equals("push")){

                int A = sc.nextInt();

                stack.push(A);
            } else if(q.equals("pop")){

                System.out.println(stack.pop());
            } else if(q.equals("size")){
                System.out.println(stack.size());
            } else if(q.equals("empty")){

                if(stack.isEmpty() == true){
                    System.out.println(1);
                } else {
                    System.out.println(0);
                }
            } else {
                System.out.println(stack.peek());
            }
        }
    }
}

 

 

4. 큐

 

import java.util.Queue;

import java.util.LinkedList;

 

Queue<(type)> name = new LinkedList<>();의 형태 선언

 

type은 reference type이고 큐에 들어갈 원소의 타입

 

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

public class Main{
    public static void main(String[] args){
        Queue<Integer> q = new LinkedList<>();
    }
}

 

 

5. 큐 핵심 메소드

 

5-1) add(E)

 

맨 뒤에 데이터 E를 추가

 

5-2) size()

 

현재 큐에 들어있는 데이터의 수를 반환

 

 

5-3) isEmpty()

 

현재 큐가 비어있다면 true, 아니라면 false를 반환

 

 

5-4) peek()

 

큐의 맨 앞에 있는 데이터를 반환

 

 

5-5) poll()

 

큐의 맨 앞에 있는 데이터를 반환하고 동시에 그 데이터를 큐에서 뺀다.

 

peek는 제거하지 않은데 poll은 제거함

 

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

public class Main {
    public static void main(String[] args){
        
        //정수를 관리할 queue를 선언합니다(빈 큐)
        Queue<Integer> q = new LinkedList<>();
        
        q.add(3);
        q.add(5);
        q.add(9);
        
        //가장 앞에 있는 원소 3을 출력
        System.out.println(q.peek());
        
        //가장 앞에 있는 3을 제거
        q.poll();
        
        //원소의 개수 2개 출력 
        System.out.println(q.size());
        
        //가장 앞에 있는 원소부터 순서대로 5,9 출력
        while(!q.isEmpty()){
        System.out.println(q.poll());
        }
    }
}

 

6. 연습문제2

 

  1. push A: 정수 A를 큐에 넣는 연산입니다.
  2. pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력합니다.
  3. size: 큐에 들어있는 정수의 개수를 출력합니다.
  4. empty: 큐가 비어있으면 1, 아니면 0을 출력합니다.
  5. front : 큐의 가장 앞에 있는 정수를 출력합니다.

 

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

public class Main {
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        Queue<Integer> queue = new LinkedList<>();

        for(int i = 0; i < n; i++){

            String q = sc.next();

            if(q.equals("push")){

                int A = sc.nextInt();

                queue.add(A);
            } else if(q.equals("pop")){

                System.out.println(queue.poll());
            } else if(q.equals("size")){
                System.out.println(queue.size());
            } else if(q.equals("empty")){
                
                if(queue.isEmpty() == true){
                    System.out.println(1);
                } else {
                    System.out.println(0);
                }
            } else {
                System.out.println(queue.peek());
            }
        }
    }
}

 

 

7. Deque

 

자바에서 Deque를 사용하기 위해..

 

import java.util.Deque;

import java.util.ArrayDeque;

 

Deque<(type)> (name) = new ArrayDeque<>(); 형태의 선언이 필요하다.

 

import java.util.Deque;
import java.util.ArrayDeque;

public class Main{
    public static void main(String[] args){
        Deque<Integer> dq = new ArrayDeque<>();
    }
}

 

8. deque 핵심 메소드

 

8-1) addFirst(E)

 

맨 앞에 데이터 E를 추가한다

 

8-2) addLast(E)

 

맨 뒤에 데이터 E를 추가한다

 

8-3) pollFirst()

 

맨 앞에 있는 데이터를 반환하고 deque에서 제거한다

 

8-4) pollLast()

 

맨 뒤에 있는 데이터를 반환하고 deque에서 제거한다.

 

8-5) size()

 

현재 deque에 들어있는 데이터의 수를 반환한다

 

8-6) isEmpty()

 

현재 deque가 비어있다면 true, 아니라면 false를 반환한다

 

8-7) peekFirst()

 

deque의 맨 앞에 있는 데이터를 반환

 

8-8) peekLast()

 

deque의 맨 뒤에 있는 데이터를 반환

 

import java.util.Deque;
import java.util.ArrayDeque;

public class Main {
    public static void main(String[] args){
    
        //정수를 관리할 deque를 선언
        Deque<Integer> dq = new ArrayDeque<>();
        
        //맨 앞에 3,5를 순서대로 추가
        //[5,3]으로 들어있음
        dq.addFirst(3);
        dq.addFirst(5);
        
        //맨 앞에 적혀있는 숫자 5가 출력
        System.out.println(dq.peekFirst());
        
        //맨 뒤에 9를 추가
        //[5,3,9]
        dq.addLast(9);
        
        //맨 뒤에 적혀있는 숫자인 9가 출력
        System.out.println(dq.peekLast());
        
        //맨 앞 숫자(5)를 제거한다.
        //[3,9]
        dq.pollFirst();
        
        //맨 앞에 적힌 숫자 3을 출력
        System.out.println(dq.peekFirst());
        //원소의 개수 2를 출력
        System.out.println(dq.size());
    }
}

 

 

9. 연습문제3

 

  1. push_front A: 정수 A를 덱의 앞에 넣습니다.
  2. push_back A: 정수 A를 덱의 뒤에 넣습니다.
  3. pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력합니다.
  4. pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력합니다.
  5. size: 덱에 들어있는 정수의 개수를 출력합니다.
  6. empty: 덱이 비어있으면 1을, 아니면 0을 출력합니다.
  7. front: 덱의 가장 앞에 있는 정수를 출력합니다.
  8. back: 덱의 가장 뒤에 있는 정수를 출력합니다.

 

import java.util.Scanner;
import java.util.Deque;
import java.util.ArrayDeque;

public class Main {
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        Deque<Integer> deque = new ArrayDeque<>();

        for(int i = 0; i < n; i++){

            String q = sc.next();

            if(q.equals("push_front")){

                int A = sc.nextInt();

                deque.addFirst(A);
            } else if(q.equals("push_back")){

                int A = sc.nextInt();

                deque.addLast(A);

            } else if(q.equals("pop_front")){

                System.out.println(deque.pollFirst());

            } else if(q.equals("pop_back")){

                System.out.println(deque.pollLast());

            } else if(q.equals("size")){

                System.out.println(deque.size());

            } else if(q.equals("empty")){

                if(deque.isEmpty() == true){

                    System.out.println(1);

                } else {

                    System.out.println(0);

                }

            } else if(q.equals("front")){

                System.out.println(deque.peekFirst());
            } else {
                System.out.println(deque.peekLast());
            }

        }
    }
}

 

 

10. 연습문제4

 

1부터 N까지의 정수가 오름차순으로 정렬되어있습니다. 이 수열을 정수가 하나만 남을때까지 다음과 같은 동작을 반복하는 프로그램을 작성해봅시다.

  1. 맨 앞의 정수를 제거합니다.
  2. 그 후 남은 수열의 맨 앞의 정수를 맨 뒤로 이동시킵니다.

 

시키는대로 구현하면 된다

 

1부터 N까지를 모두 deque에 넣고, 앞의 정수를 pollFirst()로 제거한 다음, 다시 앞의 정수를 pollFirst()로 빼서,

 

이를 k에 저장해서, k를 다시 맨 뒤로 넣는, addLast()를 수행

 

dq.size() != 1이 아닌 동안 계속 반복하도록 while문을 이용해 반복 수행

 

import java.util.Deque;
import java.util.ArrayDeque;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        Deque<Integer> dq = new ArrayDeque<>();

        for(int i = 1; i < n+1; i++){
            dq.addLast(i);
        }

        while(dq.size() != 1){
            dq.pollFirst();
            int k = dq.pollFirst();
            dq.addLast(k);
        }

        System.out.println(dq.peekFirst());
    }
}

'알고리즘 > Java 기초' 카테고리의 다른 글

자바 자료구조5 -우선순위 큐 사용법-  (0) 2023.03.04
자바 자료구조4 -HashMap과 HashSet-  (0) 2023.03.04
자바 초보부터 B형까지9 -class 생성하기 필수-  (0) 2023.03.01
자바 초보부터 B형까지8 -2차원 배열 필수-  (0) 2023.03.01
자바 초보부터 B형까지7 -변수의 범위, 지역변수, 전역변수 설정방법-  (0) 2023.03.01
TAGS.

Comments