스택 (Stack)
- 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 선형 구조로, 가장 최근에 스택에 추가한 항목이 가장 먼저 나오는 후입선출 방식
- 재귀적으로 함수를 호출해야 하는 경우 임시 데이터를 스택에 넣어두고 재귀함수를 빠져나와 백트랙할 때는 스택에 넣어 두었던 임시 데이터를 빼내야 하는데, 스택은 이런 일련의 행위를 직관적으로 가능하게 해준다.
구현 (JAVA)
import java.util.ArrayList;
import java.util.EmptyStackException;
public class Stack<E> extends ArrayList<E> {
public Stack() {
super();
}
public Stack(int capacity) {
super(capacity);
}
public E push(E item) {
add(item);
return item;
}
public E pop() {
// 마지막 요소 삭제, 스택이 비어있으면 EmptyStackException
return remove(size() - 1);
}
public E peek() {
int len = size();
if (len == 0) {
throw new EmptyStackException();
}
// 마지막 요소 반환
return get(len - 1);
}
public boolean empty() {
return size() == 0;
}
public int search(E value) {
// 끝에서부터 객체를 찾는다.
int i = lastIndexOf(value);
if (i >= 0) {
return size() - i;
}
return -1;
}
}
큐 (Queue)
- 한 쪽 끝에서는 자료를 추가하고, 다른 쪽에서는 뺄 수 있는 구조로, 먼저 집어넣은 데이터가 가장 먼저 나오는 선입선출 방식
- 큐는 데크나 우선순위 큐 같은 큐의 변형들은 여러 분야에서 매우 유용하게 쓰이며, 너비 우선 탐색(BFS)나 캐시 등을 구현하는데도 활용된다.
구현 (JAVA)
import java.util.LinkedList;
import java.util.NoSuchElementException;
public class Queue<E> extends LinkedList<E> {
static class Node<E> {
E data;
Node<E> next;
Node(E data) {
this.data = data;
this.next = null;
}
}
private Node<E> head;
private Node<E> tail;
private int size;
public Queue() {
this.head = null;
this.tail = null;
this.size = 0;
}
@Override
public boolean offer(E value) {
Node<E> newNode = new Node<>(value);
if (size == 0) {
head = newNode;
}
else {
tail.next = newNode;
}
tail = newNode;
size++;
return true;
}
@Override
public E poll() {
if (size == 0) {
return null;
}
E value = head.data;
head = head.next;
size--;
return value;
}
@Override
public E remove() {
E value = poll();
if (value == null) {
throw new NoSuchElementException();
}
return value;
}
@Override
public E peek() {
if (size == 0) {
return null;
}
return head.data;
}
@Override
public E element() {
E element = peek();
if (element == null) {
throw new NoSuchElementException();
}
return element;
}
}
링 버퍼
- 선입선출 구조를 지닌다는 점에서 기존의 큐와 동일하지만, 마지막 위치가 시작 위치와 연결되는 원형 구조
- 앞 쪽에 공간이 남아 있다면 동그랗게 연결해 앞쪽으로 추가할 수 있기 때문에 공간의 재활용이 가능한 구조
데크 (Deque)
- 더블 엔디드 큐의 줄임말로, 큐를 일반화하여 양쪽에서 삭제와 삽입을 모두 처리할 수 있다.
'Python > Algorithm' 카테고리의 다른 글
트리의 종류와 트리 순회 (0) | 2022.02.26 |
---|---|
최단 경로 알고리즘 (0) | 2022.02.25 |
그래프와 그래프 탐색 (0) | 2022.02.25 |
해시 테이블 (0) | 2022.02.24 |
배열과 연결리스트 (0) | 2022.02.22 |