[자료구조] 스택(Stack)

자료구조 공부

오늘은 스택에 대해서 공부하겠습니다.

 

스택은 자료구조중 하나로 후입선출 특징인 자료 구조 입니다. LIFO(Last-IN First-Out)이라고 합니다.

즉, 먼저들어온 데이터가 가장 나중에 나가는 형태의 자료 구조입니다.

통상 push()를 이용하여 데이터를 삽입하고 pop()을 이용하여 데이터를 뽑습니다.

 

1, 5 , 6 , 7의 데이터를 스택의 삽입한다면

 

7

6

5

1

위와 같은 형태로 삽입됩니다. 여기서 pop을 이용하여 데이터를 뽑아내면

6

5

1

위와 같이 자료구조의 담긴 데이터가 바뀌고 가장 나중에 삽입한 7은 뽑아지겟죠?

 

스택은 위와 같이 자료를 저장하는 자료구조입니다.

자바로 구현해보겠습니다.

 

우선 금융공기업 전산직 기출문제를 이용하여 구현해보겠습니다.

 

문제)

 

스택(Stack) 알고리즘을 Java 또는 C++의 클래스로 구현하시오(15점)
(단, 변수명 및 상수명은 다음과 같이 사용할 것
- 클래스명 :Stack
- 스택 저장소명 : Item(Integer의 배열)
- 스택 저장소의 최대 크기 : MAX
- 스택 포인터 : top

 

즉흥적으로 구현한 스택 (학부시절 배운내용을 기반으로)

아래는 내가 처음 작성한 스택

package datastructure;
 
import java.util.Arrays;
 
public class Stack {
    private int top=0;
    final int MAX = 10;
    private int[] item = new int[MAX];
    
    public void push(int a)
    {
        if((top-1) == MAX)
        {
            System.out.println("스택이 가득 찾습니다");
        }else
        {
            
            item[top] = a;
            top++;
            System.out.println("입력되었습니다");
        }
    }
    public int pop()
    {
        return item[top--];
    }
    
    @Override
    public String toString() {
        return "Stack [top=" + top + ", MAX=" + MAX + ", item=" + Arrays.toString(item) + "]";
    }
    public static void main(String[] args) {
        Stack stack = new Stack();
        stack.push(1);
        stack.push(6);
        stack.push(7);
        System.out.println(stack.pop());
        stack.push(3);
        System.out.println(stack.pop());
        System.out.println(stack);
    }
}
 

 

위에는 처음 즉흥적으로 짜본 스택코드

부실하기 짝이없다... 우선 필드부터 잘못지정되었고 생성자로 초기화해줘야되는데 그게 없다...

다시 만들어봐야겠다.

 

아래는 다시 수정한 배열 스택

생성자 초기화부분을 수정하고 더이상 빼낼 자료가 없을때 콘솔로 출력해준다.

try-catch 문을 써서 바운드익셉션을 추가해도 될것 같다.

 

package datastructure;
 
import java.util.Arrays;
 
public class Stack {
    final int MAX = 10;
    private int top;    
    private int[] item;
    
    public Stack()
    {
        this.top = 0;
        this.item = new int[MAX];
    }
    
    public void push(int input)
    {
        if(top >= MAX)
        {
            System.out.println("스택이 가득 찾습니다");
        }else
        {            
            item[top] = input;
            top++;
            System.out.println(input + " 입력되었습니다");
        }
    }
    public int pop()
    {
        if(top <=0 )
        {
            System.out.println("데이터가 없습니다");
            return 0;
        }else
        {
            
            
            return item[--top];
        }
        
    }
    
 
    public static void main(String[] args) {
        Stack stack = new Stack();
        stack.push(1);
        stack.push(6);
        stack.push(7);
        System.out.println(stack.pop());
        stack.push(3);
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        stack.push(32);
        System.out.println(stack.pop());
        
    }
}