[Java] Stack & Queue

스택(Stack)

• 한 쪽 끝에서만 item(항목)을 삭제하거나 새로운 item을 저장하는 자료구조
• 새 item을 저장하는 연산 : push
• Top item을 삭제하는 연산 : pop
• 후입 선출(Last-In First-Out, LIFO) 원칙 하에 item의 삽입과 삭제 수행

구현

배열로 구현한 ArrayStack 클래스

import java.ut8il.EmptyStackException;
public class ArrayStack<E> {
    private E S[];  // 스택을 위한 배열
    private int top;  // 스택의 top 항목의 배열 원소 인덱스
    // 스택 생성자
    public ArrayStack() {
        s = (E[]) new Object[1];  // 초기 크기 1인 배열 생성
        top = -1;
    }
    public int size() { return top + 1; }  // 스택에 있는 항목 수 리턴
    public boolean isEmpty() { return (top == -1);}  // 스택이 empty이면 true 리턴
    // peek(), push(), pop(), resize() 메소드 선언
    public E peek() {  // 스택의 top 인덱스 내용 리턴
        if (isEmpty()) throw new EmptyStackException();
        return s[top];
    }
    public void push(E newItem) {  // push 연산
        if (size() == s.length)  // 스택 크기 2배 크기로 확장
            resize(2 * s.length);  // 새 항목 push
        s[++top] = newItem;
    }
    public E pop() {  // pop 연산
        if (isEmpty()) thrwo new EmptyStackException();
        E item = s[top];
        s[top--] = null;
        if (size() > 0 && size() == s.length/4)  // 스택 크기 1/2배 크기로 축소
            resize(s.length/2);
        return item;
    }
    public void resize(int newSize) {  // 배열 크기 조절
        Object[] t = new Object[newSize];  // newSize 크기의 새로운 배열 t 생성
        for (int i = 0; i < size(); i++)
            t[i] = s[i];  // 배열 s를 배열 t로 복사
        s = E[]) t;  // 배열 t를 배열 s로
    }
}

단순연결리스트로 구현한 ListStack 클래스

public class Node <E> {
    private E item;
    private Node<E> next;
    // 생성자
    public Node(E newItem, Node<E> node) {
        item = newItem;
        next = node;
    }
    // get과 set 메소드
    public E getItem() {return item;}
    public Node<E> getNext() {return next;}
    public void setItem(E newItem) {item = newItem;}
    public void setNext(Node<E> newNext) {next = newNext;}
}

import java.util.EmptyStackException;
public class ListStack <E> {
    private Node<E> top;  // 스택 top 항목 가진 Node 가리킴
    private int size;  // 스택 항목 수
    // 스택 생성자
    public ListStack() {
        top = null;
        size = 0;
    }
    public int size() {return size;}  // 스택 항목수 리턴
    public boolean isEmpty() {return size == 0;}  // 스책 empty면 true 리턴
    // peek(), push(), pop() 메소드 선언    
    public E peek() {  // 스택의 top 인덱스 내용 리턴
        if (isEmpty()) throw new EmptyStackException();
        return top.getItem();
    }
    public void push(E newItem) {  // push 연산
        Node newNode = new Node(newItem, top);
        top = newNode;
        size++;
    }
    public E pop() {  // pop 연산
        if (isEmpty()) thrwo new EmptyStackException();
        E topItem = top.getItem();
        top = top.getNext();
        size--;
        return topItem;
    }
}

스택의 응용

컴파일러의 괄호 짝 맞추기

왼쪽 괄호는 스택에 push, 오른쪽 괄호를 읽으면 pop 수행

• pop된 왼쪽 괄호와 바로 읽었던 오른쪽 괄호가 다른 종류이면 에러 처리, 같은 종류이면 다음 괄호 읽음
• 모든 괄호 읽은 뒤 에러가 없고 스택이 empty이면, 괄호들이 정상적으로 사용
• 모든 괄호를 처리한 후 스택이 empty가 아니면 짝이 맞지 않는 괄호가 스택에 남은 것이므로 에러 처리

회문(Palindrome) 검사하기

전반부의 문자들을 스택에 push한 후, 후반부의 각 문자를 차례로 pop한 문자와 비교

• 회문 검사하기는 주어진 스트링 앞부분 반을 차례대로 읽어 스택에 push한 후 문자열의 길이가 짝수면
  • 뒷부분 문자 1개를 읽을 때마다 pop하여 읽어들이 문자와 pop된 문자를 비교하는 과정 반복 수행
  • 만약 마지막 비교까지 두 문자가 동일하고 스택이 empty가 되면, 입력 문자열은 회문
• 문자열 길이가 홀수 인 경우, 주어진 스트링의 앞부분 반을 차례로 읽어 스택에 push한 후, 중간문자를 읽고 버린다. 이 후 짝수 경우와 동일하게 비교 수행

후위표기법(Postfix Notation) 수식 계산하기

중위표기법(Infix Notation) 수식의 후위표기법 변환

수행시간

• 배열로 구현한 스택의 push와 pop 연산은 각각 O(1) 시간 소요
• 배열 크기를 확대 또는 축소시키는 경우에 스택의 모든 item들을 새 배열로 복사해야 하므로 O(N) 시간이 소요
  • 상각분석 : 각 연산의 평균 수행시간은 O(1) 시간
• 단순연결리스트로 구현한 스택의 push와 pop 연산은 각각 O(1) 시간이 걸리는데, 연결리스트의 앞 부분에서 노드를 삽입하기 삭제하기 때문이다.
• 배열과 단순연결리스트로 구현된 스택의 장단점은 2장으 ㅣ리스트를 배열과 단순연결리스트로 구현하였을 때 장단점과 동리

큐(Queue)

• 큐(Queue) : 삽입과 삭제가 양 끝에서 각각 수행되는 자료 구조
• 일상생활 관공서, 은행, 우체국, 병원 등에서 번호표를 이용한 줄서기가 대표적인 큐
• 선입 선출(First-In First-Out, FIFO) 원칙 하에 item의 삽입과 삭제 수행
• 큐를 배열로 구현하는 경우, 큐에서 삽입과 삭제를 거듭하게 되면 item들은 뒤에서 삽입되고 삭제는 앞에서 일어나기 때문에 큐의 item들이 배열의 오른쪽 부분으로 편중되는 문제가 발생

문제 해결 방안

항목 이동 해결 방안

1. 큐의 item들을 배열의 앞부분으로 이동
   • 수행시간이 큐에 들어있는 item의 수에 비례하는 단점
2. 배열을 원형으로, 즉 배열의 마지막 원소가 첫 원소가 맞다아 있다고 여김
   • 배열의 앞뒤가 맞닿아 있다고 생각하기 위해 배열의 rear 다음의 비어있는 원소의 인덱스
     rear = (rear + 1) % N
   • 여기서 N은 배열의 크기
   • 큐의 마지막 item을 삭제한 후에 큐가 empty임에도 불구하고 rear는 삭제된 item을 가리키고 있어 front와 rear가 서로 다른 item을 가리키고 있는 문제가 발생

큐가 empty일 때 문제 해결 방안

1. item을 삭제할 때마다 큐가 empty가 되는지 검사하고, 만일 empty 되면, front = rear = 0을 만듦
   • 삭제할 때마다 empty 조건을 검사하는 것은 프로그램 수행의 효율성 저하
2. front를 실제의 가장 앞에 있는 item의 바로 앞의 비어있는 원소를 가리키게 한다.
   • 배열의 크기가 N이라면 실제로 N-1개의 공간만 item들을 저장하는데 사용
   • 방법 1에서 item 삭제할 때마다 조건을 한번 더 검사하는 것은 ‘이론적인 수행시간’을 증가시키지는 않으나, 일반적으로 프로그램이 수행될 때 조건을 검사하는 프로그램의 실제 실행시간은 검사하지 않는 프로그램보다 더 오래 소요됨
   • wmr Empty가 되면 front == rear가 된다.

구현

큐를 배열로 구현한 ArrayQueue 클래스

import java.util.NoSuchElementException;
public class ArrayQueue <E> {
    private E[] q;  // 큐를 위한 배열
    private int frotn, rear, size;
    // 큐 생성자
    public ArrayQueue() {
        q = (E[]) new Object[2];  // 초기 크기 2인 배열 생성
        front = rear = size = 0
    }
    public int size() {return size;}  // 큐에 있는 항목 수 리턴
    public boolean isEmpty() {return (size == 0;)}  // 큐가 empty이면 true 리턴
    // add(), remove(), resize() 메소드 선언
    public void add(E newItem) {
        if ((rear + 1) % q.length == front)  // 비어있는 원소가 1개뿐인 경우 (큐가 full)
            resize(2 * q.length);  // 큐 크기 2배 확장
        rear = (rear + 1) % q.length;
        q[rear] = newItem;  // 새 항목을 add
        size++:
    }
    public E remove() {
        if (isEmpty()) throw new NoSuchElementException();
        front = (front + 1) % q.length;
        E item = q[front];
        q[front] = null;  // null로 만들어 가비지 컬렉션되도록
        size--;
        if (size > 0 && size == q.length / 4)
            resize(q.length/2);  // 큐 1/2 크기로 축소
        return item; 
    }
    public void resize(int newSize) {
        Object[] t = new Object[newSize];
        // 원형 큐를 만들기 위해 비워있는 부분 front를 만들어야해서 1부터 시작
        for (int i = 1, j = front + 1; i < size + 1; i++, j++) {
            t[i] = q[j % q.length];
        }
        front = 0;
        rear = size;
        q = (E[]) t;
    }
}    

큐를 연결리스트로 구현한 ListQueue 클래스

import java.util.NoSuchElementException;
public class ListQueue <E> {
    private Node<E> front, rear;
    private int size;
    public ListQueue() {
        front = rear = null;
        size = 0;
    }
    public int size() {return size;}
    public boolean isEmpty() {return size() == 0}
    // add(), remove() 메소드 선언
    public void add (E newItem) {
        Node newNode = new Node(newItem, null);
        if (isEmpty()) front = newNode;
        else rear.setNext(newNode);
        rear = newNode;
        size++;
    }
    public E remove() {
        if (isEmpty() throw new NoSuchElementException();
        E frontItem = front.getItem();
        front = front.getNext();
        if (isEmpty()) rear = null;
        size--;
        return frontItem;
    }
}

수행시간

• 배열로 구현한 큐의 add와 remove 연산은 각각 O(1) 시간이 소요된다.
• 배열 크기를 확대 또는 축소시키는 경우에 큐의 모든 item들을 새 배열로 복사해야 하므로 O(N) 시간 소요된다.
• 상각분석 : 평균 수행시간은 O(1)
• 단순연결리스트로 구현한 큐의 add와 remove 연산은 각각 O(1) 시간, 삽입 또는 삭제 연산이 rear와 front로 인해 연결리스트의 다른 노드들을 일일이 방문할 필요가 없기 때문이다.
• 배열과 단순연결리스트로 구현한 큐의 장단점은 리스트를 배열과 단순연결리스트로 구현하였을 때 장단점과 동일하다.

데크(Deque)

• 데크(Double-ended Queue, Deque) : 양쪽 끝에서 삽입과 삭제를 허용하는 자료구조
• 데크는 스택과 큐 자료구조를 혼합한 자료구조
• 따라서 데크는 스택과 큐를 동시에 구현하는데 사용
• 데크를 이중연결리스트로 구현하는 것이 편리

응용

• 스크롤(Scroll)
• 문서 편집기 등의 undo 연산
• 웹 브라우저의 방문 기록 등
  • 웹브라우저 방문 기록의 경우, 최근 방문한 웹페이지 주소는 앞에 삽입하고, 일정 수 새 주소들이 앞쪽에서 삽입되면 뒤에서 삭제가 수행

수행시간

• 데크를 배열이나 이중연결리스트로 구현한 경우, 스택과 큐의 수행시간과 동일
• 양 끝에서 삽입과 삭제가 가능하므로 프로그램이 다소 복잡
• 이중연결리스트로 구현한 경우는 더 복잡함
• 자바 SE7은 java.util 패키지에서 Deque 인터페이스를 제공, Queue 클래스에서 상속됨

[출처] 경기대학교|소프트웨어중심대학교