자료구조, 알고리즘/기본다지기
[자료구조] 스택(Stack)
민쓰
2018. 8. 27. 20:22
스택(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 } }