5/26(목) 자료구조 - 1️⃣ Stack, Queue 스택과 큐

 

 

 

Stack

 

 

Queue

 

 

❑ 자료구조란?

 

여러 자료(데이터)를 다루는 구조

자료(데이터)란?

휴대폰 번호, 방문기록, 고객명단, 대기열 등 모든 것이 자료이다.

자료를 정리하는 방식은 자료의 형태마다 달라야한다.

만약에 규칙없이 저장하거나 하나의 구조만으로 저장하면 자료마다 활용하는 것이 불편하다.

자료를 효율적으로 정리하면 저장하고 활용하는데 있어서 훨씬 유리하게 된다.

 

자료를 효율적으로 정리하는 방법은 여러가지가 있다.

 

자료를 다루는 구조 그 자체를 뜻하고 구현하는 방식에는 제약이 없음

 

주로쓰는 자료구조 : stack, queue, graph, tree

 

❑ Stack?

 

FILO(First In Last Out) / LIFO(Last In First Out)

먼저 들어간놈이 나중에 나오고 나중에 들어간 놈이 먼저 나오는 자료 구조

출입구가 하나고 끝이 막힌 구조를 생각하면 된다.

 

 

자바에서 Stack을 배열로 구현해보기

Doit! 자료구조와 함께 배우는 알고리즘 입문(자바편)에서 참고해서 작성하였다.

 

package stack;

public class IntStack {
    private int[] stk;  // 스택용 배열
    private int capacity;   // 스택 용량
    private  int ptr;   // 스택 포인터

    // 실행시 예외: 스택이 비어있음
    public class EmptyIntStackException extends RuntimeException {
        public EmptyIntStackException(){};
    }

    // 실행시 예외: 스택이 가득 참
    public class OverflowIntStackException extends RuntimeException {
        public OverflowIntStackException(){};
    }

    // 생성자
    public IntStack(int maxlen) {
        ptr = 0;
        capacity = maxlen;
        try {
            stk = new int[capacity];
        } catch (OutOfMemoryError e) {
            capacity = 0;
        }
    }

    // 스택에 x push
    public int push(int x) throws OverflowIntStackException {
        if(ptr >= capacity) {
            throw new OverflowIntStackException();
        }
        return stk[ptr++] = x;
    }

    // 스택에서 데이터를 pop
    public int pop() throws EmptyIntStackException {
        if(ptr <= 0) {
            throw new EmptyIntStackException();
        }
        return stk[--ptr];
    }

    // 스택에서 데이터를 peek
    public int peek() throws EmptyIntStackException {
        if(ptr <= 0) {
            throw new EmptyIntStackException();
        }
        return stk[ptr - 1];
    }

    // 스택을 비움
    public void clear() {
        ptr = 0;
    }

    // 스택에서 x를 찾아 인덱스(없으면 -1)을 반환
    public int indexOf(int x) {
        for(int i = ptr - 1; i >= 0; i--) {
            if (stk[i] == x)
                return i;
        }
        return -1;
    }

    // 스택의 용량 반환
    public int getCapacity() {
        return capacity;
    }

    // 스택에 쌓여 있는 데이터 개수를 반환
    public int size() {
        return ptr;
    }

    // 스택이 비어있는가?
    public boolean isEmpty() {
        return ptr <= 0;
//        return ptr == 0; 으로도 가능
    }

    // 스택이 가득 찼는가?
    public boolean isFull() {
        return ptr >= capacity;
    }

    // 스택 안의 모든 데이터를 bottom-> top 순서로 출력
    public void dump() {
        if(ptr <= 0) {
            System.out.println("Stack is Empty!");
        }
        else {
            for(int i = 0; i < ptr; i++)
                System.out.print(stk[i]+ " ");
            System.out.println();
        }
    }
}

 

 

테스트할 코드도 구현해보았다.

package stack;

import java.util.Scanner;

public class IntStackTester {
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        IntStack s = new IntStack(64);

        while(true) {
            System.out.println();
            System.out.printf("present data count: %d / %d\n", s.size(), s.getCapacity());
            System.out.print("(1)push (2)pop (3)peek (4)dump (5)clear (6)getCapacity (7)indexOf (8)isFull (0)exit  : ");

            int menu = stdIn.nextInt();

            if(menu == 0) break;    //exit

            int x;
            switch(menu) {
                case 1 :    // push
                    System.out.print("데이터: ");
                    x = stdIn.nextInt();
                    try {
                        s.push(x);
                    }catch (IntStack.OverflowIntStackException e) {
                        System.out.println("Stack is full!!");
                    }
                    break;
                case 2:     // pop
                    try {
                        x = s.pop();
                        System.out.println("pop data is " + x + ".");
                    } catch (IntStack.EmptyIntStackException e) {
                        System.out.println("Stack is Empty!!");
                    }
                    break;
                case 3:     // peek
                    try {
                        x = s.peek();
                        System.out.println("peek data is " + x + ".");
                    } catch (IntStack.EmptyIntStackException e) {
                        System.out.println("Stack is Empty!!");
                    }
                    break;
                case 4:     // dump
                    s.dump();
                    break;
                case 5:     // clear
                    s.clear();
                    break;
                case 6:     // getCapacity
                    System.out.println("Capacity : " + s.getCapacity());
                    break;
                case 7:     //indexOf
                    System.out.print("input you want to find : ");
                    x = stdIn.nextInt();
                    System.out.println(x + " is in " + s.indexOf(x));
                    break;
                case 8:
                    System.out.println("Stack is Full? " + s.isFull());
                    break;
            }

        }
    }
}

 

 

자바에서는 Stack 자료구조가 클래스로 이미 지원되고 있다.

여러가지 메소드들을 이용해서 효과적으로 관리할수 있다.

• push : 데이터를 넣는다.
• pop : 데이터를 꺼낸다.
• peek : 스택의 꼭대기에 있는 요소를 반환한다.
• empty : 스택이 비었는지 확인한다.
• search : 찾고자 하는 요소가 꼭대기부터 맨 처음으로 등장하는 index를 반환한다.

 

 

 

❑ Queue?

 

FIFO / LILO

먼저 들어간 놈이 먼저 나온다

줄 서서 기다리는 것을 이미지하면 된다.

은행이나 마트에서 줄서서 기다리면 먼저 온 사람 먼저 처리해준다

인큐 : 큐안에 들어옴

디큐 : 큐안에서 나감

 

자바에서 배열로 구현한 Queue..작성중..

 

 

➤ 현실적인 예시

 

문서를 출력하면 문서가 들어간 순서대로 인쇄 된다.

컴퓨터(출력버튼)-(임시기억장치)Queue에 하나씩 들어옴 - Queue에 들어온 순서대로 문서 인쇄

인쇄할 때 CPU가 인쇄 데이터를 보내는 속도가 프린터가 인쇄하는 속도보다 빠르기 때문에 인쇄 데이터를 잠시 보관할 임시저장공간이 필요하다.

만약에 CPU가 프린터가 하나씩 인쇄 되는것을 기다렸다가 데이터를 전송하면 CPU가 그 시간동안 다른일을 처리하지 못하기 때문에 비효율적이다.

컴퓨터 장치간에 데이터를 주고받을 때 장치 사이 속도가 존재한다.

시간차이나 속도차이를 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용

-> 버퍼(Buffer) 라고 함

 

 

 

 

 

읽어주셔서 감사합니다.😍

오개념에 대한 지적은 언제나 환영입니다.