스택(Stack)이란?
스택(stack)이란 책을 쌓는 것처럼 쌓아 올려진 형태의 자료구조를 말한다.
가령, A,B,C라는 책을 상자에 넣고 뺀다고 생각해보자.
넣을 때는 A,B,C 순으로 들어가겠지만, 뺄때는 C,B,A순으로 빼내어야 한다.
이런 구조를 후입선출(LIFO, Last-In-First-Out) 구조라고 한다.
스택의 특징
앞서 설명했듯, 스택은 먼저 들어간 것이 가장 나중에 나오는 형태이다.
따라서 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 접근 할 수 있다는 특징이 있으며 이러한 특징 때문에 역순 문자열 만들기, 실행 취소, 웹 브라우저 방문 기록(뒤로가기) 등의 분야에서 활용된다.
스택은 top에서 삽입과 삭제의 연산이 같이 이루어지며, 삽입 연산을 push, 삭제 연산을 pop을 통하여 진행한다.
그 밖에 peek 메서드를 통하여 스택의 맨 위 요소를 반환하여 사용 할 수 있으며, search 메서드를 통하여 지정된 요소가 스택 맨 위에서 얼마나 멀리 떨어져 있는지 알 수 있다.
자주 사용하는 메서드는 다음과 같다.
- push(E item): 스택의 맨 위에 요소를 추가합니다. 요소는 제네릭 타입 E로 지정되며, 맨 위에 추가되므로 가장 최근에 추가된 요소가 스택의 맨 위에 위치합니다.
- pop(): 스택의 맨 위 요소를 제거하고 반환합니다. 스택이 비어있을 때 이 메서드를 호출하면 EmptyStackException이 발생합니다.
- peek(): 스택의 맨 위 요소를 반환하되, 제거하지는 않습니다. 스택이 비어있을 때 이 메서드를 호출하면 EmptyStackException이 발생합니다.
- empty(): 스택이 비어있는지 여부를 확인합니다. 비어있으면 true를, 아니면 false를 반환합니다.
- search(Object o): 스택에서 지정된 요소를 찾고, 해당 요소가 스택 맨 위에서 얼마나 멀리 떨어져 있는지 반환합니다. 찾지 못하면 -1을 반환합니다.
import java.util.Stack;
public class Main {
//입력&출력 부분
public static void main(String[] args){
//스택의 선언
Stack<Integer> st = new Stack<>();
//스택에 요소 삽입
st.push(1);
//스택의 가장 상위의 요소 출력
st.peek();
//스택의 가장 상위 요소 삭제
st.pop();
//스택 초기화
st.clear();
}
}
주의할 것은 pop() 사용시 가장 맨 위의 요소를 반환하고 제거하지만, peak()는 스택의 맨 위의 요소를 반환하되 요소를 제거하지는 않는다.
따라서, 둘을 헷갈리지 말고 필요에 맞게 사용해야 할 것이다.
큐(Queue)란?
큐(Queue)는 스택과는 달리 선입선출(FIFO, First-In-First-Out) 구조라고 한다.
흔히 말하는 대기열을 생각해 보면된다.
음식점에서 A,B,C라는 사람이 대기번호를 순서대로 받았다고 생각해보자.
당연히 입장 순서는 A,B,C순으로 먼저온 사람이 먼저 들어가게 될 것이다.
큐의 특징
큐는 정해진 곳에서 삽입, 삭제가 이루어지는 스택과 달리 한쪽 끝에서는 삽입 작업이, 반대 끝에서는 삭제 작업이 이루어 진다.
삭제 연산이 수행 되는곳을 프론트(front)라고 하며 삽입연산만 이루어 지는 곳을 리어(rear)라고 한다.
또한, 큐의 리어에서 이루어지는 삽입연산을 인큐(enQueue), 프론트에서 이루어지는 삭제연산을 디큐(deQueue)라고 부른다.
큐의 경우 일반적으로 java.util.Queue 인터페이스를 통해 구현하며, 여러 구현체가 있지만 자주 사용되는 것은 LinkedList와 ArrayDeque이다.
대기열을 구현할 수 있다는 특징덕에 다양한 곳에서 사용 되며, 특히 데이터 처리의 순서를 관리하거나, 작업 대기열(워크 플로우), 네트워크 패킷 처리, 그래프 탐색 등에 활용된다.
주요 메서드는 다음과 같다.
- offer(E e): 큐에 요소를 추가합니다. 요소는 제네릭 타입 E로 지정되며, 큐의 끝에 추가됩니다. 만약 큐가 공간 부족으로 요소를 추가할 수 없는 경우 false를 반환하며, 그 외에는 true를 반환합니다.
- poll(): 큐의 맨 앞 요소를 제거하고 반환합니다. 큐가 비어있을 때 이 메서드를 호출하면 null을 반환합니다.
- peek(): 큐의 맨 앞 요소를 반환하되, 제거하지 않습니다. 큐가 비어있을 때 이 메서드를 호출하면 null을 반환합니다.
- element(): 큐의 맨 앞 요소를 반환하되, 제거하지 않습니다. 큐가 비어있을 때 이 메서드를 호출하면 NoSuchElementException을 발생시킵니다.
- remove(Object o): 큐에서 지정된 요소를 찾아서 제거합니다. 요소가 큐에 없을 경우 변경 없이 그대로 유지됩니다.
- isEmpty(): 큐가 비어있는지 여부를 확인합니다. 비어있으면 true를, 아니면 false를 반환합니다.
import java.util.LinkedList;
import java.util.Queue;
public class Main {
//입력&출력 부분
public static void main(String[] args){
//queue의 선언
Queue<Integer> arr = new LinkedList<>();
//queue의 삽입
arr.offer(1);
//queue의 맨 앞 요소 반환 (비어있을 시 null)
arr.peek();
//queue의 맨 앞 요소 반환 (비어있을 시 Exception 발생)
arr.element();
//queue의 맨 앞 요소 반환 및 제거
arr.poll();
}
}
특이한 것은, Queue는 Queue로 선언하지 않기 때문에, Queue와 LinkedList를 둘다 import 해주어야 한다.
또 한, peek과 element가 있는데, peek의 경우 queue가 비어있는 경우 null을 리턴하지만 (즉, Exception이 발생하지 않는다) element의 경우 Exception을 발생시킨다는 점이다.