스택(Stack)
입력과 출력이 한 곳(방향)으로 제한
LIFO (Last In First Out, 후입선출) : 가장 나중에 들어온 것이 가장 먼저 나옴
언제 사용?
함수의 콜스택, 문자열 역순 출력, 연산자 후위표기법
스택 구현 코드
public class Stack<T> {
private Node<T> top; // 스택의 맨 위를 가리키는 노드
private int size; // 스택의 현재 크기
private static class Node<T> {
private T data;
private Node<T> next;
public Node(T data) {
this.data = data;
}
}
public Stack() {
top = null;
size = 0;
}
// 스택에 원소를 추가합니다.
public void push(T item) {
Node<T> newNode = new Node<>(item);
newNode.next = top; // 새 노드의 다음 노드를 기존의 top으로 설정
top = newNode; // top을 새 노드로 업데이트
size++;
}
// 스택의 맨 위 원소를 제거하고 반환합니다.
public T pop() {
if (isEmpty()) {
throw new IllegalStateException("Stack is empty!");
}
T item = top.data;
top = top.next; // top을 다음 노드로 변경
size--;
return item;
}
// 스택의 맨 위 원소를 조회합니다.
public T peek() {
if (isEmpty()) {
throw new IllegalStateException("Stack is empty!");
}
return top.data;
}
public boolean isEmpty() {
return top == null;
}
public int size() {
return size;
}
}
동적 배열 스택
위처럼 구현하면 스택에는 MAX_SIZE라는 최대 크기가 존재해야 한다
(스택 포인터와 MAX_SIZE를 비교해서 isFull 메소드로 비교해야되기 때문!)
최대 크기가 없는 스택을 만드려면?
arraycopy를 활용한 동적배열 사용
public void push(Object o) {
if(isFull(sp)) {
Object[] arr = new Object[MAX_SIZE * 2];
System.arraycopy(stack, 0, arr, 0, MAX_SIZE);
stack = arr;
MAX_SIZE *= 2; // 2배로 증가
}
stack[sp++] = o;
}기존 스택의 2배 크기만큼 임시 배열(arr)을 만들고
arraycopy를 통해 stack의 인덱스 0부터 MAX_SIZE만큼을 arr 배열의 0번째부터 복사한다
복사 후에 arr의 참조값을 stack에 덮어씌운다
마지막으로 MAX_SIZE의 값을 2배로 증가시켜주면 된다.
이러면, 스택이 가득찼을 때 자동으로 확장되는 스택을 구현할 수 있음
스택을 연결리스트로 구현해도 해결 가능
public class Node {
public int data;
public Node next;
public Node() {
}
public Node(int data) {
this.data = data;
this.next = null;
}
}public class Stack {
private Node head;
private Node top;
public Stack() {
head = top = null;
}
private Node createNode(int data) {
return new Node(data);
}
private boolean isEmpty() {
return top == null ? true : false;
}
public void push(int data) {
if (isEmpty()) { // 스택이 비어있다면
head = createNode(data);
top = head;
}
else { //스택이 비어있지 않다면 마지막 위치를 찾아 새 노드를 연결시킨다.
Node pointer = head;
while (pointer.next != null)
pointer = pointer.next;
pointer.next = createNode(data);
top = pointer.next;
}
}
public int pop() {
int popData;
if (!isEmpty()) { // 스택이 비어있지 않다면!! => 데이터가 있다면!!
popData = top.data; // pop될 데이터를 미리 받아놓는다.
Node pointer = head; // 현재 위치를 확인할 임시 노드 포인터
if (head == top) // 데이터가 하나라면
head = top = null;
else { // 데이터가 2개 이상이라면
while (pointer.next != top) // top을 가리키는 노드를 찾는다.
pointer = pointer.next;
pointer.next = null; // 마지막 노드의 연결을 끊는다.
top = pointer; // top을 이동시킨다.
}
return popData;
}
return -1; // -1은 데이터가 없다는 의미로 지정해둠.
}
}큐(Queue)
입력과 출력을 한 쪽 끝(front, rear)으로 제한
FIFO (First In First Out, 선입선출) : 가장 먼저 들어온 것이 가장 먼저 나옴
언제 사용?
버퍼, 마구 입력된 것을 처리하지 못하고 있는 상황, BFS
큐의 가장 첫 원소를 front, 끝 원소를 rear라고 부름
큐는 들어올 때 rear로 들어오지만, 나올 때는 front부터 빠지는 특성을 가짐
접근방법은 가장 첫 원소와 끝 원소로만 가능
큐 구현 코드
public class Queue<T> {
private Node<T> front; // 큐의 맨 앞을 가리키는 노드
private Node<T> rear; // 큐의 맨 뒤를 가리키는 노드
private int size; // 큐의 현재 크기
private static class Node<T> {
private T data;
private Node<T> next;
public Node(T data) {
this.data = data;
}
}
public Queue() {
front = null;
rear = null;
size = 0;
}
// 큐에 원소를 추가합니다.
public void enqueue(T item) {
Node<T> newNode = new Node<>(item);
if (isEmpty()) {
front = newNode; // 큐가 비어 있으면 front와 rear 모두 새 노드를 가리킴
rear = newNode;
} else {
rear.next = newNode; // 기존의 rear 노드의 다음 노드를 새 노드로 설정
rear = newNode; // rear를 새 노드로 업데이트
}
size++;
}
// 큐의 맨 앞 원소를 제거하고 반환합니다.
public T dequeue() {
if (isEmpty()) {
throw new IllegalStateException("Queue is empty!");
}
T item = front.data;
front = front.next; // front를 다음 노드로 변경
if (front == null) {
rear = null; // 큐가 비게 되면 rear도 null로 설정
}
size--;
return item;
}
public boolean isEmpty() {
return front == null;
}
public int size() {
return size;
}
}
일반 큐의 단점 : 큐에 빈 메모리가 남아 있어도, 꽉 차있는것으로 판단할 수도 있음
(rear가 끝에 도달했을 때)
이를 개선한 것이 '원형 큐'
논리적으로 배열의 처음과 끝이 연결되어 있는 것으로 간주함!
원형 큐는 초기 공백 상태일 때 front와 rear가 0
공백, 포화 상태를 쉽게 구분하기 위해 자리 하나를 항상 비워둠
(index + 1) % size로 순환시킨다### 원형 큐 구현 코드
public class CircularQueue<T> {
private T[] array; // 큐의 원소들을 저장하는 배열
private int front; // 첫 번째 원소의 인덱스를 가리킵니다.
private int rear; // 마지막 원소의 바로 다음 인덱스를 가리킵니다.
private int size; // 큐의 현재 크기
private int capacity; // 큐의 최대 크기
@SuppressWarnings("unchecked")
public CircularQueue(int capacity) {
this.capacity = capacity;
array = (T[]) new Object[this.capacity];
front = 0;
rear = 0;
size = 0;
}
// 큐에 원소를 추가합니다.
public void enqueue(T item) {
if (isFull()) {
throw new IllegalStateException("Queue is full!");
}
array[rear] = item;
rear = (rear + 1) % capacity; // 원형 큐의 핵심: 모듈로 연산을 사용하여 인덱스를 갱신
size++;
}
// 큐의 첫 번째 원소를 제거하고 반환합니다.
public T dequeue() {
if (isEmpty()) {
throw new IllegalStateException("Queue is empty!");
}
T item = array[front];
array[front] = null;
front = (front + 1) % capacity; // 원형 큐의 핵심: 모듈로 연산을 사용하여 인덱스를 갱신
size--;
return item;
}
// 큐의 첫 번째 원소를 반환합니다.
public T peek() {
if (isEmpty()) {
throw new IllegalStateException("Queue is empty!");
}
return array[front];
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == capacity;
}
public int size() {
return size;
}
}
rear+1%size가 front와 같으면 가득찬 것
원형 큐의 단점 : 메모리 공간은 잘 활용하지만, 배열로 구현되어 있기 때문에 큐의 크기가 제한
이를 개선한 것이 '연결리스트 큐'
연결리스트 큐는 크기가 제한이 없고 삽입, 삭제가 편리
enqueue 구현
public void enqueue(E item) {
Node oldlast = tail; // 기존의 tail 임시 저장
tail = new Node; // 새로운 tail 생성
tail.item = item;
tail.next = null;
if(isEmpty()) head = tail; // 큐가 비어있으면 head와 tail 모두 같은 노드 가리킴
else oldlast.next = tail; // 비어있지 않으면 기존 tail의 next = 새로운 tail로 설정
}
데이터 추가는 끝 부분인 tail에 한다.
기존의 tail는 보관하고, 새로운 tail 생성
큐가 비었으면 head = tail를 통해 둘이 같은 노드를 가리키도록 한다.
큐가 비어있지 않으면, 기존 tail의 next에 새로만든 tail를 설정해준다.
dequeue 구현
public T dequeue() {
// 비어있으면
if(isEmpty()) {
tail = head;
return null;
}
// 비어있지 않으면
else {
T item = head.item; // 빼낼 현재 front 값 저장
head = head.next; // front를 다음 노드로 설정
return item;
}
}
- 데이터는 head로부터 꺼낸다. (가장 먼저 들어온 것부터 빼야하므로)
- head의 데이터를 미리 저장해둔다.
- 기존의 head를 그 다음 노드의 head로 설정한다.
- 저장해둔 데이터를 return 해서 값을 빼온다.
이처럼 삽입은 tail, 제거는 head로 하면서 삽입/삭제를 스택처럼 O(1)에 가능하도록 구현이 가능하다.
Deque
자바에서의 덱은 인터페이스로 구현되었다. 덱 자료구조의 여러 연산들을 정의한 Deque 인터페이스가 있고 이를 구현한 ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList 등의 클래스가 있다.
Deque 인터페이스의 메소드는 다음과 같다
addFirst()
덱의 앞쪽에 엘리먼트를 삽입한다. 용량 제한이 있는 덱의 경우, 용량을 초과하면 예외(Exception)가 발생한다
offerFirst()
덱의 앞쪽에 엘리먼트를 삽입한다. 정상적으로 엘리먼트가 삽입된 경우 true가 리턴되며, 용량 제한에 걸리는 경우 false를 리턴한다.
addLast()
덱의 마지막 쪽에 엘리먼트를 삽입한다. 용량 제한이 있는 덱의 경우, 용량 초과시 예외가 발생한다
add()
addLast()와 동일
offerLast()
덱의 마지막 쪽에 엘리먼트를 삽입한다. 정상적으로 엘리먼트가 삽입된 경우 true가 리턴되며, 용량 제한에 걸리는 경우 false를 리턴한다.
removeFirst()
덱의 앞쪽에서 엘리먼트 하나를 뽑아서 제거한 다음 해당 엘리먼트를 리턴한다. 덱이 비어있으면 예외가 발생한다.
pollFirst()
덱의 앞쪽에서 엘리먼트 하나를 뽑아서 제거한 다음 해당 엘리먼트를 리턴한다. 덱이 비어있으면 null 이 리턴된다.
removeLast()
덱의 마지막 쪽에서 엘리먼트 하나를 뽑아서 제거한 다음 해당 엘리먼트를 리턴한다. 덱이 비어있으면 예외가 발생한다.
pollLast()
덱의 마지막 쪽에서 엘리먼트 하나를 뽑아서 제거한 다음 해당 엘리먼트를 리턴한다. 덱이 비어있으면 null 이 리턴된다.
remove()
removeFirst()와 동일
poll()
pollFirst()와 동일
getFirst()
덱의 앞쪽 엘리먼트 하나를 제거하지 않은채 리턴한다. 덱이 비어있으면 예외가 발생한다
peekFirst()
덱의 앞쪽 엘리먼트 하나를 제거하지 않은채 리턴한다. 덱이 비어있으면 null이 리턴된다.
getLast()
덱의 마지막쪽 엘리먼트 하나를 제거하지 않은채 리턴한다. 덱이 비어있으면 예외가 발생한다.
peekLast()
덱의 마지막 엘리먼트 하나를 제거하지 않은 채 리턴한다. 덱이 비어있으면 null이 리턴된다.
peek()
peekFirst()와 동일
removeFirstOccurrence(Object o)
덱의 앞쪽에서부터 탐색하여 입력한 Object o와 동일한 첫 엘리먼트를 제거한다. Object o 와 같은 엘리먼트가 없으면 덱에 변경이 발생하지 않는다.
removeLastOccurrence(Object o)
덱의 뒤쪽에서부터 탐색하여 입력한 Object o와 동일한 첫 엘리먼트를 제거한다. Object o 와 같은 엘리먼트가 없으면 덱에 변경이 발생하지 않는다.
element()
removeFirst()와 동일
addAll(Collection <? extends E c)
입력 받은 Collection의 모든 데이터를 덱의 뒤쪽에 삽입한다.
push()
addFirst()와 동일. 덱을 스택으로 사용할 때 쓰임
pop()
removeFirst()와 동일. 덱을 스택으로 사용할 때 쓰임
remove(Object o)
removeFirstOccurrence(Object o)와 동일
contain(Object o)
덱에 Object o와 동일한 엘리먼트가 포함되어 있는지 확인
size()
덱의 크기
iterator()
덱의 앞쪽부터 순차적으로 실행되는 이터레이터(iterator)를 얻어옴
descendingIterator()
덱의 뒤쪽부터 순차적으로 실행되는 이터레이터(iterator)를 얻어옴
덱의 예제
class TestClass {
public static void main(String[] args) throws InterruptedException {
System.out.println("Stack!!");
Deque<String> stack = new ArrayDeque<>();
stack.addFirst("Element1");
stack.addFirst("Element2");
stack.addFirst("Element3");
System.out.println(stack.removeFirst());
System.out.println(stack.removeFirst());
System.out.println(stack.removeFirst());
System.out.println("Queue!!");
Deque<String> queue = new ArrayDeque<>();
queue.addFirst("Element1");
queue.addFirst("Element2");
queue.addFirst("Element3");
System.out.println(queue.removeLast());
System.out.println(queue.removeLast());
System.out.println(queue.removeLast());
}
}