Chapter 04. 스택과 큐

 

chapter 04 - 1 스택

데이터를 일시적으로 저장하기 위한 자료구조
후입선출 구조 (LIFO (Last In First Out) : 가장 나중에 넣은 데이터를 가장 먼저 꺼냄)

 

- 스택 관련 키워드(용어)

  - push : 스택에 데이터를 넣는 작업

  - pop : 스택에서 데이터를 꺼내는 작업

  - top : push / pop 하는 위치

  - bottom : 스택의 가장 아랫부분

- Java에서 메서드 호출하고 실행 시 프로그램 내부에서는 스택 사용

 

- 스택 만들기

  - 스택 본체의 배열, 스택 포인터, 스택 용량 등의 변수 필요

 

- 연습문제

   - 클래스 IntStack의 모든 메서드를 사용하는 프로그램

        (ⓒⓞⓓⓔ) ex01.java

   - 임의의 객체형 데이터 쌓을 수 있는 제네릭 스택 클래스 Gstack<E> 작성

        (ⓒⓞⓓⓔ) ex02.java

   - 하나의 배열을 공유하여 2개의 스택을 구현하는 int형 데이터용 스택 클래스 생성

        (ⓒⓞⓓⓔ) ex03.java

 

 

 

chapter 04 - 2 큐

데이터를 일시적으로 쌓아두기 위한 자료구조
선입선출 구조 (FIFO (First In First Out) : 가장 먼저 넣은 데이터를 가장 먼저 꺼냄)

 

- 큐 관련 키워드 (용어)

  - enqueue : 큐에 데이터 넣는 작업 / 시간복잡도 : O(1)

  - dequeue : 큐에서 데이터를 꺼내는 작업 / 시간복잡도 : O(n)

  - front : 데이터를 꺼내는 쪽

  - rear : 데이터를 넣는 쪽

 

- 배열로 큐 만들기

  - enqueue : 처리의 복잡도는 O(1)

  - dequeue : que[0] 값 꺼낸 후 요소를 모두 맨 앞으로 옮김 / 처리 복잡도는 O(n)

 

- 링 버퍼로 큐 만들기

  - 링 버퍼 (ring buffer) : 배열의 처음과 끝이 연결되어 있는 자료 구조

    - 변수 front, rear가 중요 / 각 처음 요소의 인덱스와 끝 요소의 하나 뒤의 인덱스 의미

  - enqueue / dequeue 복잡도 모두 O(1)

    - front, rear의 값 업데이트 하며 작업 수행하므로 자리 이동 문제 해결 가능

 

- 큐 클래스 IntQueue

  - 검색 메서드 indexOf에서 스캔 시작은 큐의 첫 요소 front 변수 위치임

  - dump 메서드는 큐에 있는 모든 데이터를 front -> rear 순으로 출력하는 메서드

 

- 연습문제

   - 큐를 구현하는 프로그램, 실습 4-3 메서드에 대응하는 메서드 모두 생성하는 프로그램

     (ⓒⓞⓓⓔ) IntAryQueue.java

   - 클래스 IntQueue에 임의의 데이터를 검색하는 메서드 추가(큐 안에서 몇번째인지)

     (ⓒⓞⓓⓔ) IntQueue.java

   - 임의의 객체형 데이터 쌓아 놓을 수 있는 제네릭 큐 클래스 Gqueue<E> 작성

     (ⓒⓞⓓⓔ) Gqueue.java

   - 양방향 대기열을 구현하는 클래스 IntDeque 만들기

     (ⓒⓞⓓⓔ) 

 

 

 

** 참고내용 **

  링 버퍼의 활용

  - 링 버퍼는 오래된 데이터를 버리는 용도로 활용함

  - 정수 입력은 무한히 할 수 있지만, 가장 최근 데이터로만 저장되어 남아 있음.