백, 큐, 스택 [0/1]

개발하는부티·2022년 9월 15일

데이터구조와알고리즘 백 스택 자바 큐

데이터구조와알고리즘

목록 보기

1/3

백, 큐, 스택은 객체들의 컬렉션을 이용하는 데이터 타입이다.

컬렉션 ADT를 이해하기 위한 준비

백, 큐, 스택을 살펴보기에 앞서 먼저 각각의 API와 컬렉션 추상 데이터 타입을 이해하는데 중요한 개념인 제네릭, 오토박싱, 반복자를 살펴본다.

API

백

	public class Bag<Item> implements iterable<Item>
    Bag()               // 공백 백 생성
    void add(Item item) // 항목 추가
    boolean isEmpty()   // 백이 비어 있는가?
    int size()          // 백에 든 항목의 개수

선입선출(FIFO) 큐

	public class Queue<Item> implements iterable<Item>
    Queue()                 // 공백 큐 생성
    void enqueue(Item item) // 항목 추가
    Item dequeue()          // 최근에 추가된 항목 제거(꺼내기)
    boolean isEmpty()       // 큐가 비어 있는가?
    int size()              // 큐에 든 항목의 개수

후입선출(LIFO) 스택

	public class Stack<Item> implements iterable<Item>
    Stack()                 // 비어 있는 스택 생성
    void push(Item item)    // 항목 추가
    Item pop()              // 가장 최근에 추가된 항목 제거(꺼내기)
    boolean isEmpty()       // 스택이 비어 있는가?
    int size()              // 스택에 든 항목 개수

셋 다 대부분의 메서드가 동일하지만, 큐와 스택은 특정 항목을 삭제하는 메서드를 추가로 가지고 있다.

❗ 큐와 스택의 API를 보면 메서드들의 이름만 다를 뿐인데, 어떤 컬렉션 타입이 가지는 특징을 메서드 원형(리턴 타입, 인수 등)에 드러나게 하기는 힘들다. 때문에 자연 언어(//코멘트)로 룰을 설명한는 것이 중요하다.

제네릭

제네릭은 백, 큐, 스택 등 컬렉션 ADT에 어떤 데이터 타입이든 들어올 수 있게 해주는 자바의 핵심 메커니즘이다.

위의 API에서 <Item>의 자리에는 실제 데이터 타입이 대체되어 들어간다. 예를 들어보자.

Stack<String> myStack = new Stack<String>();
myStack.push("추가할 항목");

위 코드와 같이 Stack<Item>의 Item 자리에 Stack<String> String을 넣으면 myStack을 String의 스택으로 정의한 것이다. 때문에,

myStack.push(100); //에러!

와 같이 String이 아닌 다른 데이터 타입을 push하면 오류가 발생한다.

제네릭이 컬렉션 ADT에 중요한 이유는 스택을 만들 당시에는 클라이언트가 어떤 데이터 타입을 사용할지 모르기 때문이다. 만약 제네릭이 없었다면 String용 스택, Integer용 스택 등 일일이 스택을 만들어야 했을 것이다. 또한, 제네릭은 이해하기 쉽고 디버깅하기 쉬운 클라이언트 코드를 작성하게 해준다.

오토박싱(Autoboxing)

오토박싱이란 자바 컴파일러가 자동으로 primitive type(기본형) 데이터를 대응하는 wrapper 클래스의 객체(참조형)로 변환하는 것을 의미한다. 이 반대 변환을 언박싱이라고 한다.

제네릭 타입 파라미터로부터 생성되는 변수는 참조형 타입(Integer)으로만 생성되어야 한다. 여기서 기본 데이터 타입(int)을 사용하려 할때 문제가 발생하는데, 자바의 오토박싱 기능이 이를 해결해 준다. 예를 들어보자,

	Stack<Integer> myStack = new Stack<Integer>(); // 참조형으로 선언
    myStack.push(40); // 오토박싱 (int->Integer)
    int i = myStack.pop() // 언박싱

두 번째 줄에서 int타입인 40을 Integer타입으로 오토박싱 하여 push( ) 메서드에 전달하고 있다. 반대로 세 번째 줄에서는 pop( )에서 전달받은 Integer타입을 int타입으로 언박싱하여 i에 대입하고 있다.

컬렉션 반복자

컬렉션 반복자의 역할은 컬렉션의 각 항목들에 대해 어떤 처리를 하거나 컬렉션의 모든 항목들을 순회하는 것이다.

우리가 공항 검색대에 줄을 서고 있으면 경비는 그 줄을 돌아다니며 여권을 꺼내게 하거나 줄을 잘못 선 승객을 다른 줄로 안내한다. 여기서 줄이 컬렉션이고 줄에 서있는 우리가 항목이고 경비가 컬렉션 반복자 라고 이해하면 된다. 경비가 여권을 꺼내게 하거나 다른 줄로 안내하는 것이 바로 항목에 어떤 처리를 하는 것이다.

이런 경비의 역할을 하는 순회 개념은 현대의 프로그래밍 언어들이 최우선으로 달성하고자 하는 패러다임이다. 언어 차원에서 이러한 메커니즘을 지원하는데 반복자라고 부른다. 반복자를 사용하면 세부적인 메커니즘을 고려하지 않고도 명료하고 압축적인 코드를 작성할 수 있다.

EX)

// 아래와 같은 collection이라고 부르는 큐가 있다고 해보자.
Queue<Integer> collection = new Queue<Integer>();
// 만약 collection이 반복자를 지원한다면 아래와 같이 간단하게 목록을 출력할 수 있다.
for(Integer i: collection) { StdOut.println(i); }