누가 공부할 것인가

<목표>

https://quswjddms.tistory.com/17

<결과>

https://quswjddms.tistory.com/18

<오늘의 목표>

앞서 배운 내용 복습하기

다른 팀원들이 공부한 내용 읽고 공부하기

관련 문제 풀기

<활동 내역>

을 뭐라고 써야할까...???

<회고>

프로그래밍 또한 하나의 언어를 토대로 하는 활동이기 때문에 쉬는 시간이 길수록 많이 까먹게 되는 것 같다.

2학년 때 배울 Java와 알고리즘에 관한 교재를 미리 공부해보면서 새로운 개념들을 익히게 되었다. 그 과정에서 교재만으로는 이해하기 어려운 부분들이 있었고, 실습과 예제의 중요성을 익힌 것 같다.

복습하는 과정에서 얼마전에 한 내용을 다시 공부하는 것임에도 기억이 나지 않거나 어려운 부분들이 꽤나 많았다. 제대로 스스로 해낼 수 있을 때까지 반복하는 과정이 필요하다고 느꼈다.

<목표>

자바와 함께하는 자료구조라는 교재를 가지고 공부하며 그동안 공부했던 내용들을 복습한다.

(헷갈린 부분 복습)

<결과>

스택: 한 쪽 끝에서만 항목을 삭제하고 새로운 항목을 저장하는 자료구조

push와 pop연산은 항상 스택의 가장 위에서 수행 --> 스택의 가장 위의 항목을 가지고 있는 변수(top)가 필요

배열로 스택을 구현한 ArrayStack 클래스

import java.util.EmptyStackException;

public class ArrayStack<E> {
	private E s[];
    private int top;
    
    public ArrayStack() {
    	s = (E[]) new Object[1]; // 초기에 크기가 1인 배열 생성
        top = -1;
    }
    
    public int size() {
    	return top+1;
    }
    
    public boolean isEmpty() {
    	return (top == -1);
    }
    
    private void resize(int newSize) {
    	Object[] t = new Object[newSize];
        for (int i=0; i<size(); i++) {
        	t[i] = s[i];
        }
        s = (E[]) t;
    }
    
    public E peek() {
    	if (isEmpty()) {
        	throw new EmptyStackException();
        }
        return s[top];
    
    public void push(E newItem) {
    	if (size() == s.length) { // 클래스 내부에서 메소드 호출할때는 이런 형태로 풀러도 됨
        	resize(2*s.length);
        }
        s[++top] = newItem;
    }
    
    public E pop() {
    	if (isEmpty()) {
        	throw new EmptyStackException();
        }
        E item = s[top];
        s[top--] = null; // pop할 대상을 리스트의 참조에서 삭제. 가비지 컬렉션이 나중에 샤샥하고 없애줌
        if (size() > 0 && size()==s.length/4) {
        	resize(s.length/2);
        }
        return item;
    }
}

단순연결리스트로 구현한 스택 클래스

import java.util.EmptyStackException;

public class ListStack <E> {
	private Node<E> top;
    private int size;
    
    public ListStack() {
    	top = null;
        size = 0;
    }
    
    public int size() {
    	return size;
    }
    
    public boolean isEmpty() {
    	return size == 0;
    }
    
    public E peek() {
    	if (isEmpty()) {
        	throw new EmptyStackException();
        }
        return top.getItem();
    }
    
    public void push(E newItem) {
    	Node newNode = new Node(newItem, top);
        top = newNode;
        size++;
    }
    
    public E pop() {
    	if (isEmpty()) {
        	throw new EmptyStackException();
        }
        E topItem = top.getItem();
        top = top.getNext();
        size--;
        return topItem;
    }
}

큐: 삽입과 삭제가 양 끝에서 각각 수행되는 자료구조 (1차원 배열 or 단순연결리스트)

front: 큐의 가장 앞의 항목을 가리키는 변수

rear: 가장 뒤에 있는 항목을 가리키는 변수

ListQueue 클래스

import java.util.NoSuchElementException;

public class ListQueue <E> {
	private Node<E> front, rear;
    private int size;
    
    public ListQueue() {
    	front = rear = null;
        size = 0;
    }
    
    public int size() {
    	return size;
    }
    
    public boolean isEmpty() {
    	return size()==0;
    }
    
    public void add(E newItem) {
    	Node newNode = new Node(newItem, null);
        if (isEmpty()) {
        	front = newNode;
        } else {
        	rear = newNode;
        }
        size++;
    }
    
    public E remove() {
    	if (isEmpty()) {
        	throw new NoSuchElementException();
        }
        E frontItem = front.getItem();
        front = front.getNext();
        // 큐가 empty이면 이때 front는 이미 null을 가리킴.
        // 맨마지막 원소는 next에 null 값을 갖고 있기 때문
        if (isEmpty()) {
        	rear = null;
        }
        size--;
        return frontItem;
    }
}

데크: 양쪽 끝에서 삽입과 삭제를 허용하는 자료구조 (스택 + 큐)

(( 이중연결리스트가 더 적합

백준 #10773

나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다.

재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다.

재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.

재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int K = sc.nextInt(); 
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < K; i++) {
            int num = sc.nextInt();

            if (num == 0) {
                if (!stack.isEmpty()) {
                    stack.pop(); 
                }
            } else {
                stack.push(num); 
            }
        }

        int sum = 0;
        for (int n : stack) {
            sum += n;
        }

        System.out.println(sum);
    }
}

백준 #1991

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Node {
    char value;
    Node left;
    Node right;

    public Node(char value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

public class Main {
    static Node[] tree;

    public static void preorder(Node node) {
        if (node == null) return;
        System.out.print(node.value);
        preorder(node.left);
        preorder(node.right);
    }

    public static void inorder(Node node) {
        if (node == null) return;
        inorder(node.left);
        System.out.print(node.value);
        inorder(node.right);
    }

    public static void postorder(Node node) {
        if (node == null) return;
        postorder(node.left);
        postorder(node.right);
        System.out.print(node.value);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        tree = new Node[N + 1]; 

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine()); 
            char parentValue = st.nextToken().charAt(0);
            char leftValue = st.nextToken().charAt(0);
            char rightValue = st.nextToken().charAt(0);
            
            if (tree[parentValue - 'A'] == null) { 
                tree[parentValue - 'A'] = new Node(parentValue);
            }
            if (leftValue != '.') { 
                tree[leftValue - 'A'] = new Node(leftValue); 
                tree[parentValue - 'A'].left = tree[leftValue - 'A'];
            }
            if (rightValue != '.') { 
                tree[rightValue - 'A'] = new Node(rightValue); 
                tree[parentValue - 'A'].right = tree[rightValue - 'A']; 
            }
        }

        
        preorder(tree[0]);
        System.out.println();
       
        inorder(tree[0]);
        System.out.println();
        
        postorder(tree[0]);
        System.out.println();
    }
}

<목표>

자바와 함께하는 자료구조라는 교재를 가지고 공부하기

<활동내역>

5.1 이진 탐색 트리

이진 탐색: 정렬된 데이터의 중간에 위치한 항목을 기준으로 데이터를 두 부분으로 나누어 가며 특정 항목을 찾는 탐색 방법 / 가장 기본적인 트리 형태의 자료구조 ( 특징: 하나의 트리를 중위순회하면 정렬된 출력을 얻음 )

이진트리 탐색 조건) n의 왼쪽 서브트리에 있는 노드에 저장된 키 < 각 노드 n에 저장된 키 < n의 오른쪽 서브트리에 있는 노드의 키

균형 이진탐색트리,  B-트리, 다방향 탐색트리 = 이진탐색트리에 기반한 자료구조

5.1.1 이진 탐색 트리 클래스

public class Node <Key extends Comparable<Key>, Value> {
	private Key id;
    private Value name;
    private Node left, right;
    
    prublic Node(Key newId, Value newName) { // 노드 생성자
    	id = newId;
        name = newName;
        left = right = null;
    }
    
    // get과 set 메소드들
    public Key getKey() {
    	return id;
    }
    
    public Value getValue() {
    	return name;
    }
    
    public Node getLeft() {
    	return left;
    }
    
    public Node getRight() {
    	return right;
    }
    
    public void setKey(Key newId) {
    	id = newId;
    }
    
    public void setValue(Value newName) {
    	name = newName;
    }
    
    public void setLeft(Node newLeft) {
    	left = newLeft;
    }
    
    public void setRight(Node newRight) {
    	right = newRight;
    }

이진탐색트리 클래스

public class BST<Key extends Comparable<Key>, Value> {
	public Node root;
    public Node getRoot() {
    	return root;
    }
    public BST(Key newId, newName) { // BST 생성자
    	root = new Node(newId, newName);
    }
    // get, put, min, deleteMin, delete
    // 메소드들 선언

5.1.2 탐색 연산

항상 루트에서 시작

public Value get(Key k) {
	return get(root, k);
}

public Value get(Node n, Key k) {
	if (n == null) { // k를 발견 못함
    	return null;
    }
    int t = n.getKey().compareTo(k);
    if (t > 0) {
    	return get(n.getLeft(), k);
    } else if (t < 0) {
    	return get(n.getRight(), k);
    } else {
    	return (Value) n.getValue();
    }

get() 메소드의 탐색 = 메소드 오버로딩을 활용하여 2단계로 구현

5.1.3 삽입 연산

- 탐색 연산과 거의 동일

-  탐색 연산의 마지막에서 null이 반환되어야 할 상황에서 null을 반환하는 대신, 삽입하고자 하는 값을 갖는 새로운 노드를 생성하고 이 노드를 부모노드와 연결하면 삽입 연산이 완료됨

public void put(Key k, Value v) {
	root = put(root, k, v);
}

public Node put(Node n, Key k, Value v) {
	if (n == null) {
    	return new Node(k, v);
    }
    int t = n.getKey().compareTo(k);
    if (t > 0) { // 왼쪽 서브트리에 삽입
    	n.setLeft(put(n.getLeft(), k, v));
    } else if (t < 0) { // 오른쪽 서브트리에 삽입
    	n.setRight(put(n.getRight(), k, v));
    } else { // 노드 n의 name을 v로 갱신
    	n.setValue(v);
    }
    return n; // 요 return이 루트로 올라가면서 재연겨하는 과정임

5.1.4 최솟값 찾기

루트로부터 왼쪽 자식을 따라 내려가며, null을 만났을 때 null의 부모가 가진 id = 최솟값

main() 메소드

public Key min() {
	if (root == null) {
    	return null;
    }
    return (Key) min(root).getKey();
}

private Node min(Node n) {
	if (n.getLeft() == null) {
    	return n;
    }
    return min(n.getLeft());
}

5.1.5 최솟값 삭제 연산

최솟값을 가진 노드  x를 찾아낸 뒤, x의 부모노드 p와 x의 오른쪽 자식노드 c를 연결

public void deleteMin() {
	if (root == null) {
    	System.out.println("empty 트리");
    }
    root = deleteMin(root); // 이렇게 if문 밖으로 나와있으면 root가 null이어도 실행되는거 아님?;;;
}    

public Node deleteMin(Node n) {
	if (n.getLeft() == null) { // n의 왼쪽자식이 null이라면
    	return n.getRight(); // n의 오른쪽 자식 리턴
    }
    n.setLeft(deleteMin(n.getLeft())); // n의 왼쪽자식이 null이 아니라면 n의 왼쪽자식으로 재귀호출
    return n;
}

5.1.6 삭제 연산

임의의 키를 가진 노드를 삭제하는 연산

public void delete(Key k) {
	root = delete(root, k);
}

public Node delete(Node n, Key k) {
	if (n == null) {
    	return null;
    }
    int t = n.getKey().compareTo(k);
    if (t > 0) { // 왼쪽 자식으로 이동
    	n.setLeft(delete(n.getLeft(), k));
    } else if (t < 0) { // 오른쪽 자식으로 이동
    	n.setRight(n.getRight(), k));
    } else { // 삭제할 노드 발견
    	if (n.getRight() == null) { // case 0, 1
        	return n.getLeft();
        }
        if (n.getLeft() == null) { // case 1
        	return n.getRight();
        }
        Node target = n; // case 2
        n = min(target.getRight()); // 삭제할 노드 자리로 옮겨올 노드 찾아서 n이 가리키게 함
        n.setRight(deleteMin(target.getRight()));
        n.setLeft(target.getLeft());
    }
    return n;
}

<느낀점>

이진 탐색 트리를 통해 데이터를 효율적으로 저장하고 탐색하는 방법을 배웠다. 중위 순회를 통해 정렬된 데이터를 쉽게 얻을 수 있다는 점이 인상 깊었고, 트리의 균형이 성능에 중요한 영향을 미친다는 것도 느꼈다. 기본 개념이지만 더 복잡한 트리 구조의 기초가 된다는 점에서 중요한 자료구조라고 생각한다.

<오늘의 목표>

[자바와 함께하는 자료구조의 이해] 교재 5.4단원, 5.5단원 공부 및 내용 정리

관련 활용 문제 풀기

<활동 내역>

5.4 레드 블랙 트리

레드 블랙 트리(Red-Black Tree)란 노드에 색을 부여하여 트리의 균형을 유지하며, 탐색, 삽입, 삭제 연산의 수행 시간이 각각 0을 넘지 않는 매유 효율적인 자료구조이다.

여기서 노드란 네트워크 상에서의 장치나 어느 지점을 의미한다.

일반적으로 레드 블랙 트리는 삽입이나 삭제를 수행할 때 트리의 균형을 유지하기 위해 상당히 많은 경우의 수를 고려하며 프로그램이 복잡해지고 그 길이도 증가한다는 단점이 있는데, 이의 1/5에 해당하는 프로그램만 작성해도 되는 좌편향 레드 블랙 트리(LLRB)를 사용하면 더 높은 효율을 띌 수 있게 된다.

LLRB(좌편향 레드 블랙 트리)는 루트와 null의 경우 블랙으로 표시하며 루트로부터 각 null까지 2개의 연속된 레드 link는 없다.

또한, 루트로부터 각 null까지의 경로에 있는 블랙 link의 수는 모두 같고 레드 link는 이름과 같이 좌측으로 기울어져 있다.

LLRB 트리는 레드 블랙 트리의 일종으로, 2-3 트리를 이진 트리로 표현한 구조이다.

여기서 2-3 트리는 모든 자식 노드가 두 개의 자식과 하나의 데이터 요소 또는 세 개의 자식과 두 개의 데이터 요소를 가지는 것이다.

위 그림은 좌편향 레드 블랙 트리의 예시이다. LLRB의 4가지 규칙에 의해 트리가 형성되어 있다. 레드 link는 전부 좌측으로 기울어져 있고, 연속되어 있지 않으며, 각 null까지의 경로에 있는 블랙 link의 수는 3번으로 같다.

레드 블랙 트리에서의 탐색은 이진 탐색 트리의 탐색과 같다. 탐색하고자 하는 것인 k일 때, 루트의 id와 k를 비교하는 것으로 탐색을 시작한다. k<id일 경우 루트의 왼쪽 서브트리에서 k를 찾는 것이고 그 반대는 오른쪽에서 서브트리에서 k를 찾으며, id와 k가 같으면 노드를 찾은 것이므로 노드의 value를 반환한다. 여기서 각각의 서브트리에서 k를 탐색하는 것이 루트에서의 탐색과 동일하다.

다음은 LLRB 트리의 삽입과 삭제 연산을 구현하는데 필요한 세 가지 기본 연산이다.

레드 블랙 트리에서의 삽입은 삽입하려는 키를 트리에서 탐색하여 노드의 자식이 null이 되는 곳에 새로운 노드를 생성하여 null의 부모와 연결하는 것으로 시작한다. 이때 새로운 노드는 레드로 만드는데, 새 노드를 블랙으로 만들면 LLRB의 네 가지 규칙 중 블랙 link 수 규칙을 위배하게 되기 때문이다.

레드 블랙 트리에서 최솟값을 찾는 것은 이진 탐색 트리의 최솟값 찾기와 같다. 루트로부터 계속해서 왼쪽 자식을 따라 내려가며 null을 만났을 때, null의 부모가 가진 키가 최솟값이다. 만약 최솟값을 가진 노드가 블랙이면, 블랙 노드를 삭제하게 됨에 따라 동일 블랙 link 수 규칙에 위배된다. 따라서 루트로부터 삭제하는 노드 방향으로 레드 link를 옮기어 궁극적으로 삭제되는 노드를 레드로 만든 후에 삭제하면 된다.

5.5 B-트리

B-트리는 다수의 키를 가진 노드로 구성되어 다방향 탐색(Multiway Search)이 가능한 균형 트리이다. 이는 대용량의 데이터를 위해 고안되어 주로 데이터베이스의 기본 자료구조로써 활용된다.

차수(Order)가 M인 B-트리의 모든 이파리는 동일한 깊이를 갖는다. 또한, 루트가 아닌 각 노드의 자식 수는 [M/2]이상, M이하이며 루트의 자식 수는 2 이상이다.

B-트리에서의 탐색은 방문한 각 노드에서는 탐색하고자 하는 키와 노드의 키들을 비교하여, 적절한 서브트리를 탐색한다. 단, B-트리의 노드는 일반적으로 수백 개가 넘는 키를 가지므로 각 노드에서는 이진 탐색을 수행한다.

B-트리에서의 삽입은 탐색과 동일한 과정을 거쳐 새로운 키가 저장되어야 할 이파리를 찾는다. 이때 이파리에 새 키를 수용할 공간이 있다면, 노드의 키들이 정렬 상태를 유지하도록 새 키를 삽입한다. 하지만 이파리가 이미 M-1개의 키를 가지고 있다면, 이 M-1개의 키들과 새로운 키 중에서 중간값이 되는 키를 부모로 올려 보내고, 남은 M-1개의 키들을 반씩 나누어 각각 별도의 노드에 저장한다. 이러한 과정을 분리 연산이라고 한다.

B-트리에서의 삭제는 항상 이파리에서 이루어진다. B-트리에서의 삭제는 2-3트리와 같이 이동연산과 통합 연산을 사용한다.

이파리에서 키가 삭제된 후에 키의 수가 [M/2]-1보다 작으면, 자식 수가 [M/2]보다 작으므로 B-트리 조건을 위반한다.

이 경우 underflow가 발생했다고 한다.

이때, 이동 연산은 underflow가 발생한 노드의 좌우의 형제들 중에서 도움을 줄 수 있는 노드로부터 1개의 키를 부모 노드를 통해 이동시킨다.

키가 삭제된 후 underflow가 발생한 노드 x에 대하여 이동 연산이 불가능한 경우가 발생한다.

이때 노드 x와 그의 형제를 1개의 노드로 통합하고 노드 x와 그의 형제의 분기점 역할을 하던 부모 노드에 있는 키를 통합된 노드로 끌어내리는 연산을 수행하는데, 이를 통합 연산이라고 한다.

B-트리를 조금 더 확장해서 알아보자면, B*-트리와 B⁺-트리가 있다.

B*-트리는 B-트리로서 루트를 제외한 다른 노드의 자식 수가 2/3M~M이어야 한다.

즉, 각 노드에 적어도 2/3 이상이 키들로 채워져 있어야 한다. 이는 B-트리보다 노드의 공간을 효율적으로 활용하는 자료구조이다.

B ⁺-트리는 실세계에서 가장 널리 활용되는 B-트리로서, 오히려 이를 B-트리라고 부르기도 한다.

키들만을 가지고 B-트리를 만들고, 이파리에 키와 관련된 정보를 저장한다.

Q. 5.46 초기에 empty인 LLRB트리에 45, 35, 65, 70, 25, 80, 15, 40, 90, 75, 50, 60을 차례로 삽입하였다. 만들어진 LLRB 트리의 루트에 있는 키는?

처음에 일단 트리가 비어있으므로 45를 블랙 link로 추가한다. 그 밑에 35를 45보다 작으므로 왼쪽에 레드로 추가한다. 다음으로 65를 45보다 크므로 오른쪽에 레드로 추가하는데, 그러면 양쪽 모두가 레드가 되므로 flipColors를 사용하여 색을 바꿔준다. link는 무조건 블랙이어야하므로 link의 색을 블랙으로 바꾸어준다. 다음으로 70을 65보다 크므로 65의 오른쪽 아래에 레드로 추가한다. 하지만, 레드는 LLRB의 4가지 규칙 중 레드가 좌측에 위치해야한다는 규칙에 따라 왼쪽으로 옮겨주고, 그러면 70이 65보다 숫자가 커지므로 둘의 위치를 바꾼다. 그 다음 45 아래의 두 노드가 레드이므로 flipColors를 한다. 이와 같이 4가지 규칙에 따라 트리에 숫자를 차례로 삽입하며 위치를 바꾸고 색을 바꾸는 과정을 반복하면 결국 50이 맨 위로 가게 되어 LLRB 트리의 루트에 있는 키는 50이 된다.

Q. 5.47 문제 5.46에서 만들어진 LLRB의 높이는?

50 -> 70 -> 80 -> 90 과 같은 식으로 경로가 만들어지고 다른 경로 또한 이와 같이 만들어지므로 LLRB의 높이는 3이다.

Q. 5.56 다음 중 차수가 4이고 높이가 3인 B-트리에 최대로 저장할 수 있는 키의 수는?

위 문제에서 높이를 h라 하고 차수를 m이라 할 때, 최대 키 수=(m(의 h제곱)−1) 이므로 4의 3제곱 -1은 63이다.

<회고>

레드 블랙 트리랑 LLRB 트리의 개념에 대해 잘 이해했다고 생각했는데, 막상 문제를 풀어보자니 처음부터 감이 잡히지 않아 막막했다. 예제에 대한 더 확실한 공부와 관련 문제 풀이를 하면서 감을 익히는 것이 중요한 것 같다.

2-3 트리에 대한 선행이 안 되어 있어서인지 LLRB와 B-트리를 공부하는 과정에서 2-3트리에 관한 내용이 나올 때마다 어려움이 있었다. 그래서 2-3 트리가 왜 굳이 2와 3으로 이루어진 이름을 가진 트리인지부터 공부를 하며 LLRB와 B-트리에 대한 이해도를 높이고자 하였다. 정말 2개의 노드 또는 3개의 노드를 가져서 2-3 트리라는 사실을 알자, 직관적인 이름 덕에 이해가 더 쉬웠던 것 같다.

B-트리는 LLRB에 비해 상대적으로 개념부터 이해하기가 더 어려웠다.

더 높은 이해와 활용을 위해서는 B-트리에 관한 추가적인 영상 학습 등이 필요할 것 같다.

<목표>

https://quswjddms.tistory.com/15

<결과>

https://quswjddms.tistory.com/16

<목표>

https://quswjddms.tistory.com/13

<결과>

https://quswjddms.tistory.com/14

<오늘의 목표>

[자바와 함께하는 자료구조의 이해] 교재 대단원 3단원 공부 및 내용 정리

관련 교재 문제 풀기

<활동 내역>

스택이란, 한쪽 끝에서만 항목을 삭제하거나 새로운 항목을 저장하는 자료구조이다.

스택에서 새로운 항목을 저장하는 연산을 push라고 하고, 삭제하는 연산을 pop이라고 한다.

큐는 삽입과 삭제가 양 끝에서 각각 수행되는 자료구조이다. 일상생활에서의 번호표를 이용한 줄서기가 대표적인 큐의 예시이다.

즉, 큐 자료구조는 선입 선출(First-In First-Out, FIFO) 원칙에 따라 삽입 삭제를 수행한다.

데크는 양쪽 끝에서 삽입과 삭제를 허용하는 자료구조이다. 이는 스택과 큐를 혼합한 자료구조라고 할 수 있다.

따라서, 데크는 스택과 큐를 동시에 구현하는 데 사용된다.

<회고>

스택과 큐, 데크 모두 개념은 간단한데 활용하는 것들이 많고 복잡하다.

여러 예제를 푸는 것이 매우 중요할 듯 하다.

<목표>

https://quswjddms.tistory.com/11

<결과>

https://quswjddms.tistory.com/12