[자료구조] 스택(Stack)

스택(Stack)의 개념

한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조 (선형 자료 구조)

가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO; Last In First Out) 방식으로 자료를 처리

스택(Stack)의 에러

• 스택 오버플로우 : 스택의 모든 기억장소가 꽉 채워져 있는 상태이므로 더 이상 자료를 삽입할 수 없을 때 발생

• 스택 언더플로우 : 스택에 제거할 자료가 없을 때 발생

스택(Stack)의 연산

• create(size) : 스택의 크기를 지정하고 생성한다.

• push(item) : item을 스택에 삽입한다.

• pop() : 스택에 가장 위에 있는 항목을 제거한다.

• top() : 스택의 가장 위에 있는 항목을 반환한다.

• size() : 스택에 있는 item의 개수를 반환한다.

스택(Stack)의 예제

상태의 의존관계가 생길 때 A라는 일을 마치기 위해서 B라는 일을 먼저 끝내야 할 때 사용 

= 스케줄링(Scheduling)

• 재귀 알고리즘

• DFS(깊이 우선 탐색)

• 올바른 괄호 문자열 판단

스택(Stack)의 구현

class Stack{
	int[] data = new int[100];
	int len = 0;
	int capacity = 0; // 스택의 크기
	
	void create(int m){
		capacity = m;
	}
	
	void push(int item){
		if(len >= capacity){
			System.out.println("Stack Overflow!");
		}
		else{
			data[len++] = item;
		}
	}
	
	void pop(){
		if(len <= 0){
			System.out.println("Stack Underflow!");
		}
		else{
			data[len-1] = 0;
			len--;
		}
	}
	
	int top(){ 
		// 스택의 가장 위에 있는 값을 반환
		// 단, 스택에 아무것도 없다면 -1을 반환
		if(len <= 0){
			return -1;
		}
		else{
			return data[len-1];
		}
	}
	
	int size(){
		return len;
	}
}
	
public class DataStructureStack {
	public static void main(String[] args) {
		Stack s1 = new Stack();
		s1.create(2);
		
		s1.push(1);
		s1.push(2);
		s1.push(3); //overflow
		s1.push(4); //overflow

		System.out.println(s1.top()); //2
		
		s1.pop(); 
		System.out.println(s1.top()); //1
		
		s1.pop();
		s1.pop();
		s1.pop(); // underflow
		
		System.out.println(s1.size()); // 0
	}
}