스택, 큐, 데크

Algorithm/자료구조

스택, 큐, 데크

Albosa2lol 2024. 7. 24. 20:37

스택(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

현재글스택, 큐, 데크

A little bit of skill

運七技三 - 다가올 운칠을 위하여 기삼을 다지는 블로그

항해99, 코딩테스트 준비, 장원님짱짱맨, =, thymeleaf, json, 99클럽, AOP, java, Til, 개발자 취업, gradle, 세상에이런일이, Spring, lombok,

Today :
Yesterday :

일	월	화	수	목	금	토
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

A little bit of skill