for Programming study

스택(Stack)

22 Jun 2020 | DataStructure soongsil SSU

이 포스팅은 숭실대학교 컴퓨터학부 신용태 교수님의 자료구조 수업을 기반으로 작성되었습니다.

스택(Stack)이란

LIFO 구조 즉 후입선출 구조를 갖는 자료구조인데, 한쪽 끝으로만 데이터의 추가 삭제가 이루어지는 구조입니다.
책이 쌓여 있는 모습을 생각하시면 이해가 빠르실겁니다.
대표적인 연산으로는 스택에서 top 데이터를 추출하는 Pop, 반대로 데이터를 삽입하는 Push연산이 있습니다.
간단한 그림으로 표현하면 다음과 같습니다. stack

JAVA CODE로 구현

자바 API에 구현된 스택 기능이 있으나, 이해를 위해 직접 스택 코드를 구현하였습다.
코드는 크게 5가지 부분으로 작성되어 있고, 어떤 타입의 데이터라도 사용할 수 있게 Object 타입을 사용했습니다.

  • StackADT() : StackADT 클래스의 생성자, 스택 배열을 사이즈를 지정하여 초기화 해준다.
  • pop() : 스택의 가장 TOP 데이터, 즉 가장 마지막에 추가된 데이터를 꺼낸 후 스택 배열에서는 삭제한다.
  • push() : 스택 배열에 가장 마지막에 아이템을 데이터를 추가해준다.
  • peek() : 스택 배열에서 아이템을 삭제하지 않고도 TOP 데이터를 확인할 수 있게 해준다.
  • isEmpty() : 스택 배열이 비어있으면 true를 리턴해준다.
public class StackADT {
    private Object[] data; //스택 배열
    private int manyItems; //아이템의 개수
    public StackADT(int size){ //size 크기의 스택 배열 생성
        manyItems =0; // 스택에 저장된 아이템 개수 0에서 시작
        data = new Object[size];
    }
    public Object pop(){
        Object toPop; //pop한 데이터를 리턴하기 위해 선언
        if(isEmpty()) { //비어있는 스택인지 확인
            return "Empty";
        }
        toPop = data[--manyItems]; //top 데이터를 toPop에 저장
        data[manyItems] = null; //저장한 데이터를 삭제
        return toPop;
    }
    public void push(Object item){
        if(manyItems == data.length){ //스택 배열이 꽉 찼는지 확인
            System.out.println("Stack is Full");
            return;
        }
        data[manyItems] = item;
        manyItems++;
    }
    public boolean isEmpty(){
        return manyItems==0;
    }
    public Object peek(){
        if(isEmpty()){ //비어있는 스택인지 확인
            return "empty";
        }
        return data[manyItems-1]; //배열의 인덱스는 0부터 시작하므로 item개수 -1을 해준다.
    }

    public static void main(String[] args){
        StackADT stack = new StackADT(3);
        System.out.println("Pushing elements in Stack");
        for(int i = 1; i<=3; i++) { //반복문을 통해 push
            System.out.println("Push :"+ i);
            stack.push(i );
        }
        System.out.println("Is stack empty? : "+stack.isEmpty());
        System.out.println("Peek : "+ stack.peek());

        System.out.println("Pop all element from Stack");
        for(int i=0; i<4; i++) //반복문을 통해 pop
            System.out.println("Pop : " + stack.pop());

        System.out.println("Is stack empty? : "+stack.isEmpty());
    }
}

실행 결과

stack 코드를 실행해보면 반복문을 통해 1, 2, 3을 차례대로 스택에 push하고 스택 배열이 비어있는지 확인합니다.
또 peek()를 통해 스택의 top 데이터를 확인하고. 스택에 데이터를 차례대로 pop 했을때 3, 2, 1 순서로 데이터가 출력되는것을 확인할 수 있습니다.

Read more

큐(Queue)

22 Jun 2020 | DataStructure soongsil SSU

이 포스팅은 숭실대학교 컴퓨터학부 신용태 교수님의 자료구조 수업을 기반으로 작성되었습니다.

큐(Queue)란

LIFO 구조를 가지는 Stack과 다르게 Queue는 FIFO(First In, First Out)구조입니다.
즉 먼저 들어간 데이터가 먼저 나오는 식으로 동작합니다.
일반적으로 실생활속 대기줄을 생각하시면 됩니다.
Stack에서는 데이터 삽입, 삭제를 push, pop이라고 하는데
Queue는 Rear에 데이터 삽입하는것을 Enqueue, Front에서 데이터 삭제를 하는것을 Dequeue라고 합니다.
간단한 그림으로 표현하면 다음과 같습니다. queue

큐(Queue)의 종류

큐의 종류는 크게 아래의 3가지 종류입니다.

  • 선형 큐(Linear Queue) : 선형큐는 가장 일반적인 형태의 큐로 일반적인 배열 형태로 막대 모양을 하고 있다.
    크기가 제한되어 있고 빈 공간을 사용하려면 데이터의 위치를 재배치해야 하는 단점이 있다.
  • 원형 큐(Circular Queue) : 원형큐는 선형큐의 단점을 보완하고자 만들어졌는데, 만약 Rear의 위치가 배열의
    마지막에 위치하면 Rear를 배열의 가장 앞으로 옮겨줘서 원형으로 연결하여 배열 공간을 더 효율적으로 사용 할 수 있다.
  • 우선 순위 큐(Priority Queue) : 우선 순위 큐는 삽입된 각 데이터 별로 우선순위를 부여해서 우선순위가
    높은 데이터부터 큐에서 꺼내진다. 일반적으로 데이터를 삽입할 때 우선 순위에 따라 정렬하여 구현한다.

JAVA CODE로 구현

선형큐

public class Queue {
    private Object[] data;
    private int manyItems;
    private int front;
    private int rear;
    Queue(int size){
        data = new Object[size];
        this.manyItems=0;
        this.front=0;
        this.rear=-1;
    }

    public Object Dequeue() {
        Object toDequeue;
        if (isEmpty())
            return "empty";
        toDequeue = data[front];
        front++; //front를 하나 증가시켜서 dequeue한 데이터는 접근 불가
        manyItems--; //아이템 개수 감소
        return toDequeue;
    }
    public void Enqueue(Object item){
        if(manyItems == data.length) //큐 배열이 꽉찼을 때
            System.out.println("Queue is Full");
        else{
            this.rear++; //rear를 하나 증가시켜서 데이터 저장
            data[rear] = item;
            manyItems++;
        }
    }
    public Object peek(){ //배열에서 아이템을 삭제하지 않고 확인
        if(isEmpty()){ //비어있는 스택인지 확인
            return "empty";
        }
        return data[front];
    }
    public boolean isEmpty(){
        return manyItems==0;
    }

    public static void main(String[] args){
        Queue q = new Queue(3);

        System.out.println("Enqueueing elements in Queue");
        for(int i = 1; i<=5; i++) { //반복문을 통해 push
            System.out.println("Enqueue :"+ i);
            q.Enqueue(i);
        }
        System.out.println("Is Queue empty? : "+q.isEmpty());
        System.out.println("Peek : "+ q.peek());

        System.out.println("Dequeue all element from Queue");
        for(int i=0; i<4; i++) //반복문을 통해 pop
            System.out.println("Dequeue : " + q.Dequeue());

        for(int i = 1; i<=5; i++) { //반복문을 통해 push
            System.out.println("Enqueue :"+ i);
            q.Enqueue(i);
        }
        System.out.println("Is Queue empty? : "+q.isEmpty());
    }
}

실행 결과

queue 선형 큐 코드의 실행 결과를 보면 다음과 같은데 큐가 꽉 찰때까지 Enqueue를 하고 다시 큐가 텅 비게 될때까지 Dequeue를 수행합니다. 하지만 다시 Enqueue를 하려고 하면 ArrayIndexOutOfBoundsException이 발생하는데, 이는 배열의 범위를 벗어났다는 뜻입니다. Enqueue, Dequeue를 반복적으로 수행하는 과정에서 front와 rear가 이미 배열의 끝에 도달해 있기 때문입니다.
물론 선형큐에서도 이보다 더 효율적으로 코드를 작성할 수 있지만, 선형 큐의 단점을 강조하기 위해 위와 같이 코드를 작성하였습니다.
이러한 선형 큐의 단점을 보완하기 위해 사용하는 원형 큐는 어떻게 동작하게 되는지 코드를 통해 보여 드리겠습니다.

원형 큐

Read more

이제 블로그 시작

05 Jan 2020 | start github soongsil SSU

2019년도 2학기 오픈소스 기반 기초 설계때 얻은 지식을 바탕으로 GitHub블로그를 시작하게 됐다.
한학기 동안 공부한게 있어서 어렵진 않았지만 아직 미숙한것 같다.
블로그는 앞으로 공부할 내용이나 공부했던 것들을 복기 하는데 사용될 예정이다.

Read more