[자료구조/알고리즘] - 스택, 큐

janjanee·2021년 4월 7일
queuestack알고리즘자료구조
0

자료구조/알고리즘

목록 보기
7/10

1. 스택 (stack)

데이터를 일시적으로 저장하기 위한 자료구조로, 가장 나중에 넣은 데이터를 가장 먼저 꺼낸다.
(후입선출 - Last In First Out)

스택 - 용어 및 메소드

  • top - 스택의 가장 윗부분 (꼭대기)
  • bottom - 스택의 가장 아랫부분 (바닥)
  • push(item) - 데이터를 넣는 작업
  • pop() - 데이터를 꺼내는 작업
  • peek() - 스택의 가장 위에 있는 항목 조회

스택 - 예시

배열 스택

  • push(7) → 배열의 top 자리에 7을 넣고, top을 한칸 뒤로 이동
  • pop() → top을 한칸 앞으로 이동 후, 그 값을 리턴

연결리스트 스택

  • push(7) → 노드[7]을 생성 후, 노드[7] next를 top(노드[2])으로 한다. top에 노드[7]를 대입한다.
  • pop() → top(노드[7])에 있던 data를 가져온다. top을 top의 next(노드[2])로 변경한다.
    앞의 data를 반환한다.

스택 구현 - Java 코드

int형 배열로 구현

public class IntArrayStack {

    private int max;    //  스택용량
    private int top;    //  스택 포인터 top (스택에 쌓여있는 데이터 수)
    private int[] stk;  //  스택 본체

    public IntArrayStack(int capacity) {
        top = 0;
        max = capacity;
        stk = new int[max];
    }

    /** 스택에 데이터를 push */
    public void push(int x) {
        if (isFull())
            throw new OverflowStackException();
        stk[top++] = x;
    }

    /** 스택의 꼭대기(top)에서 데이터를 pop */
    public int pop() {
        if (isEmpty())
            throw new EmptyStackException();
        return stk[--top];
    }

    /** 스택 꼭대기(top)에 있는 데이터 조회 */
    public int peek() {
       if (isEmpty())
            throw new EmptyStackException();
        return stk[top - 1];
    }

    /** 스택이 비어 있는지 여부 */
    public boolean isEmpty() {
        return top <= 0;
    }

    /** 스택이 가득 찼는지 여부 */
    public boolean isFull() {
        return top >= max;
    }
}

int형 연결리스트 구현

public class Node {

    private int data;
    private Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }

   // getter, setter

}
public class IntLinkedListStack {

    private Node top;
    private int size;

    /** 스택에 데이터를 push */
   public void push(int x) {

        Node node = new Node(x);
        node.setNext(top);
        top = node;
        size++;

    }

    /** 스택의 꼭대기(top)에서 데이터를 pop */
    public int pop() {
        if (isEmpty())
            throw new EmptyStackException();

        int result = top.getData();
        top = top.getNext();
        size--;
        return result;
    }

    /** 스택 꼭대기(top)에 있는 데이터 조회 */
    public int peek() {
        if (isEmpty())
            throw new EmptyStackException();

        return top.getData();
    }

    /** 스택이 비어 있는지 여부 */
    public boolean isEmpty() {
        return size == 0;
    }

}

배열 → 검색 빈번, 등록/수정 적음
연결리스트 → 등록/수정 빈번, 검색 적음

스택의 사용 사례

  • 재귀 알고리즘
    • 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다.
    • 재귀함수를 빠져 나와 퇴각 검색(backtrack)을 할 때 스택에 넣어 두었던 임시 데이터를 꺼낸다.
  • 메소드 호출 스택
  • 웹 브라우저 방문기록 (뒤로가기)
  • 실행 취소(undo)
  • 역순 문자열 만들기
  • 후위 표기법 계산
  • 수식의 괄호 검사

2. 큐 (queue)

데이터를 일시적으로 저장하기 위한 자료구조로, 가장 먼저 넣은 데이터를 가장 먼저 꺼낸다.
(선입선출 - First In First Out)

큐 - 용어 및 메소드

  • front - 데이터를 꺼내는 쪽(맨 앞)
  • rear - 데이터를 넣는 쪽(맨 뒤)
  • enqueue(item) - 데이터를 넣는 작업
  • dequeue() - 데이터를 꺼내는 작업
  • peek() - 큐의 가장 앞에 있는 항목 조회

큐 - 예시

배열 큐

  • enqueue(7) → 배열의 rear 자리에 7을 넣고, rear를 한칸 뒤로 이동
  • dequeue() → 현재 front의 값을 반환 후, front를 한칸 뒤로 이동
  • 문제점 해결 → 배열의 데이터를 전부 앞으로 옮겨주거나, 링 버퍼

배열 큐 - 링 버퍼, 원형 큐

연결리스트 큐

  • enqueue(7) → 노드[7]을 생성 후, 현재 rear의 next값을 노드[7]로 변경. 그 다음 rear를 노드[7]로 변경
  • dequeue() → front 의 노드[3] data를 저장 후, front를 front.next(노드[5])로 변경. data를 반환

큐 구현 - Java 코드

int형 배열로 구현

public class IntArrayQueue {

    private int max;    //  큐의 용량
    private int front;  //  첫 번째 요소 커서
    private int rear;   //  마지막 요소의 하나 뒤의 인덱스 커서
    private int size;   //  현재 데이터 수
    private int[] que;  //  큐 본체

    public IntArrayQueue(int capacity) {
        size = front = rear = 0;
        max = capacity;
        que = new int[max];
    }

    /** 큐에 데이터를 enQueue */
	public void enQueue(int x) {
        if (isFull())
            throw new OverflowQueueException();
        que[rear] = x;
        rear = (rear + 1) % max;  //  원형 큐*
        size++;

    }

    /** 큐의 맨 앞에서 데이터를 deQueue */
    public int deQueue() {
        if (isEmpty())
            throw new EmptyQueueException();

        int x = que[front];
        front = (front + 1) % max;  //  원형 큐
        size--;
        return x;
    }

    /** 큐의 맨 앞의 데이터 조회 */
    public int peek() {
        if (isEmpty())
            throw new EmptyQueueException();
        return que[front];
    }

    /** 큐가 비었는지 여부 */
    public boolean isEmpty() {
        return size <= 0;
    }

    /** 큐가 가득찼는지 여부 */
    public boolean isFull() {
        return size >= max;
    }
}

int형 연결리스트 구현

public class IntLinkedListQueue {

    private Node front;
    private Node rear;

    private int size;

    /** 큐에 데이터를 enQueue */
    public void enQueue(int x) {
        Node node = new Node(x);

        if (rear != null)
            rear.setNext(node);

        rear = node;

        if (front == null)
            front = rear;

        size++;
    }

    /** 큐의 맨 앞에서 데이터를 deQueue */
    public int deQueue() {
        if (isEmpty())
            throw new EmptyQueueException();

        int result = front.getData();
        front = front.getNext();
        size--;
        return result;

    }

    /** 큐의 맨 앞의 데이터 조회 */
    public int peek() {
        if (isEmpty())
            throw new EmptyQueueException();

        return front.getData();
    }

    /** 큐가 비었는지 여부 */
    public boolean isEmpty() {
        return size == 0;
    }
}

배열 → 검색 빈번, 등록/수정 적음
연결리스트 → 등록/수정 빈번, 검색 적음

큐의 사용 사례

  • 너비 우선 탐색(BFS, Breadth-First-Search) 구현
    • 처리해야할 노드의 리스트를 저장하는 용도로 큐를 사용
  • 캐시 구현
  • 우선순위가 같은 작업 예약 (인쇄 대기열)
  • 선입선출이 필요한 대기열 (티켓 카운터)
  • 콜센터 고객 대기시간
  • 프린터의 출력 처리
  • 은행 업무
  • 프로세스 스케쥴링
  • 네트워크 패킷 처리

References

profile
janjanee
얍얍 개발 펀치
이전 포스트

[자료구조/알고리즘] - 퀵정렬, 힙정렬, 위상 정렬

다음 포스트

[자료구조/알고리즘] - 트리, 힙

0개의 댓글