Java Deque는 일반적인 Queue와 Stack을 결합한 데이터 구조입니다. Deque의 헤드와 테일 모두에 요소를 추가하고 제거할 수 있습니다. "전통적인" 대기열에서는 줄의 꼬리(마지막 요소 뒤)에 요소를 추가하고 대기열의 머리 부분에서 요소를 제거합니다. 이 원칙을 FIFO(First In First Out)라고 하며 실생활에서 일반적인 고객 라인처럼 작동합니다. Java에서 Queue는 컬렉션 프레임워크의 일부인 인터페이스입니다. 스택이라는 중요한 데이터 구조도 있습니다. 이 목록은 후입선출(LIFO)이라는 완전히 반대되는 원리로 요소와 함께 작동합니다. 그것은 접시 더미와 유사하며 추가 또는 제거는 상단에서만 가능합니다.
큐 대 데크
Deque는 이상한 유형의 Queue입니다. 줄의 꼬리와 머리 부분에 새 요소를 추가할 수 있습니다. 제거와 같은 이야기: 이 구조에서 마지막 또는 첫 번째 요소를 제거할 수 있습니다. 따라서 Stack과 Queue가 혼합된 것으로 보입니다. "Deque"라는 이름은 "Double Ended Queue"를 의미합니다. "Deque"는 카드의 "데크"처럼 발음되며, 그거 아세요? 실제 카드 덱과 다소 유사합니다. 이러한 덱의 맨 아래 또는 맨 위에서 카드를 가져올 수 있습니다. 일부 선형 구조의 양쪽에서 요소를 추가하거나 제거하고 싶습니까? 데크를 사용하십시오. Java 8 또는 거의 모든 다른 버전에서 지원합니다. 전형적인 레고 벽돌과 벽돌로 만들어진 1열 "타워"를 상상해 보십시오. 타워 상단이나 하단에 새 브릭을 추가할 수 있습니다. 양쪽에서 벽돌을 제거할 수도 있습니다. 여기에 예가 있습니다. 모든 노란색 벽돌을 상단에 추가하고 모든 빨간색 벽돌을 하단에 추가합니다. 곧 Java 코드로 이 예제를 시연할 것입니다. 따라서 Java Deque의 양쪽 끝에서 큐에 추가하고 큐에서 제거할 수 있습니다. 즉, Deque를 큐와 스택 모두로 사용할 수 있습니다. Stack in Java에 대해 읽어보기: Java Stack 101: 스택 클래스 탐구 Java에서 Queue에 대해 읽어 보기: Java Queue Interface 및 해당 구현
데크의 특징
Java의 Deque는 구현이 크기 조정 가능한 배열의 지원을 제공하는 인터페이스입니다. 따라서 제한이 없는 다양한 용량을 보유하고 필요에 따라 새로운 요소를 추가할 수 있습니다.
여러 스레드에 의한 동시 액세스는 Deque에서 지원되지 않습니다.
Deque는 외부 동기화가 없는 경우 스레드로부터 안전하지 않습니다.
배열 deque에는 Null 요소가 허용되지 않습니다.
Deque 자바 인터페이스 선언
publicinterfaceDeque<E>extendsQueue<E>
자바 데크 메서드
java.util.Deque 는 Java Queue Interface를 확장한 인터페이스로 양방향 큐를 나타냅니다. 따라서 Deque로 작업하는 동안 모든 Java Queue 메서드를 사용할 수 있습니다. Deque가 Stack 인터페이스를 확장하지는 않지만 Deque 인터페이스는 push , peek 및 pop 과 같은 일반적인 스택 작업을 수행할 수 있는 메서드를 정의합니다 .
boolean add(element)는 Deque의 꼬리에 요소를 추가합니다. 성공하면 true를 반환하고 현재 사용 가능한 공간이 없으면 IllegalStateException을 발생시킵니다.
addFirst(element)는 Deque의 헤드에 요소를 추가합니다.
addLast(element)는 Deque의 꼬리에 요소를 추가합니다.
offer(element)는 꼬리에 요소를 추가하고 삽입이 성공했는지 설명하기 위해 부울을 반환합니다.
offerFirst(요소)는 헤드에 요소를 추가하고 삽입이 성공했는지 설명하기 위해 부울을 반환합니다.
offerLast(element)는 꼬리에 요소를 추가하고 삽입이 성공했는지 설명하기 위해 부울을 반환합니다.
iterator()는 deque에 대한 반복자를 반환합니다.
descendingIterator()는 이 deque에 대해 역순으로 반복자를 반환합니다.
push(element)는 헤드에 요소를 추가합니다.
pop(element) 헤드에서 요소를 제거하고 반환합니다.
removeFirst()는 헤드에서 요소를 제거합니다.
removeLast()는 꼬리에 있는 요소를 제거합니다.
poll()은 이 deque가 나타내는 큐의 헤드(즉, 이 deque의 첫 번째 요소)를 검색 및 제거하거나 이 deque가 비어 있으면 null을 반환합니다.
pollFirst()는 이 deque의 첫 번째 요소를 검색 및 제거하거나 이 deque가 비어 있으면 null을 반환합니다.
pollLast()는 이 deque의 마지막 요소를 검색 및 제거하거나 이 deque가 비어 있으면 null을 반환합니다.
peek() 는 이 deque가 나타내는 큐의 헤드(즉, 이 deque의 첫 번째 요소)를 검색하지만 제거하지는 않습니다. 이 deque가 비어 있으면 null을 반환합니다.
peekFirst() 는 이 deque의 첫 번째 요소를 검색하지만 제거하지는 않습니다. 이 deque가 비어 있으면 null을 반환합니다.
peekLast() 는 이 deque의 마지막 요소를 검색하지만 제거하지는 않습니다. 이 deque가 비어 있으면 null을 반환합니다.
여기 아래 표에서 모든 방법은 그룹으로 나뉩니다. 보시다시피 요소를 추가하고 제거하는 방법에는 여러 가지가 있습니다. 예를 들어 removeFirst()와 pop()은 모두 deque에서 첫 번째 요소를 제거합니다. 두 번째 것은 스택에서 "왔다". 즉, ArrayDeque를 스택으로만 사용하는 경우 pop()을 사용하여 제거하고 push()를 사용하여 추가하고 peek()을 사용하여 검사합니다. 이렇게 하면 다른 개발자가 코드를 더 이해하기 쉽게 만들 수 있습니다.
첫 번째 요소(머리)
마지막 요소(꼬리)
작업
예외 발생
특별한 가치
예외 발생
특별한 가치
삽입
addFirst(e)/푸시(e)
제안 우선(e)
추가마지막(e)
제안마지막()
제거하다
제거제()/팝()
pollFirst()
제거마지막()
투표마지막()
조사하다
getFirst()
픽퍼스트()/픽()
getLast()
엿보기마지막()
Deque 구현
Java Deque는 인터페이스이며 Java Collections API에서 구현됩니다.
java.util.LinkedList //List 및 Deque 구현
java.util.ArrayDeque //Deque 구현, Java 라이브러리
LinkedList 클래스는 내부적으로 이중 연결 목록을 사용하여 큐 또는 양단 큐를 모델링합니다. ArrayDeque 클래스는 요소를 내부적으로 배열에 저장합니다. 요소 수가 배열의 부피를 초과하면 새 배열이 할당되고 모든 요소가 이동됩니다. 즉, ArrayDeque는 필요에 따라 성장합니다.
ArrayDeque 클래스
ArrayDeque <E> 클래스는 AbstractCollection 클래스에서 기능을 상속하고 Deque 인터페이스를 사용하는 일반적인 양방향 대기열입니다. ArrayDeque는 deque 및 resizable-array를 사용하는 기능을 제공합니다. 처음에 배열은 크기 16으로 초기화됩니다. 양방향 대기열로 구현되어 헤드와 테일이라는 두 개의 포인터를 지원합니다. AbstractCollection 클래스를 상속 하고 Deque 인터페이스를 구현합니다. ArrayDeque 클래스에 대한 중요한 사항은 다음과 같습니다.
ArrayDeque(int 용량)는 초기 용량 용량 으로 대기열을 생성합니다 . 초기 용량을 지정하지 않으면 기본 용량은 16입니다.
Java Deque 예제 — ArrayDeque
기사 시작 부분의 레고 타워 예를 기억하십니까? 레고 브릭으로 단층 탑을 쌓는 수업을 만들어 봅시다. 벽돌은 빨간색, 노란색 또는 파란색일 수 있습니다. 탑 건축 규칙: 붉은 벽돌은 바닥에, 노란 벽돌은 꼭대기에 놓습니다. Big Java Deque 예제
//enum with colorspublicenumColor{RED,YELLOW,BLUE;}//class for the standard Lego Brick. You can connect or disconnect the Brick, it has colorpublicclassLegoBrick{Color color;boolean isConnected;publicvoidconnect(){System.out.println("This brick is connected");this.isConnected =true;}publicvoiddisconnect(){System.out.println("Disconnected");
isConnected =false;}publicLegoBrick(Color color,boolean isConnected){this.color = color;this.isConnected = isConnected;}publicColorgetColor(){return color;}publicbooleanisConnected(){return isConnected;}@OverridepublicStringtoString(){return"LegoBrick{"+"color="+ color +", isConnected="+ isConnected +'}';}}
다음은 타워 클래스입니다. 우리는 탑을 시작합니다. 개시된 탑은 빨간색과 노란색의 양에 따라 달라집니다. 타워에 벽돌을 추가하거나 제거할 수 있습니다. 노란색이면 상단에 벽돌을 추가하고 빨간색이면 하단에 추가합니다.
importjava.util.ArrayDeque;publicclassLegoTower{ArrayDeque<LegoBrick> myTower;int quantityOfReds;int quantityOfYellows;publicvoidaddBrickToTower(LegoBrick newLegoBrick){if(newLegoBrick.getColor()==Color.YELLOW){this.myTower.offerLast(newLegoBrick);
quantityOfYellows++;}//we can use addFirst(e)/push(e) instead of offerFirst hereif(newLegoBrick.getColor()==Color.RED){
myTower.offerFirst(newLegoBrick);
quantityOfReds++;}}publicvoid removeBrickFromTower (LegoBrick legoBrick){if(legoBrick.getColor()==Color.YELLOW){this.myTower.removeLast();
quantityOfYellows--;}if(legoBrick.getColor()==Color.RED){
myTower.removeFirst();
quantityOfReds--;}
legoBrick.isConnected =false;}publicLegoTower(int quantityOfReds,int quantityOfYellows){
myTower =newArrayDeque<>();this.quantityOfReds = quantityOfReds;this.quantityOfYellows = quantityOfYellows;for(int i =0; i < quantityOfReds; i++){LegoBrick redLegoBrick =newLegoBrick(Color.RED,false);
myTower.addFirst(redLegoBrick);
redLegoBrick.isConnected =true;}for(int i =0; i < quantityOfYellows; i++){LegoBrick yellowLegoBrick =newLegoBrick(Color.YELLOW,false);
myTower.addLast(yellowLegoBrick);
yellowLegoBrick.isConnected =true;}}publicvoidsetMyTower(ArrayDeque<legobrick> myTower){this.myTower = myTower;}publicvoidsetQuantityOfReds(int quantityOfReds){this.quantityOfReds = quantityOfReds;}publicvoidsetQuantityOfYellows(int quantityOfYellows){this.quantityOfYellows = quantityOfYellows;}@OverridepublicStringtoString(){return"LegoTower{"+"myTower="+ myTower +", quantityOfReds="+ quantityOfReds +", quantityOfYellows="+ quantityOfYellows +'}';}publicvoiddrawTower(){for(LegoBrick i : myTower){System.out.println(i.color);}}}publicclassMain{publicstaticvoidmain(String[] args){LegoBrick legoBrick1 =newLegoBrick(Color.YELLOW,false);
legoBrick1.connect();System.out.println(legoBrick1.toString());
legoBrick1.disconnect();System.out.println(legoBrick1.toString());LegoBrick legoBrick2 =newLegoBrick(Color.YELLOW,false);LegoBrick legoBrick3 =newLegoBrick(Color.RED,false);LegoBrick legoBrick4 =newLegoBrick(Color.RED,false);LegoBrick legoBrick5 =newLegoBrick(Color.YELLOW,false);LegoTower legoTower =newLegoTower(2,5);System.out.println("my Initiated Lego Tower: ");
legoTower.drawTower();
legoTower.addBrickToTower(legoBrick1);
legoTower.addBrickToTower(legoBrick2);
legoTower.addBrickToTower(legoBrick3);
legoTower.addBrickToTower(legoBrick4);
legoTower.addBrickToTower(legoBrick5);System.out.println("My LegoTower after adding some elements: ");
legoTower.drawTower();
legoTower.removeBrickFromTower(legoBrick1);
legoTower.removeBrickFromTower(legoBrick3);System.out.println("We removed one red and one yellow brick:");
legoTower.drawTower();}}
이 프로그램을 실행한 결과:
my Initiated LegoTower:
RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
My LegoTower after adding some elements:
RED
RED
RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
We removed one red and one yellow brick:
RED
RED
RED
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
YELLOW
Process finished with exit code 0
무엇을 기다립니다?? 빨간색이 위에 있는 이유는 무엇입니까? 아니, 그렇지 않아. 그들은 첫 번째(하단)부터 마지막(상단)까지 콘솔에 인쇄했습니다. 따라서 위의 브릭으로 그림과 같은 것을 보고 싶다면 LegoTower 클래스의 drawTower 메소드를 변경하면 됩니다. 매우 쉬운 작업입니다!
LinkedList
List 인터페이스는 항목 추가 순서를 유지하고 인덱스별로 항목에 액세스할 수 있도록 합니다. Deque는 양방향 대기열이며 양쪽에서 요소 추가 및 제거를 지원합니다. LinkedList는 주로 List 구현으로 알려져 있지만 이 클래스는 Deque도 구현하며 null을 포함한 모든 개체로 구성된 양방향 대기열을 만들 수 있습니다. LinkedList는 요소의 모음입니다. 클래스의 코드 소스에서 볼 수 있습니다. 이번에는 필드에 주의를 기울이십시오. 여기에 하나의 예를 추가하지만 LinkedList에 대해 자세히 알아보려면 이 CodeGym 기사를 참조하십시오 .
요소를 추가 및 제거하는 Java의 연결 목록 구현. 예
이러한 작업을 실제로 사용해 봅시다. 첫째, Java LinkedList 구현: 문자열의 LinkedList를 생성하고 거기에 3개의 요소를 추가합니다. 그런 다음 하나를 제거한 다음 중간에 하나를 추가하십시오.
publicclassMyLinkedTest{publicstaticvoidmain(String[] args){String h1 ="my";String h2 ="favorite";String h3 ="book";// LinkedList implementation in JavaLinkedList<string> linkedList =newLinkedList();
linkedList.add(h1);
linkedList.add(h2);
linkedList.add(h3);System.out.println("my list after adding 3 elements:");System.out.println(linkedList);System.out.println("element #2 of my list:");System.out.println(linkedList.get(2));
linkedList.remove(1);System.out.println("my list after removing #1:");System.out.println(linkedList);
linkedList.add(1,"first");System.out.println("my list after adding an element in the middle");System.out.println(linkedList);}
이 프로그램을 실행한 결과:
my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]