[자료구조] Stack과 Queue

Stack과 Queue

Stack

스택(Stack)은 기본적인 자료구조로 쌓아올린다는 개념으로 시작하며 접근방법은 언제나 목록의 끝에서만 일어난다.

위 그림처럼 스택은 데이터를 아래서부터 쌓아올리고 데이터들을 다시 불러올때는 가장 최근의 데이터가 호출된다.
이를 선입후출(LIFO - Last in First Out)이라고 한다. 해당 자료구조를 구현하기위해 정의해야할 메소드를 아래에 적어보겠다.

 

push(data): 데이터를 저장할 때, 호출되는 메소드
pop(): 가장 위에있는 데이터를 반환하고 그 값을 삭제하는 메소드
getTop(): 가장 위에있는 데이터를 반환하는 메소드
isEmpty(): stack이 비어있는지를 확인하는 메소드
isFull(): stack이 꽉차있는지를 확인하는 메소드
printStack(): stack의 요소들을 확인할 수있도록 출력하는 메소드

class Stack
{
    private Object[] list; //요소들을 담을 저장소
    private int top; // 제일 상위에 존재하는 요소를 가리키는 pointer변수

    // 생성자
    public Stack(int size)
    {
        list = new Object[size];
        top = -1;
    }

    public boolean isEmpty() {return top == -1;}
    public boolean isFull() {return top == list.length;}

    // 현재 top에 위치한 요소를 반환한다.
    public Object getTop() 
    {
        if(this.isEmpty()) {return 'N';}
        else {return list[top];}
    }

    // 데이터를 받아오고 top의 위치를 +1한다.
    public void push(Object data) 
    {
        if(this.isFull()) {return;}
        else {list[++top] = data;}
    }

    // top에 위치한 데이터를 반환하고 top의 위치를 -1한다.
    public Object pop() 
    {    
        if(this.isEmpty()) {return null;}
        else {return list[top--];}
    }

    // Stack을 출력하는 메소드
    public void printStack()
    {
        if(this.isEmpty()) {System.out.println("[ ]");}
        else
        {
            System.out.print("[ ");
            for(int i=0; i<top; i++)
                {System.out.print(list[i] + " ");}
            System.out.println(list[top]+"* ]"); // top은 알아볼수 있도록 "*"표시를 해주었다.
        }
    }

}

사실 java의 template을 공부하지 못해서 꼼수를 사용해서 모든 객체들의 상위 클래스인 Object를 이용하여 구현하였다. 단순 int나 String같은 데이터만 사용한다면 자료형을 바꾸어 주면 된다.

Queue

큐(Queue)는 Stack과 마찬가지로 기본적인 자료구조다. 먼저 삽입된 데이터가 먼저 나오는 선입선출(FIFO - First In First Out)의 구조를 가지고 있다.

위의 그림처럼 위치를 가리키는 포인터가 rear(뒤)와 front(앞이 존재한다.) Stack과 같이 Queue에서도 사용할 메소드를 아래에 작성해보겠다.

enQueue(data): 데이터를 넣기위해 호출되는 메소드
deQueue(): front에 위치한 데이터를 반환하고 그 요소를 삭제하는 메소드
isFull(): stack이 꽉차있는지를 확인하는 메소드
printStack(): stack의 요소들을 확인할 수있도록 출력하는 메소드

class Queue
{
    Object[] list; //요소들을 담을 저장소
    int front, rear; //요소들에 접근하기 위한 pointer 변수

    // 생성자
    public Queue(int size)
    {
        list = new Object[size];
        front = rear = 0;
    }

    public boolean isEmpty() {return front == rear;}
    public boolean isFull() {return rear == list.length;}

    //데이터를 넣기위한 메소드
    public void enQueue(Object data)
    {
        if(this.isFull()) {return;}
        else {list[rear++] = data;} //값을 추가할때는 rear가 +1이 된다.
    }

    //데이터를 반환하는 메소드
    public Object deQueue()
    {
        if(this.isEmpty()) {return 0;}
        else {return list[front++];} //값을 반환할때는 front가 +1이된다.
    }

    // Queue를 출력하는 메소드
    public void printQueue()
    {
        if(this.isEmpty()) {System.out.println("[ ]");}
        else
        {
            System.out.print("[ *");
            for(int i=front; i<rear; i++)
                {System.out.print(list[i]+" ");}
            System.out.println("]");
        }
    }
}

Stack과 같이 Object 객체를 이용해서 구현하였다.

원형큐

위의 Queue에서는 문제점이 존재한다. 사용자가 Queue의 크기를 5로 지정하여서 사용하다가 요소들을 모두 deQueue()하여 front와 near의 값이 같아졌을경우 더이상 해당 Queue는 사용할 수 없게 된다. 이를 방지하기 위해 원형큐(CirculaQueue)가 정의되었다.

원형 큐를 사용하기 위해서는 약간의 논리와 Flag변수 하나만 있으면 간단하게 구현 할 수 있다.
비어있는지(isempty)와 꽉차있는지(isFull)을 flag변수를 통해서 적절히 구현하면 된다. 바로 코드를 통해 살펴보겠다.

class CircularQueue
{
    Object[] list;
    int front, rear, flag; //flag변수가 선언되어있다.
    int size;

    public CircularQueue(int size)
    {
        list = new Object[size];
        front = 0; rear = 0;
        flag = 0;
        this.size = size;
    }
    //비어있을때: fornt와 near가 같고 flag가 0일때
    //꽉차있을때: front와 near가 같고 flag가 1일때
    public boolean isEmpty() {return front==rear && flag == 0;}
    public boolean isFull() {return front==rear && flag == 1;}

    public void enQueue(Object data)
    {
        if(this.isFull()) {return;}
        else
        {
            //값을 추가할때는 rear가 +1이 되고 Queue 사이즈 만큼 나눈 나머지를 값을 가지도록 한다.
            list[rear] = data;
            rear = (rear+1)%size; 
            flag = 1; //값이 추가됐을때는 flag를 1로 변경한다.
        }
    }
    public Object deQueue()
    {
        Object item;
        if(this.isEmpty()) {return -1;}
        else
        {
            //값을 반환할때는 front가 +1이 되고 Queue 사이즈 만큼 나눈 나머지를 값을 가지도록 한다.
            item = list[front];
            list[front] = null;
            front = (front+1)%size;
            flag = 0; //값이 반환됐을때는 flag를 0으로 변경한다.
            return item;
        }
    }

    public void printQueue()
    {
        if(this.isEmpty()) {System.out.println("[ ]"); return;}
        else
        {
            System.out.print("[ ");
            for(int i=0; i<size; i++)
            {
                if(list[i]==null) {continue;}
                if(i == front) {System.out.print("*"+list[i]+" "); continue;}
                else {System.out.print(list[i] + " ");}
            }
            System.out.println("]");
        }
    }
}

예를들어 사이즈가 5이고 현재 큐가 [F1,2,3,4,5R] 이라면 deQueue통해 1이 빠져나가면서 front = (0+1)/5 = 1이 되고 여기서 6을 enQueue하면 rear는 (4+1)/5=0이 된다. 나머지연산(%)과 flag를 통해 Queue가 꽉차있는지 비어있는지를 확인 할 수 있다.

정리

정리하자면 Stack은 넣은 순서의 역순으로 요소를 뽑아와야할때 사용하고(연산의 후입표기식, 미로 탈출 경로 알고리즘, B-Tree 구현 등등) Queue는 넣은 순서대로 요소를 뽑아와야할때 사용(스케줄러, Graph의 넓이 우선탐색(BFS))한다. 그러나 java나 C/C++ 모두 기본 라이브러리로 stack Queue를 사용할 수 있어서 저렇게 무식하게 정의해서 사용하진 않는다. 다만 원리를 알고있으면 사용하기 쉽다는 점에서 이렇게 글을 남긴다.

 

위의 전체적인 코드는 아래 GitHub에서 확인할 수 있다.
https://github.com/JoSangYeon/Algorithm/tree/master/Stack%26Queue

참조

• https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D (스택)
• https://ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) (큐)
• https://ko.wikipedia.org/wiki/%EC%9B%90%ED%98%95_%EB%B2%84%ED%8D%BC (원형큐)