자료구조 - 배열, 큐(Queue), 스택(Stack)

Remind123 2022. 10. 8. 16:28

2022. 10. 8. 16:28

- 자료구조란?
대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조를 의미
코드상에서 효율적으로 데이터를 처리하기 위해, 데이터 특성에 따라 체계적으로 데이터를 구조화해야 함

- 대표적인 자료구조
배열, 스택, 큐, 링크드 리스트, 해쉬 테이블, 힙 등

- 알고리즘이란?
어떤 문제를 풀기 위한 절차/방법
어떤 문제에 대해, 특정한 입력을 넣으면 원하는 출력을 얻을 수 있도록 만드는 프로그래밍

어떤 자료구조와 알고리즘을 쓰느냐에 따라, 성능이 차이가 많이 난다.

- 주피터 노트북 사용법

셀 추가 하는 방법)
셀 누르고 a 누르면 해당 셀 위에 새로운 셀 생성
셀 누르고 b 누르면 해당 셀 아래에 새로운 셀 생성

셀 삭제 방법)
셀 누르고 dd 누르면 해당 셀 삭제

셀에 코드를 작성할지 마크다운을 쓸지 선택은 셀 선택후 상단 탭에서 원하는 것을 선택하면 된다.

셀 실행 방법)
셀 선택 후 컨트롤 + 엔터

마크다운의 경우 셀을 더블클릭 하면 해당 내용이 어떻게 작성되었는지 볼 수 있고 수정 가능.

1. 배열

배열은 같은 종류의 데이터를 효율적으로 관리하기 위해 사용
같은 종류의 데이터를 순차적으로 저장

장점 : 빠른 접근 가능(인덱스 번호로 접근)
단점 : 데이터 추가/삭제의 어려움. 미리 최대 길이를 지정해야 함

1차원 배열, 2차원 배열, 3차원 배열 존재

2. 큐(Queue)

- 구조
가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조 - FIFO 방식으로 데이터를 꺼낸다.

Enqueue : 큐에 데이터를 넣는 기능
Dequeue : 큐에서 데이터를 꺼내는 기능

Java에서는
Enqueue 기능-> add 또는 offer라는 메서드 사용
Dequeue 기능-> remove 또는 poll이라는 메서드 사용

큐는 어디에 쓰일까?
멀티 태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해 많이 사용됨

Queue를 구현하고 있는 클래스는 LinkedList가 있다.

다형성을 이용해 Queue 타입의 참조변수를 만들 수 있다.

ArrayList로 Queue의 기능 구현해보기)

import java.util.ArrayList;

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

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

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

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

    public static void main(String args[]) {
        MyQueue<Integer> q = new MyQueue<>();
        q.enqueue(1);
        q.enqueue(2);
        q.enqueue(3);

        System.out.println(q.dequeue());
        System.out.println(q.dequeue());
        System.out.println(q.dequeue());
    }
}

3. 스택(Stack)

가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조 - LIFO 방식으로 데이터를 꺼낸다.

- 대표적인 스택의 활용

-> 컴퓨터 내부의 프로세스 구조의 함수 동작 방식(?)

- 주요 기능

push() : 데이터를 스택에 넣기

pop() : 데이터를 스택에서 꺼내기

- 스택의 장단점

장점)

구조가 단순해서, 구현이 쉽다.

데이터 저장/읽기 속도가 빠르다.

단점(일반적인 스택 구현시)

데이터 최대 갯수를 미리 정해야 한다.(최대 사이즈를 좀 크게 잡아야 하는듯)

따라서 저장 공간의 낭비가 발생할 수 있음

- Java에서 스택 자료 구조 사용하기

Stack 클래스를 사용하면 된다.

ArrayList로 Stack 기능 구현해보기)

import java.util.ArrayList;

public class MyStack<T> {

    private ArrayList<T> list = new ArrayList<>();

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

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

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

        System.out.println(ms.pop());
        System.out.println(ms.pop());
        System.out.println(ms.pop());
    }
}

개발 공부 기록