자료구조란?
- 데이터를 체계적으로 저장하여 데이터를 활용을 유리하게 한다.
- 무수한 상황에서 데이터를 효율적으로 다룰 수 있는 방법을 모두 모아, 자료구조라는 이름을 붙였다.
- 특정한 상황에 놓인 문제를 해결하는 데에 특화되어 있고, 적합한 자료구조를 적용하여 빠르고 정확하게 문제를 해결할 수 있다.
Stack
- 데이터(data)를 순서대로 쌓고, 하나씩 넣고 뺄 수 있으며, 입출력 방향이 하나로 같다.
- Stack 자료구조의 정책을 LIFO(Last In First Out) 혹은 FILO(First In Last Out)이라고 부르기도 한다.
- Stack에 데이터를 넣는 것을 'PUSH', 데이터를 꺼내는 것을 'POP'이라고 한다.
- 실사용의 예시로, 브라우저의 뒤로가기, 앞으로가기 기능을 구현할 때 사용한다.
LIFO(Last In First Out)
예1) 1, 2, 3, 4를 스택에 차례대로 넣습니다.
Stack<Integer> stack = new Stack<>(); //Integer형 스택 선언
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
---------------------------
1 <- 2 <- 3 <- 4
---------------------------
들어간 순서대로, 1번이 제일 먼저 들어가고 4번이 마지막으로 들어가게 됩니다.
예2) 스택이 빌 때까지 데이터를 전부 빼냅니다.
stack.pop();
stack.pop();
stack.pop();
stack.pop();
---------------------------
---------------------------
4, 3, 2, 1
제일 마지막에 있는 데이터부터 차례대로 나오게 됩니다.
ArrayList로 Stack 구현
public class Solution {
private ArrayList<Integer> listStack = new ArrayList<Integer>();
public void push(Integer data) {
listStack.add(data); // 배열의 add로 구현
}
// 스택에서 데이터 꺼내기
public Integer pop() {
if(listStack.size() == 0) {
return null;
}else {
return listStack.remove(listStack.size() - 1);
}
}
// 스택에 쌓인 데이터 크기 리턴
public int size() {
return listStack.size();
}
// 가장 나중에 추가된 데이터 리턴
public Integer peek() {
if(listStack.size() == 0) {
return null;
}else {
return listStack.get(listStack.size() - 1);
}
}
// 스택에 포함되어 있는 데이터를 문자열로 변환
public String show() {
return listStack.toString();
}
public void clear() { listStack.clear(); }
}
Queue
- Queue는 Stack과 반대되는 개념으로 데이터를 입력된 순서대로 처리할 때 주로 사용한다.
- 먼저 들어간 데이터가 먼저 나오는 FIFO(First In First Out) 혹은 LILO(Last In Last Out) 을 특징을 가지고 있다.
- 데이터를 넣는 것을 'enqueue', 데이터를 꺼내는 것을 'dequeue'라고 한다.
- 실사용을 예시로, 프린터는 인쇄 작업 Queue에 들어온 문서를 순서대로 인쇄한다.
FIFO(First In First Out)
예1) 1, 2, 3, 4를 큐에 차례대로 넣습니다.
Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언
queue.add(1); // queue에 값 1 추가
queue.add(2); // queue에 값 2 추가
queue.add(3); // queue에 값 3 추가
queue.add(4); // queue에 값 4 추가
queue.add(데이터)
출력 방향 <---------------------------< 입력 방향
1 <- 2 <- 3 <- 4
<---------------------------<
들어간 순서대로, 1번이 제일 먼저 들어가고 4번이 마지막으로 들어가게 됩니다.
예2) 큐가 빌 때까지 데이터를 전부 빼냅니다.
queue.poll(); // queue에 첫번째 값을 반환하고 제거
queue.poll();
queue.poll();
queue.poll();
queue.poll()
출력 방향 <---------------------------< 입력 방향
<---------------------------<
1, 2, 3, 4
제일 첫 번째 있는 데이터부터 차례대로 나오게 됩니다.
ArrayList로 Queue 구현
public class Solution {
private ArrayList<Integer> listQueue = new ArrayList<Integer>();
public void add(Integer data) {
listQueue.add(data);
}
// 첫번째로 추가된 데이터를 삭제 후 리턴
public Integer poll() {
if(listQueue.size() == 0) {
return null;
}else {
return listQueue.remove(0);
}
}
// 큐에 추가된 데이터의 크기를 리턴
public int size() {
return listQueue.size();
}
// 첫번째로 추가된 데이터를 리턴
public Integer peek() {
if(listQueue.size() == 0) {
return null;
}else {
return listQueue.get(0);
}
}
// 큐에 들어있는 모든 데이터를 String타입으로 변환 후 리턴
public String show() {
return listQueue.toString();
}
public void clear() {
listQueue.clear();
}
}