- 스택(Stack) 자료구조를 이해하고 활용한다
- 큐(Queue) 자료구조를 이해하고 활용한다
- 데크(Deque) 자료구조를 이해하고 활용한다
1. 스택(Stack) - 입/출력이 한쪽 끝단에서 모두 발생하며, 후입선출 특징을 갖는 자료구조
- 후입선출(LIFO: Last In First Out) 특성을 가지는 자료구조
- 스택의 기본 연산
- push: 스택의 맨 위에 새로운 요소를 추가
- pop: 스택의 맨 위에 있는 요소를 제거하고 반환
- peek: 스택의 맨 위에 있는 요소를 제거하지 않고 반환
- isEmpty: 스택이 비어 있는지 확인
- 활용 예시
- 실행취소(Undo) 기능
- 웹 브라우저의 뒤로가기
- 함수 호출 스택
스택 코드 예시
Java utill.Stack 라이브러리 활용
import java.util.Stack;
public class StackExample {
public static void main(String[] args) {
// 스택 생성
Stack<Integer> stack = new Stack<>();
// push 연산
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println("스택 상태: " + stack); // 출력: 스택 상태: [1, 2, 3]
// pop 연산
int poppedElement = stack.pop();
System.out.println("pop된 요소: " + poppedElement); // 출력: pop된 요소: 3
System.out.println("스택 상태: " + stack); // 출력: 스택 상태: [1, 2]
// peek 연산
int topElement = stack.peek();
System.out.println("스택의 최상단 요소: " + topElement); // 출력: 스택의 최상단 요소: 2
System.out.println("스택 상태: " + stack); // 출력: 스택 상태: [1, 2]
// isEmpty 연산
boolean isEmpty = stack.isEmpty();
System.out.println("스택이 비어 있는가? " + isEmpty); // 출력: 스택이 비어 있는가? false
}
}
Python - Stack 을 리스트로 구현
class Stack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
if not self.is_empty():
return self.stack.pop()
else:
return "Stack is empty"
def peek(self):
if not self.is_empty():
return self.stack[-1]
else:
return "Stack is empty"
def is_empty(self):
return len(self.stack) == 0
def __str__(self):
return str(self.stack)
# 스택 생성
stack = Stack()
# push 연산
stack.push(1)
stack.push(2)
stack.push(3)
print("스택 상태:", stack) # 출력: 스택 상태: [1, 2, 3]
# pop 연산
popped_element = stack.pop()
print("pop된 요소:", popped_element) # 출력: pop된 요소: 3
print("스택 상태:", stack) # 출력: 스택 상태: [1, 2]
# peek 연산
top_element = stack.peek()
print("스택의 최상단 요소:", top_element) # 출력: 스택의 최상단 요소: 2
print("스택 상태:", stack) # 출력: 스택 상태: [1, 2]
# isEmpty 연산
is_empty = stack.is_empty()
print("스택이 비어 있는가?", is_empty) # 출력: 스택이 비어 있는가? False
2. 큐 (Queue) - 한쪽에서는 입력만 다른 한쪽에서는 출력만 일어나는 선입선출 특성의 자료구조
- 선입선출(FIFO: First In First Out) 특징을 갖는 자료구조
- 흡사 줄을 서는 것과 비슷한 개념으로, 먼저 들어간 데이터가 먼저 나옵니다.
- 큐의 기본 연산
- enqueue: 큐의 끝에 요소를 추가
- dequeue: 큐의 앞에서 요소를 제거하고 반환
- 활용 예시
- 프린터 대기열: 먼저 요청된 인쇄 작업부터 차례대로 처리
- 프로세스 스케줄링
- 데이터 스트림 처리
큐 예시 코드
import java.util.LinkedList;
import java.util.Queue;
public class LinkedListQueueExample {
public static void main(String[] args) {
// 큐 생성
Queue<Integer> queue = new LinkedList<>();
// enqueue 연산
queue.add(1); // 또는 queue.offer(1);
queue.add(2); // 또는 queue.offer(2);
queue.add(3); // 또는 queue.offer(3);
System.out.println("큐 상태: " + queue); // 출력: 큐 상태: [1, 2, 3]
// dequeue 연산
int removedElement = queue.poll(); // 또는 queue.remove();
System.out.println("제거된 요소: " + removedElement); // 출력: 제거된 요소: 1
System.out.println("큐 상태: " + queue); // 출력: 큐 상태: [2, 3]
// peek 연산
int frontElement = queue.peek(); // 또는 queue.element();
System.out.println("큐의 앞에 있는 요소: " + frontElement); // 출력: 큐의 앞에 있는 요소: 2
System.out.println("큐 상태: " + queue); // 출력: 큐 상태: [2, 3]
// isEmpty 연산
boolean isEmpty = queue.isEmpty();
System.out.println("큐가 비어 있는가? " + isEmpty); // 출력: 큐가 비어 있는가? false
}
}
Python - collections 모듈의 deque 를 통해 큐를 구현
from collections import deque
class Queue:
def __init__(self):
self.queue = deque()
def enqueue(self, item):
self.queue.append(item)
def dequeue(self):
if not self.is_empty():
return self.queue.popleft()
else:
return "Queue is empty"
def peek(self):
if not self.is_empty():
return self.queue[0]
else:
return "Queue is empty"
def is_empty(self):
return len(self.queue) == 0
def __str__(self):
return str(list(self.queue))
# 큐 생성
queue = Queue()
# enqueue 연산
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print("큐 상태:", queue) # 출력: 큐 상태: [1, 2, 3]
# dequeue 연산
removed_element = queue.dequeue()
print("제거된 요소:", removed_element) # 출력: 제거된 요소: 1
print("큐 상태:", queue) # 출력: 큐 상태: [2, 3]
# peek 연산
front_element = queue.peek()
print("큐의 앞에 있는 요소:", front_element) # 출력: 큐의 앞에 있는 요소: 2
print("큐 상태:", queue)
Queue 클래스를 정의하고, enqueue, dequeue, peek, is_empty 메서드를 구현
(Java에서 제공하는 Queue 인터페이스와 유사한 기능구현)
Stack 에서 peak : 가장 상단에 있는 요소 반환 (리스트의 마지막 요소에 해당)
Queue 에서 peak : 가장 앞에 있는 요소 반환 (리스트의 첫번째 요소에 해당)
3. 데크(Deque) - 큐와 아주 유사하지만 양쪽 끝단에서 모두 입/출력이 가능한 자료구조
- 양쪽 끝에서 데이터 추가 및 제거 가능: 앞쪽이나 뒤쪽에서 데이터를 넣고 뺄 수 있어요.
- 유연한 자료구조: 덱은 스택처럼 사용할 수도 있고, **
큐**처럼 사용할 수도 있어요. - 데크의 기본 연산
- addFirst(e): 요소를 데크의 앞에 삽입합니다.
- addLast(e): 요소를 데크의 뒤에 삽입합니다.
- removeFirst(): 데크의 앞에서 요소를 제거하고 반환합니다.
- removeLast(): 데크의 뒤에서 요소를 제거하고 반환합니다.
- peekFirst(): 데크의 앞 요소를 제거하지 않고 반환합니다.
- peekLast(): 데크의 뒤 요소를 제거하지 않고 반환합니다.
Java
import java.util.Deque;
import java.util.ArrayDeque;
public class DequeExample {
public static void main(String[] args) {
// Deque 생성
Deque<Integer> deque = new ArrayDeque<>();
// 앞에 요소 추가
deque.addFirst(1);
deque.addFirst(2);
deque.addFirst(3);
System.out.println("Deque 상태 (앞에 추가): " + deque); // 출력: [3, 2, 1]
// 뒤에 요소 추가
deque.addLast(4);
deque.addLast(5);
System.out.println("Deque 상태 (뒤에 추가): " + deque); // 출력: [3, 2, 1, 4, 5]
// 앞에서 요소 제거
int front = deque.removeFirst();
System.out.println("앞에서 제거된 요소: " + front); // 출력: 3
System.out.println("Deque 상태 (앞에서 제거): " + deque); // 출력: [2, 1, 4, 5]
// 뒤에서 요소 제거
int back = deque.removeLast();
System.out.println("뒤에서 제거된 요소: " + back); // 출력: 5
System.out.println("Deque 상태 (뒤에서 제거): " + deque); // 출력: [2, 1, 4]
// 앞 요소 확인
int peekFront = deque.peekFirst();
System.out.println("앞 요소: " + peekFront); // 출력: 2
// 뒤 요소 확인
int peekBack = deque.peekLast();
System.out.println("뒤 요소: " + peekBack); // 출력: 4
// 비어 있는지 확인
boolean isEmpty = deque.isEmpty();
System.out.println("Deque가 비어 있는가? " + isEmpty); // 출력: false
}
}
Python
from collections import deque
# Deque 생성
deque = deque()
# 앞에 요소 추가
deque.appendleft(1)
deque.appendleft(2)
deque.appendleft(3)
print("Deque 상태 (앞에 추가):", list(deque)) # 출력: [3, 2, 1]
# 뒤에 요소 추가
deque.append(4)
deque.append(5)
print("Deque 상태 (뒤에 추가):", list(deque)) # 출력: [3, 2, 1, 4, 5]
# 앞에서 요소 제거
front = deque.popleft()
print("앞에서 제거된 요소:", front) # 출력: 3
print("Deque 상태 (앞에서 제거):", list(deque)) # 출력: [2, 1, 4, 5]
# 뒤에서 요소 제거
back = deque.pop()
print("뒤에서 제거된 요소:", back) # 출력: 5
print("Deque 상태 (뒤에서 제거):", list(deque)) # 출력: [2, 1, 4]
# 앞 요소 확인
peekFront = deque[0]
print("앞 요소:", peekFront) # 출력: 2
# 뒤 요소 확인
peekBack = deque[-1]
print("뒤 요소:", peekBack) # 출력: 4
# 비어 있는지 확인
isEmpty = len(deque) == 0
print("Deque가 비어 있는가?", isEmpty) # 출력: False
'Algorithm > 자료구조' 카테고리의 다른 글
Heap, Hash Table (0) | 2024.07.25 |
---|---|
브루트포스 알고리즘과 슬라이딩 윈도우 알고리즘 (0) | 2024.07.18 |
스택 (Stack) 과 큐 (Queue) 자료구조에 대해 쉽게 알아보자 (0) | 2024.06.23 |