Stack
스택은 후입선출 구조를 가지는 자료구조이다.
출력 시 가장 위에서부터 아래로, 내림차순으로 출력된다.
스택은 top으로 정한 곳을 통해서만 접근 가능하다.
top의 가장 위에 있는 자료는 가장 최근 들어온 자료이며
삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다.
스택에서 자료를 삭제할 때 top을 통해서 가능하다.
스택에서 top을 통해 삽입하는 연산을 push, 삭제하는 연산을 pop이라고 한다.
따라서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다.
import java.util.Stack;
public class StackExample {
public static void main(String[] args) {
// 정수형 데이터를 담을 스택 생성
Stack<Integer> stack = new Stack<>();
// 스택에 데이터 추가 (push)
stack.push(10);
stack.push(20);
stack.push(30);
// 스택의 맨 위 데이터 확인 (peek)
System.out.println("Top element: " + stack.peek());
// 스택에서 데이터 제거 및 출력 (pop)
while (!stack.isEmpty()) {
System.out.println("Popped element: " + stack.pop());
}
}
}| push(E item) | 스택에 데이터를 추가한다. 새로운 데이터는 항상 스택의 맨 위에 추가된다 |
| pop() | 스택의 맨 위에서 데이터를 제거하고 반환한다 |
| peek() | 스택의 맨 위에 있는 데이터를 반환하지만 제거는 하지 않는다 |
| Empty() | 스택이 비어있는지의 여부를 판단한다 |
| search(Object o) | 스택에서 특정 객체의 위치(인덱스)를 찾아 반환한다. 맨 위가 첫번째다. |
활용 예시
- 웹 브라우저 방문기록: 가장 최근에 열린 페이지부터 보여준다
- 역순 문자열 만들기: 가장 최근에 입력된 문자부터 출력한다
- 실행 취소: 가장 최근에 실행된 것부터 실행을 취소한다
- 후위 표기법 계산
- 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
Queue
한쪽 끝에서는 삽입, 다른 쪽에서는 삭제 작업이 양쪽으로 이루어지는
선입선출 구조를 가지는 자료구조이다.
스택은 삽입삭제가 한쪽으로 이루어진다면 큐는 한쪽에서는 삽입, 다른 쪽에서는 삭제 작업이
이루어진다.
이때 삭제연산만 수행되는 곳을 프론트, 삽입연산만 이루어지는 곳을 리어로 정하여 각각의
연산작업만 수행된다.
이때, 리어에서 수행되는 삽입연산을 인큐
프론트에서 이루어지는 삭제연산을 디큐라고 부른다.
활용 예시
- 데이터가 입력된 시간 순서대로 처리해야할 필요가 있는 상황에 이용한다.
- 우선순위가 같은 작업 예약 ex) 프린터의 인쇄 대기열
- 은행 업무
- 콜센터 고객 대기시간
- 프로세스 관리
- 너비 우선 탐색(BFS, Breadth-First Search) 구현
- 캐시 구현
import java.util.LinkedList;
import java.util.Queue;
public class QueueExample {
public static void main(String[] args) {
// 정수형 데이터를 담을 큐 생성
Queue<Integer> queue = new LinkedList<>();
// 큐에 데이터 추가 (offer)
queue.offer(10);
queue.offer(20);
queue.offer(30);
// 큐의 맨 앞 데이터 확인 (peek)
System.out.println("Front element: " + queue.peek());
// 큐에서 데이터 제거 및 출력 (poll)
while (!queue.isEmpty()) {
System.out.println("Polled element: " + queue.poll());
}
}
}| offer(E e) | 큐에 데이터 추가 |
| poll() | 큐의 맨 앞에서 데이터를 제거하고 반환 |
| peek() | 큐의 맨 앞에 있는 데이터를 반환하지만 |
| isEmpty() | 큐가 비어있는지의 여부 판단 |
| size() | 큐에 저장된 데이터의 개수 반환 |
List
여러 요소들을 순서대로 저장하는 자료구조인데 순서가 있고, 중복을 허용한다는 특징이 있다.
스택, 큐 또한 크게 본다면 리스트라 할 수 있다.
순차 리스트는 배열로 구현한 리스트로서 구현이 쉽고 속도가 빠르다.
하지만 배열 특성상 동적으로 크기를 줄이기 어렵다.
Singly LinkedList
- 각 노드가 데이터와 다음 노드를 가리키는 포인터로 이루어져 있다.
- 마지막 노드는 다음 노드를 가리키는 포인터가 null 혹은 nil이다
- 데이터의 추가와 삭제가 다른 자료구조에 비해 비교적 쉽다
Doubly LinkedList
- 각 노드가 데이터와 이전 노드와 다음 노드를 가리키는 포인터로 이루어져있다.
- 이전 노드와 다음 노드를 모두 쉽게 접근할 수 있어 데이터의 삽입, 삭제, 검색이 용이하다
- 각 노드가 많은 메모리를 사용한다.
// LinkedList의 노드를 나타내는 클래스
class ListNode {
int val; // 노드가 저장하는 데이터
ListNode next; // 다음 노드를 가리키는 포인터
// 생성자
ListNode(int val) {
this.val = val;
this.next = null;
}
}
// LinkedList 자료구조를 나타내는 클래스
class MyLinkedList {
ListNode head; // 첫 번째 노드를 가리키는 포인터
// 생성자: 빈 LinkedList 생성
public MyLinkedList() {
this.head = null;
}
// 맨 앞에 노드 삽입
public void addAtHead(int val) {
ListNode newNode = new ListNode(val);
newNode.next = head;
head = newNode;
}
// 특정 위치 뒤에 노드 삽입
public void addAtIndex(int index, int val) {
if (index < 0) {
addAtHead(val);
return;
}
ListNode newNode = new ListNode(val);
ListNode current = head;
int count = 0;
while (current != null && count < index - 1) {
current = current.next;
count++;
}
if (current == null) {
return;
}
newNode.next = current.next;
current.next = newNode;
}
// 맨 뒤에 노드 삽입
public void addAtTail(int val) {
ListNode newNode = new ListNode(val);
if (head == null) {
head = newNode;
return;
}
ListNode current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
// 특정 위치의 노드 삭제
public void deleteAtIndex(int index) {
if (index < 0 || head == null) {
return;
}
if (index == 0) {
head = head.next;
return;
}
ListNode current = head;
int count = 0;
while (current != null && count < index - 1) {
current = current.next;
count++;
}
if (current == null || current.next == null) {
return;
}
current.next = current.next.next;
}
// LinkedList 출력
public void printList() {
ListNode current = head;
while (current != null) {
System.out.print(current.val + " ");
current = current.next;
}
System.out.println();
}
}
// LinkedList 사용 예시
public class Main {
public static void main(String[] args) {
MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1, 2); // 1 -> 2 -> 3
linkedList.printList(); // 출력: 1 2 3
linkedList.deleteAtIndex(1); // 1 -> 3
linkedList.printList(); // 출력: 1 3
}
}| add(E element) | 리스트에 요소 추가 |
| get(int index) | 리스트에 지정된 인덱스 반환 |
| set(int index, E element) | 리스트에 지정된 인덱스 요소 설정 |
| remove(int index) | 리스트에 지정된 인덱스 요소 제거 |
| size() | 리스트에 저장된 요소의 개수 반환 |
| isEmpty() | 리스트가 비어있는지의 여부 |
| contains(Object o) | 특정 객체가 포함되어있는지의 여부 |
| indexOf(Object o) | 특정 객체의 인덱스 반환. 없으면 -1을 반환한다 |
| clear() | 리스트의 모든 요소 제거 |
스택, 큐, 리스트
| 자료구조 | 공통점 | 차이 |
| 리스트(List) | 선형 자료구조, 순서가 있음 | 읽기, 삽입, 삭제를 리스트 어느 곳에서나 가능 |
| 스택(Stack) | 삽입과 삭제를 리스트의 한쪽(top)에서 행함 | |
| 큐(Queue) | 삽입은 리스트의 레어에서 하고, 삭제는 삽입의 반대쪽 front 에서 행함 |
'자료구조 > 알고리즘 기초수학' 카테고리의 다른 글
| StringBuilder와 StringTokenizer 비교 (0) | 2024.07.18 |
|---|---|
| Hash Table / Deque (5) | 2024.07.16 |
| 이항계수, 동적계획법 (0) | 2024.07.06 |
| 유클리드 호제법 (0) | 2024.07.04 |
| 에라토스테네스의 체 (1) | 2024.07.02 |
