Knowledge/자료구조

[자료구조] 스택(Stack) 정리

똑똑한망치 2023. 11. 13. 23:59
728x90
반응형

1. Stack 컬렉션

스택(Stack)의 사전적 정의는 '쌓다', '더미'로서 접시 스택처럼 접시를 쌓아놓은 것을 말한다. 즉, 상자에 물건을 쌓아 올리듯이 데이터를 쌓는 자료 구조라고 할 수 있다.

스택은 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 구조 특징이 있는데, 이러한 자료 구조를 LIFO (Last In First Out) 구조라고 한다. 많이 사용되는 Queue(큐)의 경우 먼저 추가된 데이터가 먼저 나오는 FIFO (First In First Out) 동작을 갖는 것과 비교된다. 

스택은 배열이 수직으로 쌓여있는 것과 비슷하다. 따라서 요소의 추가 및 삭제는 맨 위에서만 차례대로 가능하다. 예를 들면 웹 뒤로가기, Ctrl+z 실행취소 등이 있다.

데이터가 입력된 순서의 역순으로 처리되어야 할 때 사용한다. 예를 들어 함수 콜 스택, 수식 계산, 인터럽트 처리 등이 있다.

스택의 원리 그림, 이미지 출처 :https://www.programiz.com/dsa/stack

 

 

(1) 자바의 Stack

자바의 Stack 클래스는 Vector 클래스를 상속(extends) 받는다.

 

 

 

 

 

2. Stack 사용법

자바는 java.util.Stack 클래스를 통해 Stack(스택) 동작을 제공하고 있다.

import java.util.Stack;

 

(1) Stack 요소 넣기

  • Object push(Object item) : Stack에 객체(item)를 저장한다.
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);

System.out.println(stack);  // [1, 2, 3]

 

 

 

(2) Stack 요소 빼기

스택(Stack)은 나중에 넣은 것이 먼저 나오는 LIFO (Last In First Out) 구조이기 때문에 넣은 순서에 역순으로 꺼내진다.

  • Object pop()
System.out.println(stack.pop());  // 3

System.out.println(stack);  // [1, 2]

System.out.println(stack.pop()); // 2
System.out.println(stack.pop());  // 1

System.out.println(stack); // []

 

 

(3) Stack 가장 위에 있는 요소 확인

스택(Stack)에 들어있는 요소 중, 가장 위에 있는 값을 확인할 수 있다. 이때 값만 확인하고 데이터는 스택에서 삭제되지 않는다.

  • Object peek()
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);

System.out.println(stack.peek());  //3
//가장 최상단 값만 확인하고 삭제하지 않는다.

System.out.println(stack);  //[1, 2, 3]

 

 

 

(4) Stack 공간이 비어있는지 확인

만약 스택에 데이터가 존재하지 않는 상황에서 pop이나 peek을 하게 되면 EmptyStackException 예외가 발생한다. 따라서 항상 메서드 호출하기 전에 스택에 데이터가 존재하는지 확인해야 한다. 

  • empty() : 스택이 비어있으면 ture, 그렇지 않다면 false를 반환한다.
Stack<Integer> stack = new Stack<>();
stack.push(1);

if (!stack.isEmpty()) {  //스택이 비어있지 않다면 스택 내부 데이터 삭제
	stack.pop();
}

 

 

(5) Stack 요소 위치 확인

스택에 특정 데이터가 존재하는지 확인하기 위해 search() 메서드를 사용할 수 있다. 리스트의 indexOf() 메서드와 비슷하다. 데이터가 존재한다면 순서를 반환하고 존재하지 않다면 -1을 반환한다. 

이때, 주의할 점은 일반적인 배열 인덱스처럼 0부터 시작하여 그 위치를 반환하는 것이 아니라, pop() 메서드를 호출했을 때 몇 번째 순서로 나오는지에 대한 인덱스를 반환한다. 즉, 인덱스가 0이 아닌 1부터 시작한다. 따라서 반환값이 1이라면 가장 먼저 pop 되는 요소이다.

Stack<Integer> stack = new Stack<>();
stack.push("apple");
stack.push("banana");
stack.push("kiwi");
stack.push("tomato");

System.out.println(stack); // [apple, banana, kiwi, tomato]

System.out.println(stack.search("banan"));  // 3
System.out.println(stack.search("tomato"));  // 1 -> 가장 먼저 pop 되는 값

 

 

 

(6) Stack 사이즈 확인

Stack 클래스는 Vector 클래스를 상속하였으며, Vector 클래스는 List 인터페이스를 구현하므로 size() 메서드를 사용할 수 있다.

Stack 클래스의 경우 ArrayList 처럼 동적 공간이라 별도의 사이즈를 명시할 필요가 없다. 처음 스택이 생성될 때 10개의 데이터를 저장할 수 있는 공간이 할당된다. 그리고 push() 메소드를 통해 요소가 추가되어 10개를 넘어버리면, 현재 스택 사이즈의 2배에 해당하는 공간을 할당하고 기존 데이터를 복사한다. 

 

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);

System.out.println(stack.size());  // 3

 

 

 

 

 

 

 

 

 

3. Stack 코드 구현

  • ArrayList 를 이용하여 Stack 구현
class MyStack {
	ArrayList list;
    
    MyStack() { this.list = new ArrayList(); }   // 생성자를 이용하여 객체 생성
    
   public boolean isEmpty() {
   		if (this.list.size() == 0 ) {
    		return true;
    	} else {
    		return false;
        }
   }
   
   public void push(int data) { this.list.add(data); }
   
   public Integer pop() {
   		if (this.isEmpty()) {
        	System.out.println("Stack is empty");
            return null;
        }
        int data = (int)this.list.get(this.list.size()-1);
        this.list.remove(this.list.size()-1);
        return data;
   }
   
   public Integer peek() {
   		if (this.isEmpty()) {
        	System.out.println("Stack is empty");
            return null;
        }
        int data = (int) this.list.get(this.list.size() -1);
        return data;
   }
   
   public void printStack() { System.out.println(this.list); }
}

 

 

 

 

 

 

 

  • 배열을 이용하여 Stack 구현
class MyStack {
	int[] arr;
    int top = -1;
    
    MyStack(int size) { arr = new int[size]; }
    
    public boolean isEmpty() {
    	if (this.top == -1) {
        	return true;
        } else {
        	return false;
        }
    }
    
    public boolean isFull() {
    	if (this.top == this.arr.length -1) {
        	return true;
        } else {
        	return false;
        }
    }
    
    public void push(int data) {
    	if (this.isFull()) {
        	System.out.println("Stack is Full");
            return;
        }
        this.top += 1;
        this.arr[this.top] = data;
    }
    
    public Integer pop() {
    	if (this.isEmpty()) {
        	System.out.println("Stack is empty");
            return null;
        }
        int data = this.arr[this.top];
        this.top -= 1;
        return data;
    }
    
    public void printStack() {
    	for (int i = 0; i<this.top ; i++) {
        	System.out.print(this.arr[i] + " ");
        }
        System.out.println();
    }
}
반응형