[Panda] 3. 스택과 큐

알고리즘 스터디 3주차 내용정리

 

스택콰 큐는 배열에서 발전된 형태의 자료구조이다.
배열은 프로그램 언어 기능 중에서 가장 많이 사용되며, 동일한 형태의 자료를 연속해서 저장하는 구조를 가진다.
스택(Stack)과 큐(Queue)는 구조는 비슷하지만 처리방식이 다르다는 특징을 가진다.

JAVA의 컬렉션 프레임워크는 LIFO(후입선출) 자료구조를 제공하는 스택 클래스와 FIFO(선입선출) 자료구조를 제공하는 큐 인터페이스를 제공한다.

스택 자료구조

스택(Stack)은 스택을 쌓아올리 듯, 데이터를 쌓아올리는 구조이다.
삽입과 삭제 연산이 데이터가 입력되는 순서대로 쌓고 나중에 들어온 것부터 먼저 사용하는 후입선출(LIFO; Last in First out) 형식으로 이루어지며 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있다.
실제로 top부분에서면 연산이 일어난다.

스택에 데이터를 넣는 것을 'PUSH'라 하며, 새 값이 스택에 들어가면 top이 새 값을 가리킨다.
데이터를 꺼내는 것을 'POP'이라고 하는데, POP은 top이 가리키는 값을 스택에서 빼게 되어있으므로 결과적으로는가장 마지막에 넣었던 값이 나오게 된다.

• top: 삽입과 삭제가 일어나는 위치
• push: top의 위치에 새로운 데이터를 삽입하는 연산
• pop: top의 위치에 현재 있는 데이터를 삭제하고 확인하는 연산
• peek: top 위치에 현재 있는 데이터를 단순 확인하는 연산

 

자바에서 Stack 객체를 생성하는 방법

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

 

자바에서 Stack 구조을 사용하는 예시

public class Coin {
    private int value;

    public Coin(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }
}

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<Coin> coinBox = new Stack<Coin>();

        coinBox.push(new Coin(100));
        coinBox.push(new Coin(50));
        coinBox.push(new Coin(500));
        coinBox.push(new Coin(10));

        while(!coinBox.isEmpty()){
            Coin coin = coinBox.pop();
            System.out.println("꺼내온 동전: " + coin.getValue() + "원");
        }
    }
}

위 코드에서 동전은 후입선출 즉 10원, 500원, 50원, 100원 순으로 출력된다.

 

스택 자료구조 용도

스택은 대표적으로 프로그램을 수행할 때 사용한다.
주 프로그램에서 함수A를 호출하면 주 프로그램 위에 함수A가 쌓이고, 함수A 수행 중에 함수B가 호출되면, 함수A 위에 함수B가 스택처럼 쌓이게 된다.

함수B의 실행이 완료되면, 함수A가 실행되고, 함수A의 실행이 돤료되면 주 프로그램의 실행이 시작된다.

 

스택은 주로 우선 탐색, 백트래킹 종류에 주로 사용된다.

재귀하뭇 알고리즘 원리와 매우 유사하기 때문에 실제로 구현 시 재귀함수를 많이 쓰긴한다.

큐보다 구조가 독특하기 때문에 응용하는 문제가 많이 출제된다.

 

재귀 함수 알고리즘과 스택의 관계

: 재귀함수가 호출될 때마다 해당 호출의 실행 정보는 스택에 저장된다.

 

재귀함수 호출은 함수가 자신을 다시 호출하는 것을 의미한다.

종료 조건을 만족할 때까지 자기 자신을 호출하며 종료 조건이 없으면 무한한 재귀 호출이 발생할 수 있다. 반복적인 작업이나 자료구조를 다룰 때, 순환적인 문제를 해결할 때 사용하면 좋다.

 

재귀함수를 호출하게 되면 현재 함수의 실행을 일시 중지하고 새로운 함수의 호출을 처리하기 위한 메모리 공간이 할당되어야 한다. 재귀함수는 자신을 호출할 때마다 현재 상태 즉 호출 정보(매개변수, 지역 변수 등)를 스택 프레임이라고 부르는 메몰기 공간에 저장한다.

재귀함수의 이러한 반복적인 호출은 스택에 여러프레임을 쌓게 되고 종료조건이 만족되면 역순으로 스택 프레임을 해제하고 각각의 호출은 결과를 반환하고 메모리에서 제거된다.

 

 

큐 자료구조

큐는 데이터가 입력되면 입력되는 순서대로 쌓고, 먼저 들어온 것부터 먼저 사용하는, 선입선출(FIFO; First In First Out)로 이루어지는 자료구조이다.

스택과 다르게 먼저 들어온 데이터가 먼저 나가고, 삽잉과 삭제가 양방향에서 이루어지는 것을 확인할 수 있다.

새 값의 추가는 큐의 rear에서 이루어지고, 삭제는 큐의 front에서 이루어진다.

큐의 구현은 배열이나 LinkedList를 사용한다.

• rear: 큐에서 가장 끝 데이터를 가리키는 영역
• front: 큐에서 가장 앞의 데이터를 가리키는 영역
• add: rear부분에 새로운 데이터를 삽입하는 연산
• poll: front부분에 있는 데이터를 삭제하고 확인하는 연산
• peek: 큐의 맨 앞에 있는 데이터를 확인하는데 사용하는 연산

자바에서 큐는 인터테이스 형태로 제공한다.

큐 인터페이스에는 객체를 큐에 넣는 offer(E e)메소드와 큐에서 객체를 빼는 poll() 메소드가 정의되어 있다.

큐 인터페이스를 구현한 대표적인 클래스는 LinkedList이다.

 

LinkedList 객체를 Queue인터페이스 변수에 대입하는 법

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

 

자바에서 Queue 구조를 사용하는 예시

public class Message {
    public String command;
    public String to;
    
    public Message(String command, String to) {
        this.command = command;
        this.to = to;
    }
}

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

public class QueueExample {
    public static void main(String[] args){
        //Queue 컬렉션 생성
        Queue<Message> messageQueue = new LinkedList<>();

        //메세지 넣기
        messageQueue.offer(new Message("sendMail", "홍길동"));
        messageQueue.offer(new Message("sendSMS", "이지원"));
        messageQueue.offer(new Message("sendKakaotalk", "감자바"));

        //메세지를 하니씩 꺼내어 처리
        while(!messageQueue.isEmpty()) {
            Message message = messageQueue.poll();
            switch(message.command) {
                case "sendMail":
                    System.out.println(message.to + "님에게 메일을 보냅니다.");
                    break;
                case "sendSMS":
                    System.out.println(message.to + "님에게 SMS를 보냅니다.");
                    break;
                case "sendKakaotalk":
                    System.out.println(message.to + "님에게 카카오톡을 보냅니다.");
                    break;
            }
        }
    }
}

 

큐 자료구조의 용도

컴퓨터 안에 여러 개의 프로세스가 수행 중인데 새로운 프로세스가 수행되어야하는 경우 기존에 수행되던 프로세스 중에 가장 먼저 메모리에 올라온 프로세스가 아웃되고 새로운 프로세스를 메모리에 올리게 된다. 이경우에 운영체제는 현재 수행중인 프로세스를 큐의 형태로 관리하는 것이다.

 

또 윈도우 운영체제를 사용하는 컴퓨터에서 수행 중인 프로그램에 이벤트가 발생하면 발생한 이벤트가 큐에 저장되고, 수행 중인 프로그램이 큐에 저장된 것을 앞에서부터 읽어 와서 처리한다.(선입선출 구조) 이때도 큐가 사용된다.

 

알고리즘에서는 너비 우선 탬색에서 큐 구조를 자주 사용한다.

 

우선순위 큐

큐는 선입선출의 구조를 띄고 있지만 우선순위 큐는 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.

보통 힙(Heap)을 이용하여 구현한다. 힙은 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조이다. 여러개의 값중 최댓값 또는 최솟값을 찾아내는 연산이 빠르다.

큐 설정에 따라 front에 항상 최댓값 또는 최솟값이 위치한다.

우선순위 큐를 힙이 아니라 배열 또는 연결리스트를 이용하여 구현할 수 있는데 이때 힙보다 시간이 오래 걸린다.(힙이 제일 효율적인 방법)