LinkedList
배열은 가장 기본적인 형태의 자료구조로 구조가 간단하며 사용하기 쉽고 데이터를 읽어 오는데 걸리는 시간(접근 시간, access time)이 가장 빠르다는 장점을 가지고 있지만 다음과 같은 단점도가지고 있다.
- 크기 변경 불가능 - 새로운 배열을 생성해서 데이터 복사, 충분히 큰 배열을 만들 경우 메모리 낭비
- 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸림- 데이터를 추가하고 마지막에서부터 데이터를 삭제하는 것은 빠르지만, 배열 중간에 데이터를 추가하려면 , 빈 자리를 만들기위해 다른 데이터들을 복사해서 이동해야 한다.
배열의 단점을 보안하기 위해 링크드 리스트(linked list)라는 자료구조가 고안되었다.
class Node{
Node next; //다음 요소의 주소를 저장
Object obj; //데이터를 저장
}링크드 리스트의 각 요소(node)들은 자신과 연결된 다음 요소에 대한 참조(주소값)와 데이터로 구성되어 있다.
링크드 리스트에서의 데이터 삭제는 간단하다.
삭제하고자 하는 요소의 이전 요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경하면 된다.
하나의 참조변수만 변경하면 삭제가 이뤄진다. 또한 배열처럼 데이터를 이동하기 위해 복사하는 과정이 없기 때문에 처리속도가 빠르다.
새로운 데이터를 추가할 때는 새로운 요소를 생성한 다음 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경하고, 새로운 요소가 그 다음 요소를 참조하도록 변경하기만 하면 되므로 처리속도가 매우 빠르다.
링크드리스트는 이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만 이전 요소에 대한 접근은 어렵다.
이점 을 보안한것이 더블 링크드 리스트(이중 연결리스트, doubly linked list)이다.
class Node{
Node next; //다음 요소의 주소를 저장
Node previous; //이전 요소의 주소를 저장
Object obj; //데이터를 저장
}더블 링크드 리스트는 링크드 리스트에 참조변수를 하나 더 추가하여 이전 요소에 대한 참조가 가능하게 하였다.
즉 각 요소에 대한 접근과 이동이 쉽기 때문에 링크드 리스트보다 많이 사용된다.
더블 링크드 리스트의 접근성을 보다 향상 시킨것이 더블 써큘러 링크드 리스트(이중 원형 연결리스트, doubly circular linked list)이다. 이것은 더블 링크드 리스트의 첫번째 요소와 마지막 요소를 서로 연결시킨것이다.
실제 LinkedList클래스는 이름과 달리 링크드리스트가 아닌, 더블 링크드 리스트로 구현되어 있다.
LinkedList() : LinkedList 객체를 생성
LinkedList(Collection c) : 주어진 컬렉션을 포함하는 LinkedList 객체를 생성
boolean add(Object o) : 지정된 객체(o)를 LinkedList의 끝에 추가, 저장에 성공하면 true, 실패하면 false
void add(int index, Object element) : 지정된 위치에 객체를 추가
boolean addAll(Collection c) : 주어진 컬렉션에 포함된 모든 요소를 LinkedList의 끝에 추가한다. 성공하면 true, 실패하면 false
boolean addAll(int index, Collection c) : 지정된 위치에 주어진 컬렉션에 포함된 모든 요소를 추가, 성공하면 true, 실패하면 false
void clear() : LinkedList의 모든 요소 삭제
boolean contains(Object o) : 지정된 객체가 LinkedList에 포함되어 있는지 알려줌
boolean containsAll(Collection c) : 지정된 컬렉션의 모든 요소가 포함되어 있는지 알려줌
Object get(int index) : 지정된 위치의 객체를 반환
int indexOf(Object o) : 지정된 객체가 저장된 위치(앞에서 몇 번째)를 반환
boolean isEmpty() : LinkedList가 비어있는지 알려준다. 비어있으면 true
Iterator iterator() : Iterator를 반환한다.
int lastIndexOf(Object o) : 지정된 객체의 위치(index)를 반환(끝부터 역순검색)
ListIterator listIterator() : ListIterator를 반환한다.
ListIterator listIterator(int index) : 지정된 위치에서부터 시작하는 ListIterator를 반환
Object remove(int index) : 지정된 위치의 객체를 LinkedList에서 제거
boolean remove(Object o) : 지정된 객체를 LinkedList에서 제거, 성공하면 true, 실패하면 false
boolean removeAll(Collection c) : 지정된 컬렉션의 요소와 일치하는 요소를 모두 삭제
boolea retainAll(Collection c) : 지정된 컬렉션의 모든 요소가 포함되어 있는지 확인
Object set(int index, Object element) : 지정된 위치의 객체를 주어진 객체로 바꿈
int size() : LinkedList에 저장된 객체의 수를 반환
List subList(int fromIndex, int toIndex) : LinkedList의 일부를 List로 반환
Object[] toArray() : LinkedList에 저장된 객체를 배열로 반환
Object[] toArray(Obejct[] a) : LinkedList에 저장된 객체를 주어진 배열에 저장하여 반환
Queue 인터페이스
Object element() : LinkedList의 첫 번쨰 요소를 반환
boolean offer(Object o) : 지정된 객체를 LinkedList의 끝에 추가, 성공하면 true, 실패하면 false
Object peek() : LinkedList의 첫번쨰 요소를 반환
Object poll() : LinkedList의 첫 번째 요소를 반환, LinkedList에서는 제거된다.
Object remove() : LinkedList의 첫번째 요소를 제거
Deque인터페이스
void addFirst(Object o) : LinkedList의 맨 앞에 객체를 추가
void addLast(Object o) : LinkedList의 맨 끝에 객체를 추가
Iterator descendingIterator() : 역순으로 조회하기 위한 DescendingIterator를 반환
Object getFirst() : LinkedList의 첫번쨰 요소를 반환
Obejct getLast() : LinkedList의 마지막 요소를 반환
boolean offerFirst(Object o) : LinkedList의 맨 앞에 객체를 추가, 성공하면 true
boolean offerLast(Object o) : LinkedList의 맨 끝에 객체를 추가, 성공하면 true
Object peekFirst() : LinkedList의 첫번쨰 요소를 반환
Object peekLast() : LinkedList의 마지막 요소를 반환
Object pollFirst() : LinkedList의 첫번쨰 요소를 반환하면서 제거
Object pollLast() : LinkedList의 마지막 요소를 반환하면서 제거
Object pop() : removeFirst()와 동일
void push(Object o) : addFirst()와 동일
Object removeFirst() : LinkedLIst의 첫번째 요소를 제거
Object removeLast() : LinkedList의 마지막 요소를 제거
boolean removeFirstOccurrence(Object o) : LinkedList에서 첫번째로 일치하느 ㄴ객체를 제거
boolean removeLastOccurerence(Object o) : LinkedList에서 마지막으로 일치하는 객체를 제거
LinkedList 역시 List인터페이스를 구현하였다.
import java.util.*;
public class ArrayListLinkedListTest {
public static void main(String[] args) {
//추가할 데이터의 개수를 고려하여 충분히 잡는다.
ArrayList al = new ArrayList(2000000);
LinkedList ll = new LinkedList();
System.out.println("순차적으로 추가하기");
System.out.println("ArrayList : "+add1(al));
System.out.println("LinkedList : "+add1(ll));
System.out.println();
System.out.println("중간에 추가하기");
System.out.println("ArrayList : "+add2(al));
System.out.println("LinkedList : "+add2(ll));
System.out.println();
System.out.println("중간에서 삭제하기");
System.out.println("ArrayList : "+remove2(al));
System.out.println("LinkedList : "+remove2(ll));
System.out.println();
System.out.println("순차적으로 삭제하기");
System.out.println("ArrayList : "+remove1(al));
System.out.println("LinkedList : "+remove1(ll));
System.out.println();
}
public static long add1(List list){
long start = System.currentTimeMillis();
for(int i=0; i<1000000;i++) list.add(i+"");
long end = System.currentTimeMillis();
return end-start;
}
public static long add2(List list){
long start = System.currentTimeMillis();
for(int i=0; i<10000;i++) list.add(500,"X");
long end = System.currentTimeMillis();
return end-start;
}
public static long remove1(List list){
long start = System.currentTimeMillis();
for(int i=list.size()-1; i>=0; i--) list.remove(i);
long end = System.currentTimeMillis();
return end-start;
}
public static long remove2(List list){
long start = System.currentTimeMillis();
for(int i=0; i<10000;i++) list.remove(i);
long end = System.currentTimeMillis();
return end-start;
}
}
=========================
순차적으로 추가하기
ArrayList : 202
LinkedList : 1570
중간에 추가하기
ArrayList : 2214
LinkedList : 10
중간에서 삭제하기
ArrayList : 1891
LinkedList : 178
순차적으로 삭제하기
ArrayList : 10
LinkedList : 39결론 1 : 순차적으로 추가/삭제하는 경우에는 ArrayList가 LinkedList보다 빠르다
순차적으로 삭제한 다는 것은 마지막 데이터부터 역순으로 삭제한다는 것을 의미하고, ArrayList는 마지막 데이터부터 삭제할 경우 각 요소들의 재배치가 필요하지 않기 때문에 상당히 빠르다.
결론 2: 중간에 데이터를 추가/삭제하는 경우에는 LinkedList가 ArrayList보다 빠르다.
중간 요소를 추가 또는 삭제하는 경우 LinkedList는 각 요소간의 연결만 변경해주면 되기 떄문에 처리속도가 빠르지만, ArrayList는 각 요소들을 재배치하여 추가할 공간을 확보하거나 빈 공간을 채워야 하기 때문에 처리속도가 늦다.
import java.util.*;
public class ArrayListLinkedListTest2 {
public static void main(String[] args) {
ArrayList al = new ArrayList(1000000);
LinkedList ll = new LinkedList();
add(al);
add(ll);
System.out.println("접근 시간 테스트");
System.out.println("ArrayList :" + access(al));
System.out.println("LinkedList :" + access(ll));
}
public static void add(List list) {
for (int i = 0; i < 100000; i++)
list.add(i + "");
}
public static long access(List list) {
long start = System.currentTimeMillis();
for (int i = 0; i < 10000; i++)
list.get(i);
long end = System.currentTimeMillis();
return end - start;
}
}
========================
접근 시간 테스트
ArrayList :1
LinkedList :276배열의 경우 인덱스가 n인 요소의 값을 얻어 오고자 한다면 단순히 아래와 같은 수식ㅇ르 계산함으로써 해결된다.
인덱스가 n인 데이터의 주소 = 배열의 주소+n*데이터의 타입 크기
배열은 각 요소들이 연속적으로 메모리상에 존재하기 때문에 간단한 계산만으로 원하는 요소의 주소를 얻어서 저장된 데이터를 바로 읽어올수 있다.
LinkedList는 불연속적으로 위치한 각 요소들이 서로 연결된 것이라, 처음부터 n번째 데이터까지 차례로 따라가야만 원하는 값을 얻을 수 있다.
그래서 LinkedList는 저장해야할 데이터의 개수가 많아질수록 데이터를 읽어오는 시간, 접근시간이 길어진다는 단점이 있다.
ArrayList의 접근시간은 빠르고, 추가/삭제는 느리다.
LinkedList의 접근시간은 느리고, 추가/삭제는 빠르다.
ArrayList는 순차적인 추가삭제는 더 빠르다, 비효율적인 메모리 사용
LinkedList는 데이터가 많을 수록 접근성이 떨어진다.
다루고자 하는 데이터의 개수가 변하지 않는 경우라면, ArrayList가 최상의 선택이지만 , 데이터 개수의 변경이 잦다면 LInkedList를 사용하는 것이 더 나은 선택이 될것이다.
또한 두 클래스의 장점을 이용해 조합할 수도 있다.
데이터를 저장할 때는 ArrayList를 사용한 다음, 작업할 때는 LinkedList로 데이터를 옮겨서 작업하면 좋은 효율을 얻을 것이다.
ArrayList al = new ArrayList(1000000);
for(int i=0; i<100000;i++) al.add(i+"");
LinkedList ll = new LinkedList(al);
for(int i=0; i<100000;i++) ll.add(500,"X");컬렉션 프레임웍에 속한 대부분의 컬렉션 클래스들은 이처럼 서로 변환이 가능한 생성자를 제공한다.
Stack과 Queue
스택은 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 LIFO(Last In First Out)구조로 되어있다.
큐는 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO(First In Last Out)구조로 되어있다.
쉽게 얘기하면 스택은 한 방향으로만 뺄수 있는 구조이고, 큐는 위아래로 뚫려 있어 한방향으로 넣고 한 방향으로는 뺴는 파이프와 같은 구조로 되어 있다.
예를 들어 스택에 0,1,2 순서로 데이터를 넣으면 꺼낼 때는 2,1,0의 순서로 꺼내게 된다.
즉 넣은 순서와 꺼낸 순서가 뒤집어 지게 되는 것이다.
이와 반대로 큐는 0,1,2의 순서로 데이터를 넣으면 꺼낼 때 역시 0,1,2 순서로 꺼내게 된다. 순서의 변경없이 먼저 넣은 것을 꺼내게 되는 것이다.
순차적으로 데이터를 추가하고 삭제하는 스택은 ArrayList와 같은 배열 기반의 컬렉션 클래스가 적합하지만, 큐는 데이터를 꺼낼 때 항상 첫번째 저장된 데이터를 삭제하므로, ArrayList와 같은 배열 기반의 컬렉션 클래스를 사용한다면 데이터를 꺼낼 때마다 빈 공간을 채우기 위해 데이터의 복사가 발생하므로 비효율적이다. 그래서 큐는 데이터의 추가/삭제가 쉬운 LinkedList로 구현하는 것이 더 작합하다.
Stack의 메서드
boolean empty() : Stack이 비어있는지 알려준다
Object peek() : Stack의 맨 위에 저장된 객체를 반환, pop()과 달리 Stack에서 객체를 꺼내지 않음.(비어있을 때는 EmptyStackException 발생)
Object pop() : Stack의 맨 위에 저장된 객체를 꺼낸다. (비어있을 때는EmptyStackException 발생)
Object push(Object item) : Stack에 객체(item)를 저장한다.
int search(Object o) :Stack에서 주어진 객체를찾아서 그 위치를 반환, 못찾으면 -1을 반환 (배열과 달리 위치는 0이 아닌 1부터 시작)
Queue의 메서드
boolean add(Object o) : 지정된 객체를 Queue에 추가한다. 성공하면 true를 반환, 저장공간이 부족하면 IIIegalStateException 발생
Object remove() : Queue에서 객체를 꺼내 반환, 비어있으면 NoSurchElementException발생
Object element() : 삭제없이 요소를 익어온다. peek과 달리 Queue가 비어있을 떄 NoSuchElementException 발생
boolean offer(Object o) : Queue에 객체를 저장, 성공하면 true, 실패하면 false를 반환
Object poll() : Queue에서 객체를 꺼내서 반환, 비어있으면 null을 반환
Object peek() : 삭제없이 요소를 읽어온다. Queue가 비어있으면 null을반환
import java.util.*;
public class StackQueueEx {
public static void main(String[] args) {
Stack st = new Stack();
Queue q = new LinkedList(); //Queue인터페이스의 구현체인 LinkedList사용
st.push("0");
st.push("1");
st.push("2");
q.offer("0");
q.offer("1");
q.offer("2");
System.out.println("Stack");
while(!st.empty()){
System.out.println(st.pop());
}
System.out.println("Queue");
while(!q.isEmpty()){
System.out.println(q.poll());
}
}
}
===================================
Stack
2
1
0
Queue
0
1
2스택과 큐에 각각 같은 순서로 데이터를 넣고 꺼내었을때 결과가 다른 것을 알 수 있다.
큐는 먼저 넣은것이 먼저 꺼내지는 구조 FIFO구조 이므로 넣을 떄와 같은 순서이고,
스택은 먼저 넣은 것이 나중에 꺼내지는 구조 LIFO이기 때문에 넣을 때의 순서와 반대로 꺼내진 것을 알 수 있다.
자바에서는 스택을 Stack클래스로 구현하여 제공하고 있지만, 큐는 Queue인터페이스만 정의해놓았을뿐 별도의 클래스를 제공하지 않는다. 대신 Queue인터페이스를 구현한 클래스들이 있어서 이 들 중의 하나를 선택해서 사용하면 된다.
Stack 직접 구현하기
Stack은 ArrayList가 아닌 Vector로부터 상속받아 구현하였다. Stack의 실제 코드를 이해하기 위해 수정해서 MyStack을 구현해보자
import java.util.*;
public class MyStack extends Vector{
public Object push(Object item){
addElement(item);
return item;
}
public Object pop(){
Object obj = peek(); //Stack에 저장된 마지막 요소를 읽어온다.
//만일 Stack이 비어있다면 peek()메서드가 EmptyStackException을 발생시킨다.
//마지막 요소를 삭제한다. 배열의 index가 0부터 시작하므로 1을 빼준다.
removeElementAt(size()-1);
return obj;
}
public Object peek(){
int len = size();
if(len ==0)
throw new EmptyStackException();
//마지막 요소를 반환한다. 배열의 index가 0부터 시작하므로 1을 뺴준다.
return elementAt(len-1);
}
public boolean empty(){
return size() ==0;
}
public int search(Object o){
int i= lastIndexOf(o); //끝에서부터 객체를 찾는다.
//반환 값은 저장된 위치(배열의 index)이다.
if(i >=0){ //객체를 찾은 경우
return size() -i; //Stack은 맨 뒤에 저장된 객체의 index를 1로 정의하기 때문에
//계산을 통해서 구한다.
}
return -1; //찾지못하면 -1을 반환한다.
}
}Vector에 구현되어 있는 메서드를 이용하기 때문에 코드고 간단하고 어렵지도 않다.
스택과 큐의 활용
스택의 활용 예 : 수식계산, 수식괄호검사, 워드프로세서의 undo/redo , 웹브라우저의 뒤로/앞으로
큐의 활용 예 :최근사용문서, 인쇄작업대기목록, 버퍼(buffer)
import java.util.*;
public class StackEx1 {
public static Stack back = new Stack();
public static Stack forward = new Stack();
public static void main(String[] args) {
goURL("1.네이트");
goURL("2. 야후");
goURL("3.네이버");
goURL("4. 다음");
printStatus();
goBack();
System.out.println(" '뒤로' 버튼을 누른 후");
printStatus();
goBack();
System.out.println(" '뒤로' 버튼을 누른 후");
printStatus();
goForward();
System.out.println(" '앞으로' 버튼을 누른 후");
printStatus();
goURL("www.github.com");
System.out.println("새로운 주소로 이동 후");
printStatus();
}
public static void printStatus(){
System.out.println("back:"+back);
System.out.println("forward:"+forward);
System.out.println("현재 화면은 '"+back.peek()+"' 입니다.");
System.out.println();
}
public static void goURL(String url){
back.push(url);
if(!forward.empty())
forward.clear();
}
public static void goForward(){
if(!forward.empty())
back.push(forward.pop());
}
public static void goBack(){
if(!back.empty())
forward.push(back.pop());
}
}
========================
back:[1.네이트, 2. 야후, 3.네이버, 4. 다음]
forward:[]
현재 화면은 '4. 다음' 입니다.
'뒤로' 버튼을 누른 후
back:[1.네이트, 2. 야후, 3.네이버]
forward:[4. 다음]
현재 화면은 '3.네이버' 입니다.
'뒤로' 버튼을 누른 후
back:[1.네이트, 2. 야후]
forward:[4. 다음, 3.네이버]
현재 화면은 '2. 야후' 입니다.
'앞으로' 버튼을 누른 후
back:[1.네이트, 2. 야후, 3.네이버]
forward:[4. 다음]
현재 화면은 '3.네이버' 입니다.
새로운 주소로 이동 후
back:[1.네이트, 2. 야후, 3.네이버, www.github.com]
forward:[]
현재 화면은 'www.github.com' 입니다.이 예제는 웹브라우저의 뒤로, 앞으로 버튼 기능을 구현한 것이다.
import java.util.*;
public class ExpValidCheck {
public static void main(String[] args) {
if(args.length != 1){
System.out.println("Usage: java ExpValidCheck \"EXPRESSION\"");
System.out.println("Example : java ExpValidCheck \"((2+3)*1)+3\"");
System.exit(0);
}
Stack st = new Stack();
String expression = args[0];
System.out.println("expression :"+expression);
try{
for(int i=0; i<expression.length(); i++){
char ch = expression.charAt(i);
if(ch== '('){
st.push(ch+"");
}else if(ch==')'){
st.pop();
}
}
if(st.isEmpty()){
System.out.println("괄호가 일치합니다.");
}else{
System.out.println("괄호가 일치하지 않습니다.");
}
}catch(EmptyStackException e){
System.out.println("괄호가 일치하지 않습니다.");
}
}
}
=======================================
expression :(2+3)*1
괄호가 일치합니다.입력한 수식의 괄호가 올바른지를 체크하는 예제이다.
(를 만나면 스택에 넣고 )를 만나면 스택에서 (를 꺼낸다. ')'를 만나서 '('를 꺼내려 할 때 스택이 비어있거나 수식을 검사하고 난 후에도 스택이 비어있지 않으면 괄호가 잘못된 것이다.
import java.util.*;
public class QueueEx1 {
static Queue q = new LinkedList();
static final int MAX_SIZE = 5; // Queue에 최대 5개까지만 저장되도록 한다.
public static void main(String[] args) {
System.out.println("help를 입력하면 도움말을 볼 수 있습니다.");
while(true){
System.out.print(">>");
try{
//화면으로부터 라인단위로 입력받는다.
Scanner s = new Scanner(System.in);
String input = s.nextLine().trim();
if("".equals(input)) continue;
if(input.equalsIgnoreCase("q")){
System.exit(0);
}else if(input.equalsIgnoreCase("help")){
System.out.println(" help - 도움말을 보여줍니다.");
System.out.println(" q 또는 Q - 프로그램을 종료합니다.");
System.out.println(" history = 최근에 입력한 명령어를 "+MAX_SIZE +"개 보여줍니다.");
}else if(input.equalsIgnoreCase("history")){
int i=0;
//입력받은 명령어를 저장
save(input);
//LinkedList의 내용을 보여준다.
LinkedList tmp = (LinkedList)q;
ListIterator it = tmp.listIterator();
while(it.hasNext())
System.out.println(++i+"."+it.next());
}else{
save(input);
System.out.println(input);
} //if(input.euqalsIgnoreCase("q")){
} catch(Exception e){
System.out.println("입력 오류입니다.");
}
}
}
public static void save(String input) {
// queue에 저장한다.
if (!"".equals(input))
q.offer(input);
// queue의 최대 크기를 넘은 제일 처음 입력된 것을 삭제한다.
if (q.size() > MAX_SIZE) // size()는 Collection인터페이스에 정의
q.remove();
}
}
===========================
help를 입력하면 도움말을 볼 수 있습니다.
>>help
help - 도움말을 보여줍니다.
q 또는 Q - 프로그램을 종료합니다.
history = 최근에 입력한 명령어를 5개 보여줍니다.
>>dir
dir
>>cd
cd
>>mkdir
mkdir
>>dir
dir
>>history
1.dir
2.cd
3.mkdir
4.dir
5.history
>>q위 예제는 유닉스의 명령어 history를 Queue를 이용해서 구현한 것이다.
PriorityQueue
Queue인터페이스의 구현체 중의 하나로, 저장한 순서에 관계없이 우선순위가 높은 것 부터 꺼내게 된다는 특징이 있다. 그리고 null을 저장할 수 없다. null을 저장하면 NullPointerException이 발생한다.
PriorityQueue는 저장공간으로 배열을 사용하며, 각 요소를 힙(heap)이라는 자료구조의 형태로 저장한다.
- 자료구조 힙(heap)은 JVM의 힙(heap)과 이름만 같을 뿐 다른것이다.
import java.util.*;
public class PriorityQueueEx {
public static void main(String[] args) {
Queue pq = new PriorityQueue();
pq.offer(3);
pq.offer(1);
pq.offer(5);
pq.offer(2);
pq.offer(4);
System.out.println(pq); // pq의 내부 배열을 출력
Object obj = null;
// PriorityQueue에 저장된 요소를 하나씩 꺼낸다.
while ((obj = pq.poll()) != null)
System.out.println(obj);
}
}
============================
[1, 2, 5, 3, 4]
1
2
3
4
5저장순서가 3,1,5,2,4 인데도 출력결과는 1,2,3,4,5이다. 우선순위가 작을수록 높은 것이므로 1이 가장 먼저 출력된것이다. 물론 숫자 뿐만아니라 객체도 저장할 수도 있는데 그럴 경우 각 객체의 크기를 비교할 수 있는 방법을 제공해야 한다.
참조변수 pq를 출력하면 내부적으로 가지고 있는 배열의 내용이 출력되는데, 저장한 순서와 다르게 저장되었다. 힙이라는 자료구조 형태로 저장되기 때문이다.
Deque(Double -Ended Queue)
Queue의 변형으로 한쪽 끝으로만 추가/삭제할 수있는 Queue와 달리, Deque(덱, 또는 디큐라고 읽음)은 양쪽 끝에서 추가/삭제가 가능하다. Deque의 조상은 Queue이며, 구현체로는 ArrayDeque과 LinkedList등이 있다.
덱은 스택과 큐를 하나로 합쳐놓은것과 같으며, 스택으로 사용할 수 도 있고, 큐로 사용할 수도 있다.
Deque : offerLast() pollLast() pollFirst() peekFirst() peekLast()
Queue : offer() x poll() peek() x
Stack : push() pop() x x peek()
'Back-end' 카테고리의 다른 글
| 11 컬렉션 프레임웍(4) (0) | 2021.07.08 |
|---|---|
| 11 컬렉션 프레임웍(3) (0) | 2021.07.07 |
| 03 SELECT문의 기본 형식 (0) | 2021.07.06 |
| 11 컬렉션 프레임웍(1) (0) | 2021.07.06 |
| 02 관계형 데이터베이스와 오라클 데이터 베이스 (0) | 2021.07.05 |
