[자주 쓰는 알고리즘 문법 정리] Stack, Queue, Collection Binary Search

안녕하세요!

퇴근하고 돌아온 jju_developer입니다.

 

오늘은 자바에서 자주 사용하는 코딩 기초 알고리즘 문법을 정리해보려고 합니다.

 

예시로는 'jju 서점'이라는 웹 페이지를 가정하여 설명드리겠습니다.

 

이번시간에는 Stack, Queue, Collection Binary Search에 대해 정리하려고 합니다~!

 

그럼 시작하겠습니다~

---

1. Stack (스택)

정의

스택은 후입선출(LIFO, Last In First Out) 방식의 자료구조입니다. 즉, 가장 나중에 들어간 데이터가 가장 먼저 나옵니다. 책을 쌓는 것과 같은 방식으로 생각할 수 있습니다.

 

알고리즘이 필요한 이유 및 성능 개선점

스택은 웹 페이지의 '뒤로 가기' 기능이나 수식 계산기 등에서 많이 사용됩니다.

성능 면에서는 삽입과 삭제가 O(1)로 매우 빠르기 때문에 효율적입니다.

 

시간복잡도 보러가기 클릭!!!

[1년차 개발자 입장] 알고리즘을 알아야 하는 이유?

 

사용 방법

다음은 jju 서점 웹 페이지에서 사용자가 열람한 책 페이지를 스택에 저장하고, 뒤로 가기 기능을 구현한 예제입니다.

import java.util.Stack;

public class JjuBookStore {
    private Stack<String> pageHistory = new Stack<>();

    // 책 페이지를 열람할 때
    public void visitPage(String page) {
        pageHistory.push(page);  // 페이지를 스택에 추가합니다.
        System.out.println("페이지 방문: " + page);
    }

    // '뒤로 가기' 기능 구현
    public void goBack() {
        if (!pageHistory.isEmpty()) {
            String lastPage = pageHistory.pop();  // 마지막 페이지를 스택에서 제거하고 반환합니다.
            System.out.println("이전 페이지로 이동: " + lastPage);
        } else {
            System.out.println("이전 페이지가 없습니다.");
        }
    }

    public static void main(String[] args) {
        JjuBookStore store = new JjuBookStore();
        store.visitPage("책 1");
        store.visitPage("책 2");
        store.visitPage("책 3");
        store.goBack();  // '책 3' 페이지로 이동
        store.goBack();  // '책 2' 페이지로 이동
        store.goBack();  // '책 1' 페이지로 이동
        store.goBack();  // 이전 페이지가 없습니다.
    }
}

 

간단한 예시로 스택을 이해하기 쉽게 만들어 보았습니다.

 

상황에 따라서 후입선출이 필요한 부분의 웹 개발에서 쓰일 수 있겠죠?

 

💻 후입선출(LIFO)이 필요한 웹 개발 상황은?

* 브라우저 히스토리 관리: 사용자가 페이지를 방문할 때마다 URL을 스택에 추가하고,

뒤로 가기 버튼을 눌렀을 때 스택에서 가장 마지막 URL을 꺼내는 방식으로 구현합니다.

*  페이지 네비게이션 상태 관리: SPA(Single Page Application)에서 
페이지 이동 시 이전 상태를 저장하고 복원할 때 스택을 사용하여 이전 상태로 돌아갈 수 있습니다.

*  호출 스택(Call Stack) 관리: 자바스크립트와 같은 언어에서 함수 호출과 리턴을 관리할 때 스택을 사용합니다. 
재귀 호출 시 특히 중요!

*  Undo/Redo 기능: 텍스트 에디터나 그래픽 소프트웨어에서 사용자 작업을 되돌리거나 
다시 실행할 때 스택을 사용하여 작업 내역을 관리합니다.

 

---

2. Queue (큐)

정의

큐는 선입선출(FIFO, First In First Out) 방식의 자료구조입니다.

즉, 먼저 들어간 데이터가 먼저 나옵니다.

줄 서기와 같은 방식으로 생각할 수 있습니다.

 

알고리즘이 필요한 이유 및 성능 개선점

큐는 웹 페이지의 대기열 처리, 프린터 작업 큐 등에서 많이 사용됩니다.

삽입과 삭제가 O(1) 로 빠르기 때문에 효율적으로 작업을 처리할 수 있습니다.

 

사용 방법

다음은 jju 서점 웹 페이지에서 주문 처리를 위해 큐를 사용하는 예제입니다.

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

public class JjuBookStore {
    private Queue<String> orderQueue = new LinkedList<>();

    // 주문 추가
    public void addOrder(String order) {
        orderQueue.add(order);  // 주문을 큐에 추가합니다.
        System.out.println("주문 추가: " + order);
    }

    // 주문 처리
    public void processOrder() {
        if (!orderQueue.isEmpty()) {
            String nextOrder = orderQueue.poll();  // 큐에서 가장 먼저 추가된 주문을 제거하고 반환합니다.
            System.out.println("주문 처리: " + nextOrder);
        } else {
            System.out.println("처리할 주문이 없습니다.");
        }
    }

    public static void main(String[] args) {
        JjuBookStore store = new JjuBookStore();
        store.addOrder("주문 1");
        store.addOrder("주문 2");
        store.addOrder("주문 3");
        store.processOrder();  // '주문 1' 처리
        store.processOrder();  // '주문 2' 처리
        store.processOrder();  // '주문 3' 처리
        store.processOrder();  // 처리할 주문이 없습니다.
    }
}

간단한 예시로 큐를 이해하기 쉽게 만들어 보았습니다.

 

주문은 순차적으로 받고 주문 큐에 추가,

가장 빨리 주문한 사람것을 순차적으로 처리.

 

💻 선입선출(FIFO)이 필요한 웹 개발 상황은?

작업 대기열(Task Queue): 서버에서 요청을 처리하는 순서를 관리할 때 먼저 들어온 요청을 공정하게 처리할때 필요.

메시지 큐: 마이크로서비스 아키텍처에서 서비스 간 메시지를 전달할 때 메시지 큐를 사용하여 순차적으로 메시지를 처리합니다. >> 저는 갤럭시 워치와 서버간의 통신을 할때에 서버에서 단체로 문자 보낼시에 메시지큐를 사용합니다.

프린터 작업 큐: 사용자들이 여러 프린터 작업을 요청할 때, 큐를 사용하여 먼저 요청된 작업을 먼저 처리합니다.

채팅 시스템: 실시간 채팅 시스템에서 메시지를 순서대로 전달하고 처리하기 위해 큐를 사용합니다.

예약 시스템: 티켓 예약 시스템에서 요청이 들어온 순서대로 예약을 처리하기 위해 큐를 사용합니다.

 

 

---

3. Collection Binary Search (이진 탐색)

정의

이진 탐색은 정렬된 배열에서 중간 값을 기준으로

탐색 범위를 반으로 줄여가며 원하는 값을 찾는 알고리즘입니다.

O(log n)의 시간 복잡도로 매우 효율적입니다.

 

알고리즘이 필요한 이유 및 성능 개선점

이진 탐색은 데이터베이스 쿼리, 로그 파일 분석 등에서 매우 유용합니다.

특히 정렬된 데이터를 빠르게 검색할 수 있는 장점이 있습니다.

 

사용 방법

다음은 jju 서점 웹 페이지에서 책 제목을 이진 탐색으로 찾는 예제입니다.

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class JjuBookStore {

    // 책 목록에서 이진 탐색
    public void searchBook(String title) {
        List<String> bookTitles = Arrays.asList("jju_Java", "jju_Spring", "jju_Programming", "Data Structures", "Jju 서점");
        Collections.sort(bookTitles);  // 책 제목을 정렬합니다.
        int index = Collections.binarySearch(bookTitles, title);  // 이진 탐색을 수행합니다.

        if (index >= 0) {
            System.out.println("책을 찾았습니다: " + bookTitles.get(index));
        } else {
            System.out.println("책을 찾지 못했습니다.");
        }
    }

    public static void main(String[] args) {
        JjuBookStore store = new JjuBookStore();
        store.searchBook("jju_Spring");  // 'jju_Spring' 책을 찾음
        store.searchBook("JavaScript");  // 'JavaScript' 책을 찾지 못함
    }
}

 

여기서 핵심은 책 제목을 정렬을 한뒤에 이진 탐색으로

반을 나누어서 책제목에 맞는 것을 탐색하는 것 입니다.

 

💻 이진 탐색이 필요한 웹 개발 상황은?

제품 검색 및 필터링: 전자 상거래 웹사이트에서 제품을 검색할 때, 

정렬된 제품 목록에서 이진 탐색을 사용하여 빠르게 제품을 찾을 수 있습니다.

자동 완성 기능: 검색 바에 사용자가 입력하는 동안, 

정렬된 키워드 목록에서 이진 탐색을 사용하여 추천 검색어를 빠르게 찾습니다.

데이터베이스 인덱싱: 대규모 데이터베이스에서 특정 레코드를 빠르게 찾기 위해 

이진 탐색 트리를 기반으로 인덱스를 생성합니다.

로그 분석: 서버 로그 파일에서 특정 시간대의 로그를 빠르게 찾기 위해 

정렬된 로그 데이터에서 이진 탐색을 사용합니다.

회원 관리 시스템: 정렬된 회원 목록에서 특정 회원 정보를 

빠르게 검색하고 업데이트하는 데 이진 탐색을 사용합니다.

개발을 하다보면 참 다양한 상황이 있습니다~

 

효율적으로 작업을 처리하고 성능을 최적화 하려면,

각 상황에 맞는 적절한 알고리즘을 선택하여 웹 개발을 진행하는 것이 중요할 것 같네요!

 

 

앞으로 더 공부해서 많은 알고리즘과 자료구조에 대해

포스팅할 예정이니 많은 관심 부탁드립니다~

 

그럼 오늘도 수고하셨습니다~~~🎵🎁