Stack(스택)

1. 특성

- 선형구조(자료 간의 관계가 1대 1의 관계를 가짐)
- LIFO(Last In First Out) 구조 (후입선출)

 

 

2. 구현 in Java

: java.util에 있는 Stack<E> 클래스를 사용한다.

ex> 정수 스택 : Stack<Integer> stack = new Stack<>();

- empty() : 스택이 비어있는가

- peek() : 스택의 제일 상단에 있는 요소 반환

- pop() : 스택의 제일 상단에 있는 요소 반환 + 제거

- push(E item) : 제일 상단에 요소를 삽입

- search(Obejct o) : 제일 상단의 요소를 1로 하여 객체가 존재하는 위치의 인덱스 반환

 

 

3. Stack의 연산

배열, ArrayList 등의 자료구조와 가장 상단의 인덱스를 나타내는 top을 이용해 Stack 자료구조를 구현하고, push와 pop 연산을 나타낼 수 있다.

(1) push

public static void push(int[] stack, int x) {
	if(top+1 >= stacksize)
		System.out.println("overflow");
	else{
		stack[++top] = x;
		System.out.println("push" + " " + x);
	}
}

(2) pop

public static void pop(int[] stack) {
	if(top == -1)
		System.out.println("underflow");
	else {
		System.out.println(stack[top--]);
	}
}

 

 

4. 응용1 : 괄호 검사

(1) 괄호 종류 : 대괄호([]), 중괄호({}), 소괄호(())

(2) 조건

- 왼쪽 괄호 개수와 오른쪽 괄호 개수가 같도록

- 왼쪽 괄호가 오른쪽보다 먼저

- 괄호 사이에는 포함 관계만 존재

(3) 알고리즘

- 왼쪽 괄호 : stack에 삽입

- 오른쪽 괄호 : stack에서 pop하여 괄호의 짝이 맞는지 확인

(stack이 empty()이거나, 짝이 맞지 않는 괄호이거나, 전부 조사했는데 아직 괄호에 남은 요소가 있다면 ERROR)

 

++ 유사문제 : 프로그래머스 올바른 괄호(level2)

2020/08/03 - [Coding Test/프로그래머스] - [200803] 올바른 괄호 - 연습문제(level2)

 

 

 

4. 응용2 : Function call(함수 호출 관리)

(1) 함수 호출의 원리

- 후입선출 구조

- 호출 : 해당 함수에 필요한 지역변수, 매개변수, 복귀 주소를 Stack에 저장

- 실행 완료 : Stack의 top원소를 pop하여 얻은 복귀주소로 복귀

 

(2) 프로그램 메모리 공간

- 코드 영역 : 프로그램의 코드(명령문)

- 데이터 영역 : 전역변수, static 변수가 할당 / 프로그램 시작 시 할당되고 종료 시까지 남아있음

- 힙 영역 : 원하는 시점에 메모리 공간에 할당 및 소멸하기 위한 영역

- stack 영역 : 지역변수와 매개변수 할당 / 함수 실행 완료 시 소멸