728x90
배열의 장단점
- 장점 : 배열은 구조가 간단하고 데이터를 읽는 데 걸리는 시간(접근 시간, access time)이 짧음
- 단점 :
1. 크기를 변경할 수 없음(실행중)
-크기를 변경해야 하는 경우 새로운 배열을 생성 후 데이터를 복사
※ 더 큰 배열을 생성 -> 기존 배열을 새로 만든 배열에 복사 -> 참조 변경
-크기 변경을 피하기 위해 충분히 큰 배열을 생성하면, 메모리가 낭비
2. 비순차적인 데이터의 추가, 삭제에 시간이 많이 걸림
-데이터 추가, 삭제를 위해 다른 데이터를 옮겨야함
-순차적인 데이터 추가(끝에 추가)와 삭제(끝부터 삭제)는 빠름
LinkedList
배열의 단점 (크기 변경X, 추가, 삭제 시간 ↑) 을 보완
LinkedList 장점
- 배열과 달리 LinkedList는 불연속적으로 존재하는 데이터를 연결(link)
배열은 삭제, LinkedList 기차 - 데이터 삭제 : 단 한 번의 참조변경만으로 가능
- 데이터 추가 : 한 번의 Node 객체생성과 두 번의 참조변경만으로 가능
LinkedList 단점
- 데이터 접근성이 나쁨
=> doubly linked list : 이중 연결리스트, 접근성 향상
=> doubly circular linked list : 이중 원형 연결리스트
ArrayList와 LinkedList 성능
- 순차적으로 데이터를 추가/삭제 => ArrayList가 빠름
- 비순차적으로 데이터를 추가/삭제 => LinkedList가 빠름
- 접근시간(access time) => ArrayList가 빠름
인덱스가 n인 데이터의 주소 = 배열의 주소 + n * 데이터타입의 크기 (n번째 요소)
| 구분 | 읽기(접근시간) | 추가/삭제 | 비고 |
| ArrayList | 빠름 | 느림 | 순차적인 추가삭제는 더 빠름 비효율적인 메모리 사용 |
| LinkedList | 느림 | 빠름 | 데이터가 많을수록 접근성이 떨어짐 |
ArrayList 배열 기반(연속), LinkedList 연결 기반(불연속)
Stack, Queue
Stack(밑이 막힌 상자) => 배열로 구현하는 것이 유리
LIFO(Last in First Out)구조. 마지막에 저장된 것을 제일 먼저 꺼내게 됨
저장(push), 추출(pop)
Queue(줄서기, 양끝이 뚫린 상자) => 링크드 리스트로 구현하는 것이 유리
FIFO(First in First Out) 구조. 제일 먼저 저장한 것을 제일 먼저 꺼내게 됨
저장(offer), 추출(poll)
Stack의 메서드
| 메서드 | 설명 |
| boolean empty() | Stack이 비어있는지 알려줌 |
| Object peek() | Statck 맨 위에 저장된 객체를 반환. pop()과 달리 Stack에서 객체를 꺼내지 않음. (비어있을 때는 EmptyStackException 발생) |
| Object pop() | Statck의 맨 위의 저장된 객체를 꺼냄 (비어있을 때는 EmptyStackException 발생) |
| Object push(Object item) | Statck에 객체(item)를 저장 |
| int search(Object o) | Stack에서 주어진 객체(o)를 찾아서 그 위치를 반환. 못 찾으면 -1을 반환 (배열과 달리 위치는 0이 아닌 1부터 시작) |
※Stack 클래스
Queue의 메서드
| 메서드 | 설명 |
| boolean add(Object o) | 지정된 객체를 Queue에 추가. 성공하면 true 반환, 저장공간이 부족하면 IllegalStateException 발생 |
| Object remove() | Queue에서 객체를 꺼내 반환. 비어있으면 NoSuchElementException 발생 |
| Object element() | 삭제없이 요소를 읽음. peek와 달리 Queue가 비어있을 때 NoSuchElementException 발생 |
| boolean offer(Object o) | Queue에 객체를 저장. 성공하면 true 반환, 실패하면 false 반환 |
| Object poll() | Queue에서 객체를 꺼내서 반환. 비어있으면 null 반환 |
| Object peek() | 삭제없이 요소를 읽어 옴. 비어있으면 null 반환 |
※ add(), offer() 추가. 예외 발생 여부가 다름. remove(), poll() 삭제. 예외 발생 여부가 다름
※인터페이스로 구현됨
//Queue를 구현한 클래스 사용
Queue queue = new LinkedList();
//LinkedList queue = new LinkedList();
queue.offer("0");
package chapter11;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class Study05Ex1 {
public static void main(String[] args) {
Stack stack = new Stack();
Queue queue = new LinkedList(); //Queue인터페이스의 구현체인 LinkedList
stack.push("0");
stack.push("1");
stack.push("2");
queue.offer("0");
queue.offer("1");
queue.offer("2");
System.out.println("Stack");
while(!stack.empty()) {
System.out.println(stack.pop());
}
System.out.println("Queue");
while(!queue.isEmpty()) {
System.out.println(queue.poll());
}
}
}
스택의 활용 : 수식계산, 수식괄호검사, 워드프로세스의 undo/redo, 웹브라우저 뒤로/앞으로
큐의 활용 : 최근사용문서, 인쇄작업 대기목록, 버퍼(buffer)
package chapter11;
import java.util.EmptyStackException;
import java.util.Stack;
public class Study05Ex2 {
public static void main(String[] args) {
Stack stack = new Stack();
String expr = "(3+4)*5-2)";
System.out.println("표현식 : " + expr);
try {
for(int i = 0; i< expr.length(); i++) {
char ch = expr.charAt(i);
if(ch=='(') {
stack.push(ch+"");
} else if(ch==')') {
stack.pop();
}
}
if(stack.isEmpty()) {
System.out.println("괄호가 일치");
} else {
System.out.println("괄호 개수 일치 하지 않음");
}
} catch (EmptyStackException e) {
System.out.println("괄호 개수가 일치 하지 않음");
}
}
}
package chapter11;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Study05Ex3 {
static Queue queue = new LinkedList();
static final int MAX_SIZE = 5;
public static void save(String input) {
if(!"".equals(input))
queue.offer(input);
if(queue.size()>MAX_SIZE)
queue.remove();
}
public static void main(String[] args) {
System.out.println("help를 입력하면 도움말을 확인");
while(true) {
System.out.print(">>");
try {
Scanner sc = new Scanner(System.in);
String input = sc.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")) {
save(input);
LinkedList list = (LinkedList)queue;
// for(int i = 0; i<list.size();i++) //list.size()를 계속해서 불러오기 때문에 좋지 않은 코드 아래와 같이 해주도록 권장
final int SIZE = list.size();
for(int i= 0 ; i<SIZE ; i++)
System.out.println((i+1)+"."+list.get(i));
} else {
save(input);
System.out.println(input);
}
} catch (Exception e) {
System.out.println("입력 오류");
}
}
}
}
728x90