티스토리 뷰

Study/자료구조

01 스택 (Stack) 자료 구조

Lkt_Programmer 2017. 9. 28. 20:47
반응형

스택 (Stack)


스택(Stack)은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO- Last In First Out)으로 되어있습니다. 자료를 넣는 것을 PUSH라고 하고 넣어둔 자료를 꺼내는 것을 POP이라고 합니다.

 

스택 입/출력 방식

 

실제로 스택이 어떤 식으로 자료가 입/출력 되는지 살펴 보겠습니다. 상자안에 책을 쌓는다고 생각을 하면 됩니다. 즉 가장 먼저 넣은 책은 가장 나중에 꺼낼 수 있으며, 가장 최근에 넣은 책을 가장 먼저 뺄수 있습니다.

 

가장 먼저 5를 PUSH 합니다. 스택 자료 구조에 가장 아래에 위치하게 됩니다.

 

차례대로 PUSH 4, PUSH 3을 한 결과입니다. 

 

POP 2회를 실시하게 되면 출력 결과는 3,4가 됩니다. 즉 3은 가장 나중에 입력 되었지만 가장 먼저 출력이 됩니다.

 

소스 코드 (Source Code)

 

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
public class Stack {
    
    int maxsize = 0;
    int top = 0;
    int[] stack;
    
    public Stack(int maxsize)    //생성자에서 스택 사이즈 지정
    {
        this.maxsize=maxsize;
        stack = new int[maxsize];
    }
    
    public void Push(int number)    //push 데이터 삽입, maxsize보다 작을 경우에만
    {
        if(top < maxsize)
        {
            stack[top] = number;
            top++;
        }
        else
        {
            System.out.println("오버플로우");
        }
    }
    
    public Object Pop()            //top이 가르키는 위치의 원소를 반환
    {
        if(top > 0 )
        {
            return stack[--top];
        }
        else
        {
            System.out.println("스택에 데이터가 존재하지 않습니다.");
            return null;
        }
    }
}

 

실제로 구현한 스택 자료 구조 입니다. 생성자를 통해서 Stack의 크기를 지정해주고 데이터의 삽입 index를 가르

키는 top은 최초 0으로 초기화합니다. Push의 경우는 maxsize보다 작을 경우에만 해당 top의 위치에 원소를 넣어주고 top의 크기를 증가 시킵니다. Pop은 top의 index가 0보다 큰 경우에만 top의 1 감소 시킨 위치의 원소를 반환해줍니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Main {
    public static void main(String[] args)
    {
        Stack stack = new Stack(5);
        stack.Push(5);
        stack.Push(4);
        stack.Push(3);
        stack.Push(2);
        stack.Push(1);
        System.out.println(stack.Pop());
        System.out.println(stack.Pop());
        System.out.println(stack.Pop());    
        System.out.println(stack.Pop());
        System.out.println(stack.Pop());    
    }
}

 

실제 스택을 사용하는 메인 영역입니다.

 

 

반응형