[자료 구조] 선형 구조(Linear Structure)

선형 구조(Linear Structure)

• 데이터를 저장하기 위한 기본적인 형태로 데이터가 일렬로 나열되어 있으며 순서가 있고 논리적으로 이어져 있는 구조를 의미한다.
• Ex) 큐(Queue), 스택(Stack), 덱(deque)

1. 큐(Queue)

---

• 선입선출(First-In-First-Out, FIFO)의 특성을 가진다.

동작 과정

• 데이터 삽입(Enqueue)
  - rear 부분에 데이터가 저장되며 rear은 다음 삽입할 데이터의 위치로 이동한다.
    * rear : 삽입할 데이터의 위치를 가리키는 포인터로 맨 뒤에 위치한다.
• 데이터 추출(Dequeue)
  - front 부분에서 데이터가 추출되며 front는 다음 추출한 데이터의 위치로 이동한다.
    * front : 추출될 데이터의 위치를 가리키는 포인터로 맨 앞에 위치한다.

사용 예시

• 프로세스 관리
  - 운영체제에 존재하는 프로세스 대기열에서 먼저 들어온 순서대로 CPU를 할당받기 위해 사용된다.
• 너비 우선 탐색
  - 인접 노드를 우선 방문하는 경우 사용된다.
• 캐시
  - 가장 오래된 데이터를 먼저 삭제하는 정책을 구현할 때 사용된다.

import java.util.LinkedList;
import java.util.Queue;

public class QueueEx {

    public static void main(String[] args) {

        Queue<String> queue = new LinkedList<>();

        queue.add("A");     // 큐가 다 찼을 경우 IllegalStateException 발생
        queue.offer("B");   // 큐가 다 찼을 경우 false 반환
        queue.add("C");
        queue.offer("D");

        System.out.println(queue);

        String peekElement = queue.peek();  // 맨 앞의 요소를 반환
        String pollElement = queue.poll();  // 맨 앞의 요소를 반환 후 제거

        System.out.println(queue);

        System.out.println("peek element : " + peekElement);
        System.out.println("poll element : " + pollElement);

        queue.clear();

        System.out.println(queue);

    }

}

 

2. 스택(Stack)

---

• 후입선출(Last-In-First-Out, LIFO)의 특성을 가진다.

동작 과정

• 데이터 삽입 및 추출
  - top 부분에 데이터가 삽입되고 추출된다.
    * top : 삽입 및 추출될 데이터의 위치를 가리키며 맨 위에 위치한다.

import java.util.Stack;

public class StackEx {

    public static void main(String[] args) {

        Stack<String> stack = new Stack<>();

        stack.push("A");
        stack.push("B");

        System.out.println(stack);

        String popElement = stack.pop();

        System.out.println("pop element : " + popElement);

        System.out.println(stack);

        String peekElement = stack.peek();

        System.out.println("peek element : " + peekElement);

    }

}

 

3. 덱(Deque)

---

• 양쪽 끝에서 삽입과 삭제가 가능(선입선출(FIFO) + 후입선출(LIFO))하다는 특성을 가진다.

사용 예시

• 회문 판별
  - 앞에서 읽으나 뒤에서 읽으나 동일한 문자열을 검사할 때 사용된다.
• 최댓값/최솟값 검색
  - 슬라이딩 윈도우 알고리즘을 이용할 때 사용된다.
    * 슬라이딩 윈도우 알고리즘 
      : 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘

import java.util.Deque;
import java.util.LinkedList;

public class DequeueEx {

    public static void main(String[] args) {

        Deque<String> dequeue = new LinkedList<>();

        dequeue.addFirst("a");
        dequeue.addFirst("A");
        dequeue.addLast("B");
        dequeue.addLast("b");

        System.out.println(dequeue);

        String firstElement = dequeue.getFirst();
        String lastElement = dequeue.getLast();

        System.out.println("first element : " + firstElement);
        System.out.println("last element : " + lastElement);

        String firstRemoveElement = dequeue.removeFirst();
        String lastRemoveElement = dequeue.removeLast();

        System.out.println("first remove element : " + firstRemoveElement);
        System.out.println("last remove element : " + lastRemoveElement);

        System.out.println(dequeue);

    }

}

 

 

▷ 출처

https://adjh54.tistory.com/135

https://medium.com/javarevisited/linear-data-structures-with-time-complexity-every-programmer-must-know-c58a446e06ac

https://medium.com/depayse/kotlin-data-structure-collections-4-stack-queue-deque-4c383efebee9