대기 열 01 동적 배열 기반 대기 열

2455 단어
대기 열 인터페이스 큐
  • 인터페이스 Queue 로 대기 열 이라는 데이터 구 조 를 표시 하고 바 텀 에서 사용 하 는 데이터 구조 에 따라 구체 적 으로 다르다.
  • public interface Queue {
    
        int getSize();
        boolean isEmpty();
        void enqueue(E e);
        E dequeue();
        E getFront();
    
    }
    

    배열 큐
  • 동적 배열 대기 열, 바 텀 은 동적 배열 을 유지 했다.
  • E dequeue () 의 시간 복잡 도 는 O (n) 입 니 다. 동적 배열 array. removeFirst () 는 첫 번 째 요 소 를 삭제 할 때 모든 요 소 를 한 칸 앞으로 옮 겨 야 하기 때 문 입 니 다. 최 적 화 된 공간, 즉 순환 대기 열 이 있 습 니 다.
  • public class ArrayQueue implements Queue {
    
        private Array array;
    
        public ArrayQueue(int capacity){
            array = new Array<>(capacity);
        }
    
        public ArrayQueue(){
            array = new Array<>();
        }
    
        @Override
        public int getSize(){
            return array.getSize();
        }
    
        @Override
        public boolean isEmpty(){
            return array.isEmpty();
        }
    
        public int getCapacity(){
            return array.getCapacity();
        }
    
        @Override
        public void enqueue(E e){
            array.addLast(e);
        }
    
        @Override
        public E dequeue(){
            return array.removeFirst();
        }
    
        @Override
        public E getFront(){
            return array.getFirst();
        }
    
        @Override
        public String toString(){
            StringBuilder res = new StringBuilder();
            res.append("Queue: ");
            res.append("front [");
            for(int i = 0 ; i < array.getSize() ; i ++){
                res.append(array.get(i));
                if(i != array.getSize() - 1)
                    res.append(", ");
            }
            res.append("] tail");
            return res.toString();
        }
    
        public static void main(String[] args) {
            ArrayQueue queue = new ArrayQueue<>();
            for(int i = 0 ; i < 10 ; i ++){
                queue.enqueue(i);
                System.out.println(queue);
                if(i % 3 == 2){
                    queue.dequeue();
                    System.out.println(queue);
                }
            }
        }
    
    }
    

    출력:
    Queue: front [0] tail Queue: front [0, 1] tail Queue: front [0, 1, 2] tail Queue: front [1, 2] tail Queue: front [1, 2, 3] tail Queue: front [1, 2, 3, 4] tail Queue: front [1, 2, 3, 4, 5] tail Queue: front [2, 3, 4, 5] tail Queue: front [2, 3, 4, 5, 6] tail Queue: front [2, 3, 4, 5, 6, 7] tail Queue: front [2, 3, 4, 5, 6, 7, 8] tail Queue: front [3, 4, 5, 6, 7, 8] tail Queue: front [3, 4, 5, 6, 7, 8, 9] tail

    좋은 웹페이지 즐겨찾기