ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [Data Structure] 자료구조 - 스택 (Stack)
    CSE/Data Structure 2015. 6. 12. 16:12

    스택(Stack)




    개념: 스택은 같은 구조와 크기의 자료를 top 이라고 정한 한 곳에만 쌓을 수 있고, 

    top으로만 접근하도록 제한하여 만든 자료구조




    스택에서 top을 통해 들어온 자료가 일정한 방향으로 차곡차곡 쌓입니다.


    마치 뷔페식당의 쌓인 접시나


    책상위에 차곡차곡 쌓아 둔 책


    과 같이 말이죠~



    스택에서 자료를 삭제할 때도 top을 통해서만 가능하기 떄문에 


    top이 가리키고 있는 스택의 마지막 자료만 삭제할 수 있습니다.


    따라서, 스택은 시간순서에 따라 자료가 쌓이고, 


    삭제할 때는 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 


    후입선출(LIFO: Last In First Out)의 구조를 갖습니다.



    스택의 구조






     




    위처럼 data1,2,3이 차곡차곡 쌓이고 stack에서 top의 위치는 data 3을 가리키는 겁니다!


    절대로 스택에서 data3이 먼저 제거되지 않는 한, data2와 data1을 꺼낼수 없습니다!!!




    자 그럼 소스 코드를 통해 스택에 대해 알아보도록 합시다!




    먼저 


    순차 자료구조(배열)로 구현한 스택을 살펴보겠습니다!!!



    클래스다이어그램으로 먼저 프리뷰하죠~




     


    스택은 크게 4개의 연산을 가지고 있습니다!


    Push: 스택안에 데이터를 집어 넣는 연산


    Pop: 스택안의 데이터를 끄집어 내는 연산


    Top: 스택의 상위 데이터를 반환하는 연산(Pop과는 다른 용도입니다!!!)


    Empty: 스택이 비어있는지 불리언 값 반환하는 연산





    그럼 소스코드를 보시지요~



    stack.java

     

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    package Stack;
     
    public interface Stack {
        public boolean isEmpty();
        public void push(String item);
        public String pop();
        public void delete();
        public String top();
    }
     
    cs



    ArrayStack.java


     

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
     
    package Stack;
     
    public class ArrayStack implements Stack {
        private int top;
        private int stackSize;
        private String[] itemArray;
     
        public ArrayStack(int stackSize) {
            this.top = -1;
            this.stackSize = stackSize;
            itemArray = new String[this.stackSize];
        }
     
        public boolean isEmpty() {
            return (top == -1);
        }
     
        public boolean isFull() {
            return (top == this.stackSize - 1);
        }
     
        public void push(String item) {
            if (isFull()) {
                System.out.println("Stack is Overflow!");
            } else {
                itemArray[++top] = item;
                ;
                System.out.println("Inserted Item : " + item);
            }
        }
     
        public String pop() {
            if (isEmpty()) {
                System.out.println("Stack is Underflow!");
                return null;
            } else {
                return itemArray[top--];
            }
        }
     
        public void delete() {
            if (isEmpty()) {
                System.out.println("Deleting fail! Stack is Empty!");
            } else {
                top--;
            }
        }
     
        public String top() {
            if (isEmpty()) {
                System.out.println("top fail! stack is Empty!");
                return null;
            } else {
                return itemArray[top];
            }
        }
     
        public void printStack() {
            if (isEmpty()) {
                System.out.println("Stack is empty!");
            } else {
                System.out.print("Array Stack >> ");
                for (int i = 0; i <= top; i++) {
                    System.out.print(itemArray[i] + " ");
                }
                System.out.println();
            }
        }
    }
     
    cs



    StackMain.java


     

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
     
    package Stack;
     
    public class StackMain {
        public static void main(String[] args) {
            int stackSize = 5;
            String deleteItem = null;
            ArrayStack stack = new ArrayStack(stackSize);
     
            stack.push("S");
            stack.printStack();
     
            stack.push("T");
            stack.push("A");
            stack.push("C");
            stack.push("K");
            stack.printStack();
     
            deleteItem = stack.pop();
     
            if (!deleteItem.isEmpty()) {
                System.out.println("deleted Item: " + deleteItem);
            }
     
            stack.printStack();
        }
    }
     
    cs




    결과는 아래와 같습니다!!




     





    다음은!


    연결 자료구조(배열)로 구현한 스택

    을 구현해보겠습니다!



    클래스다이어그램부터 보시자.




     




    Stack Interface는 위에서 만든 거 고대로 썼어요~



    StackNode.java


     

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
     
    package Stack;
     
    public class StackNode {
        private String data;
        private StackNode link;
     
        public StackNode() {
            this.data = "";
            this.link = null;
        }
     
        public StackNode(String data) {
            this.data = data;
            this.link = null;
        }
     
        public StackNode(String data, StackNode link) {
            this.data = data;
            this.link = link;
        }
     
        public String getData() {
            return data;
        }
     
        public void setData(String data) {
            this.data = data;
        }
     
        public StackNode getLink() {
            return link;
        }
     
        public void setLink(StackNode link) {
            this.link = link;
        }
    }
     
    cs






    LinkedStack.java


     

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
     
    package Stack;
     
    public class LinkedStack implements Stack {
        private StackNode top;
     
        public boolean isEmpty() {
            return (top == null);
        }
     
        public void push(String item) {
            StackNode newNode = new StackNode(item, top);
            top = newNode;
            System.out.println("Inserted data: " + item);
        }
     
        public String pop() {
            if (isEmpty()) {
                System.out.println("Stack is Empty!!! ");
                return null;
            } else {
                String item = top.getData();
                top = top.getLink();
                return item;
            }
        }
     
        public void delete() {
            if (isEmpty()) {
                System.out.println("Stack is Empty!!! ");
            } else {
                top = top.getLink();
            }
        }
     
        public String top() {
            if (isEmpty()) {
                System.out.println("Stack is Empty!!");
                return null;
            } else {
                return top.getData();
            }
        }
     
        public void printStack() {
            if (isEmpty()) {
                System.out.println("Stack is Empty!!");
            } else {
                StackNode tmp = top;
                System.out.println("Linked Stack >> ");
                while (tmp != null) {
                    System.out.print("  " + tmp.getData() + "   ");
                    tmp = tmp.getLink();
                }
                System.out.println();
            }
        }
     
    }
     
    cs






    StackMain.java


     

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
     
    package Stack;
     
    public class StackMain {
        public static void main(String[] args) {
            String deleteItem = null;
            LinkedStack lStack = new LinkedStack();
     
            lStack.push("I");
            lStack.push("AM");
            lStack.push("A");
            lStack.push("BOY");
     
            lStack.printStack();
     
            deleteItem = lStack.pop();
            if (!deleteItem.isEmpty()) {
                System.out.println("deleted Item : " + deleteItem);
            }
     
            lStack.printStack();
     
        }
    }
     
    cs




    결과 화면은 아래와 같습니다!!!



     




    댓글

Designed by Tistory.