[자료구조] 배열 (Array), 큐(Queue), 스택(Stack)

배열 (Array)

 

같은 타입의 데이터를 순차적으로 저장하여 관리

• index 번호로 빠른 데이터 접근이 가능
• 데이터 추가/삭제의 어려움
• 미리 최대 길이를 지정해야 하고 바꿀 수 없음

 

ArrayList 클래스로 배열 다루기

 

// int 형 데이터를 담을 수 있는 가변 길이의 배열 선언
ArrayList<Integer> list1 = new ArrayList<Integer>(); 

// 배열에 아이템 추가 시 add(아이템) 메서드 사용
list1.add(1);
list1.add(2);

// 배열에 특정 아이템을 읽을 시 get(인덱스번호) 메서드 사용 
// (굳이 System.out.println() 을 사용하지 않아도 됨)
list1.get(0) // 1

// 특정 인덱스에 해당하는 아이템 변경 시, set(인덱스번호, 변경할값) 메서드 사용
list1.set(0, 5); 
list1.get(0); // 5

// 특정 인덱스에 해당하는 아이템 삭제 시, remove(인덱스번호) 메서드 사용
list1.remove(0); 
list1.get(0) // 2

// 배열 길이 확인하기
list1.size() // 1

 

문자 M을 가지고 있는 아이템 수 출력하기

// 문자열.indexof(String key) 
//     : 문자 key가 해당 문자열에 있으면 해당 문자의 위치 (index 값)을 리턴하고, 
//       없으면 -1 을 리턴함

String dataset[] = {
    "Braund, Mr. Owen Harris",
    "Cumings, Mrs. John Bradley (Florence Briggs Thayer)",
    "Heikkinen, Miss. Laina",
};

Integer count = 0;

for (Integer item=0; item < dataset.length; item++) {
    if (dataset[item].indexOf("M") >= 0) {   
        // System.out.println(dataset[item]);
        count++;
    }
}

System.out.println(count); // 3

 

 

큐(Queue)

• FIFO(선입선출) 구조로 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 구조
• 마트 줄서면 먼저 선 사람부터 계산하는 원리와 동일
• 그래프의 넓이 우선 탐색(BFS)에서 사용
• 컴퓨터 버퍼에서 많은 입력으로 인해 처리를 하지 못할 때 버퍼(큐)를 만들어 대기 시킴
• 멀티 태스킹을 위한 프로세스 스케줄링 방식을 구현하기 위해 사용

출처 : https://coding-factory.tistory.com/602

java.util 패키지에서 Queue 클래스를 제공한다

• LinkedList 클래스 사용하여 Queue 클래스 데이터 생성
• enqueue : add(value), offer(value) 메서드 
• dequeue : poll(), remove() 메서드 
• 첫번째로 저장된 값 확인 : peek() 메서드

 

// Queue 사용을 위해, LinkedList 클래스를 사용하므로, 두 클래스 모두 import 해야 함
import java.util.LinkedList; 
import java.util.Queue;

// 자료형 매개변수를 넣어서, 큐에 들어갈 데이터의 타입을 지정해야 함
// Integer 형 queue 선언
Queue<Integer> queue_int = new LinkedList<Integer>(); 

// 데이터 추가
queue_int.add(1);
queue_int.offer(2);

// Queue 인스턴스를 출력하면, 해당 큐에 들어 있는 아이템 리스트가 출력됨
System.out.println(queue_int)

// 큐의 첫 번째 값 반환, 해당 값은 큐에서 삭제
queue_int.poll();
queue_int.remove()

 

ArrayList 클래스를 이용해 Queue의 enqueue, dequeue 기능 구현

 

import java.util.ArrayList;

public class Queue<T> {
    private ArrayList<T> queue = new ArrayList<T>();

    public void enqueue(T item) {
        queue.add(item);
    }

    public T dequeue() {
        if (queue.isEmpty()) {
            return null;
        }
        return queue.remove(0);
    }

    public boolean isEmpty() {
        return queue.isEmpty();
    }

    public static void main(String[] args) {
        Queue<Integer> mq = new Queue<Integer>();
        
        mq.enqueue(1);
        mq.enqueue(2);
        mq.enqueue(3);
        
        System.out.println(mq.dequeue());  // 1
        System.out.println(mq.dequeue());  // 2
        System.out.println(mq.dequeue());  // 3  
    }
}

 

 

스택(Stack)

• LIFO(후입선출) 구조로 가장 나중에 넣은 데이터를 가장 먼저 꺼내는 데이터 구조
• 상자에 물건을 쌓아 올리듯이 데이터를 쌓는 자료 구조
• 컴퓨터 내부의 프로세스 구조의 함수 동작 방식
• 그래프의 깊이 우선 탐색(DFS)에서 사용
• 단순하고 빠른 성능을 자랑하지만 데이터의 최대 갯수를 미리 정해야 해서 저장 공간의 낭비가 발생할 수 있다.
• 재귀적 함수 호출 시 사용

출처 : https://coding-factory.tistory.com/601

 

java.util.Stack을 import하면 바로 사용 가능하다.

• 데이터 추가 : push(item) 메서드
• 데이터 추출(삭제) : pop() 메서드
• 최상단 데이터 확인 : peek() 메서드

 

import java.util.Stack;

// 자료형 매개변수를 넣어서, 스택에 들어갈 데이터의 타입을 지정해야 함
Stack<Integer> stack_int = new Stack<Integer>(); 

stack_int.push(1);     // Stack 에 1 추가
stack_int.push(2);     // Stack 에 2 추가
stack_int.push(3);     // Stack 에 3 추가

stack_int.pop();       // 3
stack_int.pop();       // 2
stack_int.pop();       // 1

 

Java ArrayList 클래스를 활용해서 스택 구현하기

import java.util.ArrayList;

class MyStack<T> {
    private ArrayList<T> stack = new ArrayList<T>();

    public void push(T item) {
        stack.add(item);
    }

    public T pop() {
        if (stack.isEmpty()) {
            return null;
        }
        return stack.remove(stack.size() - 1);
    }

    public boolean isEmpty() {
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        MyStack<Integer> ms = new MyStack<Integer>();
        ms.push(1);
        ms.push(2);
        System.out.println(ms.pop()); // 2
        ms.push(3);
        System.out.println(ms.pop()); // 3
        System.out.println(ms.pop()); // 1
    }
}

 

 

 

출처

https://coding-factory.tistory.com/602