자료구조 : Stack / Queue

◎ 자료구조

• 데이터 : 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값

  • 단순히 데이터를 가지고 있는 것은 도움이 되지 않는다.
  • 데이터는 (목적과 필요에 따라) 분석하고 정리하여 활용해야만 의미를 가질 수 있다.
  • ex1) 전화번호 저장시에 - 은 굳이 저장할 필요가 없다.

• 자료구조

  • 무수한 상황에서 데이터를 효율적으로 다룰 수 있는 방법
  • 대부분의 자료구조는 특정한 상황에 놓인 문제를 해결하는 데에 특화
    • 많은 자료구조를 알아두면, 어떠한 상황이 닥쳤을 때 적합한 자료구조를 빠르고 정확하게 적용하여 문제를 해결할 수 있다.
  • 자료(데이터)를 다루는 구조 그 자체를 뜻하며, 구현하는 방식에는 제약이 없다.
  • 가장 많이 쓰이고 알고리즘 테스트(코딩 테스트)에 자주 등장하는 네 가지
    • Stack(스택), Queue(큐), Tree(트리), Graph(그래프)
      

• 자료 구조 공부시 봐야할 사항

  • 특징, 적합한 상황, (내부구조 직접 구현), 동작원리 이해
  • 알고리즘 문제 풀기

◎ Stack

• Stack

  • 데이터(data)를 순서대로 쌓는 자료구조
  • 가장 먼저 들어간 데이터가 가장 나중에 나옴 : LIFO(Last In First Out), FILO(First In Last Out)
  • 비유) 프링글스 통 (한쪽이 막혀서 쌓여있는 구조)

• Stack 특징

  • 데이터를 제한적으로 접근함 (맨 나중에 넣은 데이터만 접근 할 수 있다.)
  • 데이터는 하나씩 넣고 뺄 수 있다.
  • 하나의 입출력 방향을 가지고 있다.

• 중요 메서드

  • .push : 데이터를 넣음
  • .pop : 데이터를 꺼냄

• 적합한 상황 (실사용 예제)

  • 브라우저 뒤고가기, 앞으로 가기
    • Prev Stack, Next Stack 을 구현

◎ Queue

• Queue

  • 데이터(data)를 순서대로 줄세우는 자료구조
  • 가장 먼저 들어간 데이터가 가장 먼저 나옴 : FIFO(First In First Out)
  • 비유) 드라이브스루 (들어온 순서대로 나가는 구조)

• Queue 특징

  • 데이터를 제한적으로 접근함 (맨 처음에 넣은 데이터만 접근 할 수 있다.)
  • 데이터는 하나씩 넣고 뺄 수 있다.
  • 두 개의 입출력 방향을 가지고 있다.

• 중요 메서드

  • .add : 데이터를 넣음 ('enqueue')
  • .poll : 데이터를 꺼냄 ('dequeue')

• 적합한 상황 (실사용 예제)

  • Buffer : 각 장치 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용
  • 컴퓨터와 연결된 프린터에서 여러 문서를 순서대로 인쇄
    • Queue에 쌓아놓고, 먼저 쌓인것부터 인쇄

◎ Circular Queue (원형 큐)

• Queue의 단점

  • 큐에 데이터가 꽉 찼다면 데이터를 더 추가할 수 없습니다.
    (물론 큐 사이즈를 늘리고 원소를 다시 복사가 가능하지만 과정이 복잡)
  • 배열로 단순히 구현하면 front가 뒤로 계속 밀려 앞의 공간이 남게 되죠. 그러니까 하나의 원소가 빠져나가면 그 다음부터 모든 녀석들을 앞으로 당겨와야하니까 속도 측면에서 상당히 느리다.

• Circular Queue

  • 직선 형태로 놓는 것 보다 원형으로 생각해서 큐를 구현하는 것
  • 현재 front와 rear의 인덱스를 같이 저장해야 한다.
    • front와 rear는 설정하기에 따라 조금씩 다르게 해줄 수 있다.
    • front : 맨 앞에 있는 요소의 index를 가리킴
    • rear : 요소 추가시, 들어갈 자리를 가리킴

• 구현해보기

class CirQueue<T>{
    private int front = 0; // 맨 앞에 있는 데이터의 index를 가리킴
    private int rear = 0; // 데이터 추가시, 뒤쪽에 데이터가 들어갈 자리를 가리킴
    private T[] dataArray; // 데이터 저장 공간 (실제 사용할 공간보다 하나 많이 설정)
    private int length; // dataArray 길이 (매번 dataArray 호출하는거보다 생성할 때 저장하는게 나을거 같아서)

    // constructor
    CirQueue(int queueLength) {
        this.dataArray = (T[]) new Object[queueLength + 1]; // dataArray Queue 공간보다 하나 많이 설정
        this.length = queueLength + 1; // dataArray 길이
    }

    // enqueue, if queue is full, throw Exception
    public boolean add(T element) throws Exception {

        // Queue가 다 차있을 때 (dataArray 가 하나 비어있을 때) 에러 발생
        if(front - rear == 1 || front - rear == -1 * (length - 1)){
            Exception exception = new IllegalStateException();
            throw exception;
        }

        dataArray[rear] = element; // 데이터 추가
        rear = (rear + 1) % length; // rear 를 한칸 뒤로 미룸
        return true; // 데이터 추가 성공시 true 반환
    }
    // enqueue, if queue is full, return false
    public boolean offer(T element)  {

        // Queue가 다 차있을 때 (dataArray 가 하나 비어있을 때) false 반환
        if(front - rear == 1 || front - rear == -1 * (length - 1)){
            return false;
        }
        dataArray[rear] = element; // 데이터 추가
        rear = (rear + 1) % length; // rear 를 한칸 뒤로 미룸
        return true; // 데이터 추가 성공시 true 반환
    }

    // dequeue and return element
    public T poll() {

        // dataArray가 비어있을 때, null 반환
        if (front == rear) return null;

        T positionData = dataArray[front]; // 맨 앞 데이터를 가져옴
        dataArray[front] = null; // 꺼낸 데이터 자리을 비움

        front = (front + 1) % length; // 맨 앞을 가리키는 변수를 하나 뒤로 미룸

        return positionData; // 꺼낸 데이터를 반환
    }

    // dequeue
    public void remove() {
        if (front == rear) return; // dataArray가 비어있을 때, null 반환

        dataArray[front] = null; // 맨 앞에 해당하는 데이터를 비움

        front = (front + 1) % length; // 맨 앞을 가리키는 변수를 하나 뒤로 미룸
    }

    // initialized
    public void clear() {
        // arrayList 초기화
        for(int i=0; i < dataArray.length; i++){
            dataArray[i] = null;
        }
        front = 0; // 맨 앞 index를 가리키는 변수 초기화
        rear = 0; // 데이터 추가할 index를 가리키는 변수 초기화
    }
}

• 참고자료
  • 원형 큐