스택 데이터 구조 및 예제

https://www.programiz.com/dsa/stack

Stack Data Structure and Implementation in Python, Java and C/C++

 

 

스택

• Last In Frist Out(LIFO) 원칙을 따르는 선형 데이터 구조
• 스택에 마지막으로 삽입된 요소가 제일 먼저 제거되는 형태

 

 

LIFO 원칙

push: 스택 위에 항목을 올리는 것

pop: 스택에서 항목을 제거하는 것

 

 

위 사진에서 3은 가장 나중에 추가되었지만 LIFO 원칙에 따라 가장 먼저 제거된다.

 

 

스택의 기본 동작

push: 스택의 맨 위에 요소를 추가

pop: 스택의 맨 위에서 요소를 제거

IsEmpty: 스택이 비어있는지 확인

IsFull: 스택이 가득 찼는지 확인

Peek: 최상위 요소를 제거하지 않고 해당 요소의 값을 가져옴

 

 

 

스택 데이터 구조의 작동

1) top은 스택의 맨 위에 있는 요소를 추적하는 포인터다. 스택 초기화 시 스택의 공백 여부를 확인하기 위해 -1로 설정한다.

2) 스택에 요소 push 시 top의 값이 증가한다. 

3) 두 번째 요소 push

4) 세 번째 요소 push

5) 요소 pop 시 top이 가리키는 요소를 반환하고 top의 값은 줄어든다.

스택 데이터 구조의 작동

 

 

스택 사용 예제

 

스택 선언하기

import java.util.Stack;

class Main {
    public static void main(String[] args) {
        // Integer형 스택 선언
        Stack<Integer> stackInt = new Stack<>();
        // String형 스택 선언
        Stack<String> stackStr = new Stack<>();
        // Boolean형 스택 선언
        Stack<Boolean> stackBool = new Stack<>();
    }
}

 

 

스택에 요소 추가 또는 제거하기

import java.util.Stack;

class Main {
    public static void main(String[] args) {
        // Integer형 스택 선언
        Stack<Integer> stack = new Stack<>();

        // push로 요소 추가
        stack.push(1);
        stack.push(2);
        stack.push(3);

        // pop으로 요소 제거
        stack.pop(); // 3 제거
        stack.pop(); // 2 제거
        stack.pop(); // 1 제거

        // add로 요소 추가
        stack.add(1);
        stack.add(2);
        stack.add(3);
        
        // [1, 2, 3] 출력
        System.out.println(stack);

        // 모든 요소 제거
        stack.clear();
    }
}

 

push() 또는 add() 메서드로 스택에 요소를 추가할 수 있다.

마지막 요소를 반환할 때는 pop() 메서드를 사용한다.

모든 요소를 제거하려면 clear() 메서드를 사용한다.

 

 

반환하지 않고 요소 출력하기

import java.util.Stack;

class Main {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

        stack.push(1);
        stack.push(2);
        stack.push(3);
	
    	// 3 출력
        System.out.println(stack.peek());
        
        // [1, 2, 3] 출력
        System.out.println(stack);
    }
}

 

peek() 메서드는 pop() 메서드와 달리 스택의 마지막 요소를 제거하지 않으면서 반환한다.

 

 

empty()

import java.util.Stack;

class Main {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

		// true 출력
        System.out.println(stack.isEmpty());
        
        stack.push(1);
        stack.push(2);
        stack.push(3);
	
    	// false 출력
        System.out.println(stack.isEmpty());
        
    }
}

 

empty() 메서드는 스택이 비어있는지에 대한 여부를 확인하고 비었다면 true, 아니면 false를 반환한다.

 

 

search()

import java.util.Stack;

class Main {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(2);
	
        System.out.println(stack.search(3)); // 2 출력
        System.out.println(stack.search(1)); // 4 출력
        System.out.println(stack.search(2)); // 1 출력
        System.out.println(stack.search(10)); // -1 출력
        
    }
}

 

search() 메서드는 인자를 스택에서 검색하여 위치를 반환한다. 

스택에서 맨 위에 있는 요소가 1이다. 즉 마지막으로 삽입된 요소가 1이고 그 전에 삽입된 요소가 2가 된다.

값이 중복된 경우 늦게 삽입된 위치를 반환한다.

스택에 없는 값일 경우 -1을 반환한다.