자료구조와 스택

자료 구조

• 순차 리스트
  • 배열 / 행렬 / 레코드
  • 스택 / 큐 / 데크
• 연결 리스트
  • 단일 연결리스트
  • 원형 연결리스트
  • 이중 연결리스트
• 트리
  • 일반 트리
  • 이진 트리

순차 리스트

• 각 자료가 메모리 중에서 서로 이웃해 있는 구조
• 선형 구조라고도 함
• 메모리에 연속되어 저장
• 배열 / 행렬 / 레코드 / 스택 / 큐 / 데크

배열

• 크기와 데이터형이 같으며 동일한 이름을 같은 원소들의 연속적 저장 영역
• 배열의 원소는 메모리 내에서 연속적으로 순서대로 저장
• 각 배열의 원소는 첨자([0]~[n])로 구별

레코드

• 서로 다른 데이터 형태와 크기로 구성되어 있는 이질적 데이터 구조
• 예 : 다양한 사람들에 대한 자료들인 이름, 주민등록번호, 주소 등 서로 관계있는 여러 자료를 한 개의 조로 묶어서 구성
• 배열과 차이점 : 배열은 데이터 원소의 크기와 형태가 동일하지만 레코드는 데이터 원소의 크기, 형태 서로 다르다.

스택(Stack)

• 선형 리스트 구조의 특별한 형태
• 리스트 내의 데이터 삽입과 삭제가 Top라고 하는 한쪽 끝에서만 일어나는 데이터 구조
• 데이터 구조에서는 기억 장치에 데이터를 일시적으로 쌓아 두었다가 필요할 때 꺼내서 사용할 수 있는 메모리나 레지스터의 일부를 항당하여 사용하는 임시적인 기억을 말함
• Push / Pop으로 가장 마지막에 삽입한 데이터를 제일 먼저 삭제
• LIFO(Last In First Out)리스트라고도 불린다.

• TOP(Top Point)
  • 스택에 대한 삽입과 삭제가 이루어지는 위치
  • 가장 최근에 입력된 항목의 위치를 가리키는 포인터
  • 출력 우선 순위가 가장 높은 원소를 가리키는 포인터
  • 초기에 TOP는 0부터 시작하지만 배열로 스택 구현 시 배열 첨자가 0부터 시작하므로 TOP은 -1로 초기화 한다.
• BOTTOM
  • TOP의 반대쪽으로 노드의 입출력 불가
• PUSH
  • 스택에 새로운 노드 입력(삽입)
  • TOP = TOP + 1
• POP
  • 스택에서 노드 삭제
  • TOP = TOP - 1
• 오버플로우(Overflow)
  • 스택이 가득차 있을 때(TOP == n(n은 스택의 크기)) 스택에 더 이상 삽입할 수 없는 경우
  • 스택에 삽입 전 오버플로우가 발생하는지 확인해야 함.(isFull())
• 언더플로우(Underflow)
  • 스택이 비어있을 때(TOP == 0) 노드가 없어서 노드를 더 이상 삭제할 수 없는 경우
  • 스택 삭제 전 언더플로우가 발생하는지 확인해야 함.(isEmpty())
• 스택에서 사용되는 연산
  • 삽입 (push)
    • if TOP == n then overflow exist
    • TOP = TOP + 1
    • stack[TOP] <- insert_data
  • 삭제 (pop)
    • if TOP = 0 then underflow exist
    • deleted_data <- stack[TOP]
    • TOP = TOP -1

스택 예제

1. 배열을 사용한 스택 구현
   • index가 0부터 시작하므로 초기 상태를 -1로 설정
   • top = -1 이면 empty, pop하면 underflow 발생

• MyStack.java (메소드 구현)

package AlgoPractice.stack;

public class MyStack {
    // 멤버 변수
    private int stackSize; // 스택 크기
    private int top; // 스택 포인터
    private char[] stackArr; // 스택(배열 변수만 선언하고 할당, 크기 설정 안됨)

    // 생성자
    public MyStack(int stackSize) {
        top = -1;
        this.stackSize = stackSize; // 스택 크기만 설정
        stackArr = new char[this.stackSize]; // 스택 배열 생성
    }

    // 메서드
    // 스택이 비었는지 isEmpty() 결과는 true(비었을 때) / false(가득  찼을 때)로 반환
    public boolean isEmpty() {
        if(top == -1) return true;
        else return false;
    }
    // 스택이 차있는지 isFull() 결과는 true(가득 찼을 때) / false(가득 아닐 때)로 반환
    public boolean isFull() {
        if(top == stackSize-1) return true;
        else return false;
    }
    // 스택에 데이터를 삽입하는 push()
    // 1. 삽입 전 overflow 발생하는지 확인
    // 2. overflow가 아니면 삽입 push 시작
    // 3. top 위치 확인 후 top+1(++top)에 삽입
    // 삽입을 위한 매개변수를 받고 반환 값은 없다.
    public void push(char input) {
        if(isFull()) {
            System.out.println("Stack is Full\nOverFlow!!!\npush Failed");
        }
        else {
            // push 할 때 먼저 1증가
            stackArr[++top] = input;
        }
    }
    // 스택에 데이터를 삭제하는 pop()
    // 1. 데이터 삭제 전 underflow 검사
    // 2. underflow가 아니면 데이터 삭제
    // 3. top 위치 확인 후 top위치 삭제 후 top-1
    // 삭제한 문자를 반환
    public char pop() {
        if(isEmpty()) {
            System.out.println("Stack is Empty\nUnderFlow!!!\npop Failed");
            return 'E'; // 형식적인 반환 값
        }
        else {
            return stackArr[top--];
        }
    }
    // 스택의 최상위 데이터 출력하는 peek()
    // 1. 스택에 값이 있는지 확인 isEmpty()
    // 2. 최상위 데이터(top위치) 리턴
    public char peek() {
        if(isEmpty()) {
            System.out.println("Stack is Empty \n ");
            return 'E'; // 형식적인 반환 값
        }
        else {
            return stackArr[top];
        }
    }
    //  스택을 비우는 clear()
    // 1. top = -1로
    // 2. stack 값 모두 삭제
    public void clear() {
        top = -1;
    }
    // 스택의 전체 데이터를 출력하는 showStack()
    // 출룍먼 하고 반환 값은 없다
    // 1. 출력 전 비었는지 확인(반환 값 없음)
    // 2. 스택 모든 요소 값 출력
    public void showStack() {
        if(isEmpty()) {
            System.out.println("Stack is Empty");
        }
        else {
            System.out.print("Stack Items : ");
            for(int i = 0; i <= top; i++) {
                System.out.print(i + ":" + stackArr[i] + " ");
            }
            System.out.println("\ntop : " + top);
            System.out.println("top index is " + stackArr[top]);
        }
    }
}

• MyStackMain (Main 메소드)

package AlgoPractice.stack;

public class MyStackMain {
    public static void main(String[] args) {
        int stackSize = 5; // 스택 크기
        MyStack myStack = new MyStack(stackSize);

        System.out.print("스택 초기 : ");
        myStack.showStack();

        System.out.println();
        System.out.println("pop 수행");
        myStack.pop();

        System.out.println();
        System.out.println("a, b, c push 수행");
        myStack.push('a');
        myStack.push('b');
        myStack.push('c');
        myStack.showStack();

        System.out.println();
        System.out.println("최상위 값 : " + myStack.peek());

        System.out.println();
        System.out.println("d, e, push 수행");
        myStack.push('d');
        myStack.push('e');
        myStack.showStack();

        System.out.println();
        System.out.println("f push 수행");
        myStack.push('f');

        System.out.println();
        System.out.println("pop 두 번 수행");
        System.out.println("pop 한 값 : " + myStack.pop());
        System.out.println("pop 한 값 : " + myStack.pop());
        myStack.showStack();

        System.out.println();
        System.out.println("clear 수행");
        myStack.clear();
        myStack.showStack();

        System.out.println();
        System.out.println("h push 수행");
        myStack.push('h');
        myStack.showStack();
    }
}

2. 자바에서 제공하는 스택 클래스를 사용한 스택 구현

• UtilStack.java(util에서 제공하는 메인 메소드로 구현)

package AlgoPractice.stack;

import java.util.Stack;

public class UtilStack {
    public static void main(String[] args) {
        Stack<String> stk = new Stack<String>();

        stk.push("메시");
        stk.push("호날두");
        stk.push("고병채");

        for(int i =0; i<stk.size(); i++) {
            System.out.println(i + " : " + stk.get(i)); //get은 값만 출력(pop이 아님)
        }
        System.out.println();
        System.out.println("스택 크기 : " + stk.size());
        System.out.println("최상위 값 : " + stk.peek());

        System.out.println();
        System.out.println("호날두가 들어 있나? : " + stk.contains("호날두"));
        System.out.println("호날두가 들어 있나? : " + stk.contains("음바페"));

        System.out.println();
        System.out.println("pop 수행1 : " + stk.pop());
        System.out.println("pop 수행2 : " + stk.pop());
        for(int i =0; i<stk.size(); i++) {
            System.out.println(i + " : " + stk.get(i)); //get은 값만 출력(pop이 아님)
        }

        System.out.println();
        System.out.println("clear 수행");
        stk.clear();
        System.out.println("empty ? -> " + stk.empty());

        try {
            System.out.println();
            System.out.println("pop 수행3 : " + stk.pop());
        } catch (Exception e) {
            System.out.println();
            System.out.println(e.toString());
        }

    }
}