자료구조 - 스택, 큐 직접 구현(Stack, Queue)

 

1. 스택, 큐란?

 

이미 이전의 포스팅들에서 설명을 완료하였으므로 해당 포스팅의 링크를 아래와 같이 표시해두겠습니다.
간단히 설명하면 스택은 LIFO(Last-In, First-Out), 큐는 FIFO(First-In, First-Out) 방식을 취하는 자료구조이다.

hongjw1938.tistory.com/4?category=884192

자료구조(Java) - Collection Framework

 

아래에 각각의 자료구조를 배열 또는 리스트 기반으로 직접 구현한 코드를 작성하였다. 이전의 ArrayList / LinkedList에서 기 작성하긴 했으나 별도로 정리하여 한 토픽으로 쓰는 것이 좋을 것 같아 별도 작성하였다.

 

 

2. 배열 기반 직접 구현하기

 

배열을 기반으로 스택, 큐를 구현한다면 각각의 장점과 단점이 있다.

스택은 마지막에 넣은 자료를 먼저 빼는 구조이기 때문에 자료를 넣고 뺄 때 기존의 자료들의 위치를 변경할 필요가 없다. 단순히 넣고 빼면 되므로 삽입/추출 시, O(1) 수준의 시간복잡도를 요구한다.

큐는 그와 반대로 먼저 넣은 자료를 먼저 빼는 구조이므로 자료를 넣고 뺄 때, 기존에 삽입된 자료들의 위치를 변경해야 한다. 따라서 삽입/추출 시, O(n) 수준의 시간복잡도가 요구된다.

하지만 두 경우에 모두 내부의 데이터 탐색 시, 위치를 알고 있다면 O(1)의 시간이 소요된다. 

 

아래의 코드는 기존의 ArrayList를 통해 구현한 것을 그대로 사용한 것인데 공통 사용 method와 스택 / 큐에서 사용하는 method를 별도 표시하였다.

package com.test;

// 배열 기반의 Stack 및 큐를 동시 구현
public class ArrayBasedStackAndQueue<T>{
    // 배열을 기반으로 하는 자료구조

    private Object element[];
    private int size;
    private int capacity;
    private static final int default_capacity = 10;

    public ArrayBasedStackAndQueue(){
        element = new Object[default_capacity];
        capacity = default_capacity;
        this.size = 0;
    }

    public ArrayBasedStackAndQueue(int capacity){
        if(capacity == 0){
            element = new Object[]{};
        } else {
            element = new Object[capacity];
        }
        this.capacity = capacity;
        this.size = 0;
    }

    private void sizeUp(){
        if(this.capacity == 0){
            element = new Object[default_capacity];
            this.capacity = default_capacity;
        } else {
            Object temp[] = new Object[this.capacity*2];
            System.arraycopy(this.element, 0, temp, 0, size);
            this.capacity *= 2;
        }
    }

    // Data를 특정 index 값에 집어 넣는 함수
    public boolean add(int index, T data){
        if(index < 0 || index > this.size){
            throw new IllegalArgumentException();
        }
        if(this.element.length == this.size){
            this.sizeUp();
        }
        for(int i=this.size-1; i >= index; i--){
            element[i+1] = element[i];
        }
        element[index] = data;
        this.size++;
        return true;
    }

    // Data를 앞에서 집어 넣는 함수 - Queue에서 사용
    public boolean addFront(T data){
        return this.add(0, data);
    }

    // Data를 뒤에서 집어 넣는 함수 - Stack에서 사용
    public boolean addBack(T data){
        return this.add(this.size, data);
    }

    public T poll(int index){
        if(index < 0 || index > this.size){
            throw new IllegalArgumentException();
        }
        if(this.element.length == this.size){
            this.sizeUp();
        }
        T temp = (T) this.element[index];
        for(int i=index+1; i < this.size; i++){
            this.element[i-1] = this.element[i];
        }
        this.element[size-1] = null;
        this.size--;

        return temp;
    }

    // Data를 앞에서 빼내는 경우 - Queue에서 사용
    public T pollFront(){
        return poll(0);
    }

    // Data를 뒤에서 빼내는 경우 - Stack에서 사용
    public T pollBack(){
        return poll(this.size-1);
    }

    // 특정 index에 있는 값을 참조하고 싶은 경우
    public T get(int index){
        if(index < 0 || this.size <= index){
            throw new IllegalArgumentException();
        }
        return (T) this.element[index];
    }

    // 제일 첫 데이터를 참조 하는 경우 - Queue에서 사용
    public T peekFront(){
        return get(0);
    }

    // 제일 끝 데이터를 참조하는 경우 - Stack에서 사용
    public T peekBack(){
        return get(this.size-1);
    }

    // 현재 배열이 비어있는지 확인하고 싶은 경우
    public boolean isEmpty(){
        return this.size == 0;
    }

    // 현재 배열의 크기를 알고 싶은 경우
    public int getSize(){
        return this.size;
    }

    // 현재 배열을 비우고 싶은 경우
    public void clear(){
        this.element = new Object[this.capacity];
    }

    // Iterator 가져오기
    public Iterator getIterator(){
        return new Iterator();
    }

    class Iterator{
        // 현재 탐색할 순서를 가리키는 Index
        private int nextIndex = 0;

        // next 값이 있는지 확인하는 메소드
        public boolean hasNext(){
            return nextIndex < getSize();
        }

        // next 값을 반환하는 메소드
        public T next(){
            if(!hasNext()){
                throw new IllegalArgumentException();
            }
            return (T)element[nextIndex++];
        }

        // previous 값이 있는 확인하는 메소드
        public boolean hasPrevious(){
            return size > 0 && nextIndex > 0;
        }

        // previous 값을 반환하는 메소드
        public T previous(){
            return (T)element[--nextIndex];
        }

        // 현재 index에 element를 추가한다.
        public boolean add(T element){
            return ArrayBasedStackAndQueue.this.add(nextIndex++, element);
        }

        // 현재 index의 element를 제거한다.
        public T poll(){
            T temp =  ArrayBasedStackAndQueue.this.poll(nextIndex-1);
            nextIndex--;
            return temp;
        }
    }
}

 

 

3. 리스트 기반 직접 구현하기

 

리스트를 기반으로 스택, 큐를 구현해도 각각의 장점과 단점이 있다.

스택은 마지막에 넣은 자료를 삽입 혹은 추출 시, 기존의 마지막에 넣어져 있던 자료(tail)와의 상호 prev/next 관계만 바꾸어주면 되므로 삽입/추출 시, O(1) 수준의 시간복잡도를 요구한다.

큐는 먼저 넣은 자료를 삽입 혹은 추출 시, 기존의 가장 앞에 넣어져 있던 자료(head)와의 상호 prev/next 관계만 바꾸어주면 되므로 삽입/추출 시, O(1) 수준의 시간복잡도가 요구된다.

하지만 두 경우에 모두 내부의 데이터 탐색에는 O(n)의 시간이 소요된다. 

 

아래의 코드는 기존의 LinkedList를 통해 구현한 것을 그대로 사용한 것인데 공통 사용 method와 스택 / 큐에서 사용하는 method를 별도 표시하였다.

package com.test;

import java.util.NoSuchElementException;

public class LinkedListBasedStackAndQueue<T> {
    private int size;
    private Node<T> head;
    private Node<T> tail;

    // Head 부분에 노드 추가하기 - Queue에서 사용
    public boolean addFirst(T data){
        Node<T> node = new Node<>(data);

        node.next = this.head;
        node.previous = this.tail;

        // 기존에 아무것도 없었다면
        if(this.size == 0){
            this.tail = node;

            // 기존에 Node가 하나라도 있었다면
        } else {
            this.head.previous = node;
            this.tail.next = node;
        }
        this.head = node;
        this.size++;
        return true;
    }

    // Tail 부분에 노드 추가하기 - Stack에서 사용
    public boolean addLast(T data){
        Node<T> node = new Node<>(data);

        node.previous = this.tail;
        node.next = this.head;
        // 기존에 Node가 없었다면
        if(this.size == 0){
            this.head = node;

          // 기존에 Node가 하나라도 있었다면
        } else {
            this.head.previous = node;
            this.tail.next = node;
        }
        this.tail = node;
        this.size++;
        return true;
    }

    // 중간에 노드 추가하기
    // idx는 0번부터 시작한다고 가정
    public boolean add(T data, int idx){
        if(idx == 0){
            addFirst(data);
        } else if(idx >= this.size){
            addLast(data);
        } else {
            Node<T> newNode = new Node<>(data);
            Node<T> current = this.head;
            for(int i=0; i < idx; i++){
                current = current.next;
            }
            newNode.next = current.next;
            current.next.previous = newNode;

            current.next = newNode;
            newNode.previous = current;
            this.size++;
        }
        return true;
    }

    // Head Node 빼서 반환하기
    // Head를 바꿔주고 기존 tail과 바뀐 head가 서로 가리키도록 변경
    // Queue에서 사용
    public Node<T> pollFirst(){
        // 기존에 Node가 없었다면
        if(this.size == 0){
            throw new NoSuchElementException();
        }
        Node<T> retNode = this.head;
        
        // 현재 1개밖에 없다면 모두 null로 만들고 반환
        if(this.size == 1){
            this.head = null;
            this.tail = null;
            this.size--;
            return retNode;
        }
        this.head = retNode.next;
        this.head.previous = this.tail;
        this.tail.next = this.head;
        this.size--;
        return retNode;
    }

    // Tail Node 빼서 반환하기
    // Tail을 바꿔주고 기존 Head와 바뀐 Tail이 서로 가리키도록 변경
    // Stack에서 사용
    public Node<T> pollLast(){
        // 기존에 Node가 없었다면
        if(this.size == 0){
            throw new NoSuchElementException();
        }
        Node<T> retNode = this.tail;
        
        // 현재 1개밖에 없다면 모두 null로 만들고 반환
        if(this.size == 1){
            this.head = null;
            this.tail = null;
            this.size--;
            return retNode;
        }
        this.tail = retNode.previous;
        this.head.previous = this.tail;
        this.tail.next = this.head;
        this.size--;

        return retNode;
    }

    // 중간 Node 빼서 반환하기
    public Node<T> poll(int idx){
        if(idx == 0){
            return pollFirst();
        } else if(idx >= this.size-1){
            return pollLast();
        } else {
            Node<T> target = head;
            for(int i=0; i < idx; i++){
                target = target.next;
            }
            target.previous.next = target.next;
            target.next.previous = target.previous;

            return target;
        }
    }

    // 현재 Node의 개수
    public int size(){
        return this.size;
    }

    // 현재 비어있는지 확인인
    public boolean isEmpty(){
        return this.size == 0;
    }

    // Head값만 참조해보기
    public Node<T> peek(){
        return this.head;
    }

    // Iterator 반환하기
    public Iterator getIterator(){
        return new Iterator();
    }

    public static class Node<T>{
        private T data;
        private Node<T> next;
        private Node<T> previous;

        public Node(T data){
            this.data = data;
        }

        public void setData(T data){
            this.data = data;
        }

        public T getData(){
            return this.data;
        }

        public Node<T> getNext() {
            return this.next;
        }

        public Node<T> getPrevious(){
            return this.previous;
        }
    }

    class Iterator{
        // 현재 탐색할 순서를 가리키는 Index
        private int nextIndex;
        private int prevIndex;
        private Node<T> next;
        private Node<T> previous;
        private Node<T> lastReturned;

        public Iterator(){
            next = head;
            previous = null;

            nextIndex = 0;
            prevIndex = -1;
        }
        // next 값이 있는지 확인하는 메소드
        public boolean hasNext(){
            return this.nextIndex < size();
        }

        // next 값을 반환하는 메소드
        public Node<T> next(){
            if(!hasNext()){
                throw new NoSuchElementException();
            }
            if(nextIndex >= 1){
                prevIndex = nextIndex - 1;
                previous = lastReturned;
            }

            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned;
        }

        // previous 값이 있는 확인하는 메소드
        public boolean hasPrevious(){
            return prevIndex >= 0;
        }

        // previous 값을 반환하는 메소드
        public Node<T> previous(){
            if(!hasPrevious()){
                throw new NoSuchElementException();
            }
            lastReturned = previous;
            previous = previous.previous;
            next = lastReturned.next;

            nextIndex--;
            prevIndex--;
            return lastReturned;
        }
    }
}

 

 

 

오류가 있는 부분은 댓글로 남겨주시면 반영하겠습니다. 감사합니다.