Stack & Queue 구현

2023. 4. 13. 21:07·📚 Data Architect/Algorithm

💡 ArrayList로 스택 구현

public class Implementation_Stack {
    private ArrayList<Integer> listStack = new ArrayList<Integer>();

    public void push(Integer data) {
        listStack.add(data);
    }

    public Integer pop() {
        if (listStack.size() == 0) {
            return null;
        } else {
            return listStack.remove(listStack.size()-1);
        }
    }

    public int size() {
        return listStack.size();
    }

    public Integer peek() {
        if (listStack.size() == 0) {
            return null;
        } else {
            return listStack.get(listStack.size()-1);
        }
    }

    public String show() {
        return listStack.toString();
    }

    public void clear() {
        listStack.clear();
    }
}

스택을 배열로 구현

배열은 순서가 있고 첫 부분을 제거하거나 추가하려면 요소들을 하나씩 뒤로 옮겨야 하며 시간복잡도는 O(n) 임
스택과 큐의 과정이 비효율적이기 때문에 스택과 큐에서는 기본적인 배열을 사용하지 않음

그래서 첫 부분을 제거하거나 추가하는 과정의 시간복잡도가 상수인 연결 리스트를 스택 & 큐에 적용하는게 좋음


배열로 스택 구현

  • addLast, removeLast -> O(1)의 시간복잡도
  • addFirst, removeFirst -> 배열의 원소들은 메모리 상에서 순차적으로 저장되기 때문에 맨 앞에서 삽입/삭제 연산이 일어나면 뒤로 한칸씩 미루거나 앞으로 한칸씩 당겨야 하므로 O(n)의 시간복잡도
  • Last In First Out (LIFO, 후입선출, 나중에 들어온 원소가 제일 먼저 나간다.)
  • top에서만 삽입/삭제가 일어나며, 배열로 구현하면 O(1)의 시간복잡도 (addLast, addFirst)

💡 Queue - ArrayList로 구현

public class Implementation_Queue {
    private ArrayList<Integer> listQueue = new ArrayList<>();

    public void add(Integer data) {
        listQueue.add(data);
    }

    public Integer poll() {
        if (listQueue.size() == 0) {
            return null;
        } else {
            return listQueue.remove(0);
        }
    }

    public int size() {
        return listQueue.size();
    }

    public Integer peek() {
        if (listQueue.size() == 0) {
            return null;
        } else {
            return listQueue.get(0);
        }
    }

    public String show() {
        return listQueue.toString();
    }

    public void clear() {
        listQueue.clear();
    }
}

배열로 큐 구현

  • addLast, removeLast -> O(1)의 시간복잡도
  • addFirst, removeFirst -> O(n)의 시간복잡도
  • First In First Out (FIFO, 선입선출, 먼저 들어온 원소가 먼저 나간다.)
  • 삽입은 rear에서 삭제는 front에서 일어나므로 삽입은 O(1), 삭제는 O(n)의 시간복잡도
  • front에서 배열 원소를 삭제할 때도 상수 시간을 보장하려면? 원형 배열
    (head와 tail의 위치가 고정적이지 않고, 배열의 시작과 끝이 연결되어 있는 구조)

스택 & 큐 를 배열로 구현했을 때

배열은 순서가 있고 첫 부분을 제거하거나 추가하려면 요소들을 하나씩 뒤로 옮겨야 하며 시간복잡도는 O(n) 임
스택과 큐의 과정이 비효율적이기 때문에 스택과 큐에서는 기본적인 배열을 사용하지 않음

그래서 첫 부분을 제거하거나 추가하는 과정의 시간복잡도가 상수인 연결 리스트를 스택 & 큐에 적용하는게 좋음

저작자표시 (새창열림)

'📚 Data Architect > Algorithm' 카테고리의 다른 글

Quick Sort  (0) 2023.04.14
Insertion Sort  (0) 2023.04.14
Selection Sort  (0) 2023.04.14
Bubble Sort  (0) 2023.04.13
DFS & BFS 구현  (0) 2023.04.13
'📚 Data Architect/Algorithm' 카테고리의 다른 글
  • Insertion Sort
  • Selection Sort
  • Bubble Sort
  • DFS & BFS 구현
신건우
신건우
조용한 개발자
  • 신건우
    우주먼지
    신건우
  • 전체
    오늘
    어제
    • 분류 전체보기 (422)
      • 📘 Frontend (71)
        • Markup (1)
        • Style Sheet (2)
        • Dart (8)
        • Javascript (12)
        • TypeScript (1)
        • Vue (36)
        • React (2)
        • Flutter (9)
      • 📘 Backend (143)
        • Java (34)
        • Concurrency (19)
        • Reflection (1)
        • Kotlin (29)
        • Python (1)
        • Spring (42)
        • Spring Cloud (5)
        • Message Broker (5)
        • Streaming (2)
        • 기능 개발 (5)
      • 💻 Server (6)
        • Linux (6)
      • ❌ Error Handling (11)
      • 📦 Database (62)
        • SQL (31)
        • NoSQL (2)
        • JPQL (9)
        • QueryDSL (12)
        • Basic (4)
        • Firebase (4)
      • ⚙️ Ops (57)
        • CS (6)
        • AWS (9)
        • Docker (8)
        • Kubernetes (13)
        • MSA (1)
        • CI & CD (20)
      • 📚 Data Architect (48)
        • Data Structure (10)
        • Algorithm (8)
        • Programmers (17)
        • BaekJoon (5)
        • CodeUp (4)
        • Design Pattern (4)
        • AI (0)
      • ⚒️ Management & Tool (8)
        • Git (7)
        • IntelliJ (1)
      • 📄 Document (10)
        • Project 설계 (6)
        • Server Migration (3)
      • 📄 책읽기 (2)
        • 시작하세요! 도커 & 쿠버네티스 (2)
      • 🎮 Game (4)
        • Stardew Vally (1)
        • Path of Exile (3)
  • 블로그 메뉴

    • 링크

      • Github
    • 공지사항

    • 인기 글

    • 태그

      Lock #Thread #Concurrency
      React #Markdown
      GStreamer #Pipeline
    • 최근 댓글

    • 최근 글

    • hELLO· Designed By정상우.v4.10.0
    신건우
    Stack & Queue 구현
    상단으로

    티스토리툴바