어떤 사람에 관한 자료들인 이름, 주민등록번호, 주소 등과 같이 서로 관계있는 여러 필드를 한 개의 조로 묶어서 구성
배열과의 차이점
배열: 데이터 원소의 크기와 데이터 형태 동일
레코드: 데이터 원소의 크기와 데이터 형태 서로 다름
스택 (Stack)
쌓아 올린 더미를 의미
선형 리스트 구조의 특별한 형태
리스트 내의 데이터 삽입과 삭제가 Top이라고 하는 한쪽 끝에서만 일어나는 데이터 구조
데이터 구조에서는 기억 장치에 데이터를 일시적으로 쌓아 두었다가 필요할 때 꺼내서 사용할 수 있는 주기억장치(메모리)나 레지스터의 일부를 할당하여 사용하는 임시적인 기억을 말함
푸시(push) / 팝(pop)의 이름으로 가장 마지막에 삽입한 데이터를 제일 먼저 삭제
LIFO(Last-In First-Out) / 후입선출방식
[출처:
n: 스택 크기
스택에 저장할 수 있는 최대 노드의 수
TOP: top point
스택에 대한 삽입과 삭제가 이루어지는 위치
가장 최근에 입력된 항목의 위치를 가리키는 포인터
출력 우선 순위가 가종 높은 원소를 가리키는 포인터
초기에 TOP은 0부터 시작
주의!!
배열로 스택 구현 시 배열 첨자가 0부터 시작하므로 TOP은 -1로 초기화
BOTTOM
TOP의 반대쪽으로 노드의 입출력 불가
PUSH: 삽입
스택에 새로운 노드 입력
TOP = TOP + 1
POP: 삭제
스택에서 노드 삭제
TOP = TOP - 1
오버플로우(Overflow)
스택이 가득 차있을 때 (TOP == n) 새로운 노드가 생기면 스택에 더 이상 삽입을 할 수 없는 경우
TOP > n
Full (스택에 삽입 전에 Overflow가 발생하는지(스택이 가득 차있는지) 확인: isfull())
언더플로우(underflow)
스택이 비어있을 때(TOP == 0) 노드의 삭제가 일어나서 더 이상 삭제를 할 수 없는 경우
TOP < 0
Empty (스택에서 노드 삭제 전에 underflow가 발생하는지(스택이 비어있는지) 확인: isEmpty())
스택에서 사용되는 연산
삽입(push)
if TOP == n then overflow exist
TOP = TOP + 1
stack[TOP] <- insert_data
삭제 (pop)
if TOP = 0 then underflow exist
deleted_data <- stack[TOP]
TOP = TOP -1
스택의 이용
서브 프로그램의 복귀 주소(return address) 보관
산술식 표현 : a + b
Java 프로그램에서 메서드 호출하고 실행할 때 스택 사용
힙 영역
JVM 시작할 때 생성
객체 / 배열 저장
사용되지 않는 객체는 Garbage Collector가 자동 제거
JVM 스택
스레드 별 생성
메서드 호출할 때마다 프레임(Frame)을 스택에 추가 (PUSH)
메서드 종료하면 프레임 제거 (POP)
프레임 내부의 로컬 변수 스택에 변수 저장
변수에 값이 저장될 때 변수 생성
연습문제 - Stack
스택(stack) 예제
배열을 사용해서 스택 구현
java.util.Stack 클래스 이용
배열을 사용해서 스택 구현
index가 0부터 시작하므로 초기 상태를 top = -1로 설정
top이 -1이면, empty, underflow
push 하려면 --top
pop은 top--
MyStack.java
package Stack;
public class MyStack {
// 멤버 변수
private int stackSize; // 스택 크기
private int top; // 스택 포인터
private char[] stackArr; // 스택(배열) : 배열 변수만 선언. 아직 할당되지 않음
// 생성자: 스택 초기화
// 배열 인덱스는 0부터 시작
// top 초기화는 -1로 설정
public MyStack(int stackSize) {
top = -1;
this.stackSize = stackSize; // 스택 크기 설정
stackArr = new char[this.stackSize]; // 스택 배열 생성
}
// 메서드
// 스택이 비었는지 확인하는 isEmpty()
// 결과 반환: true / false
public boolean isEmpty() {
return top == -1; // top이 -1이면 true, 아니면 false 반환
}
// 스택이 가득 차있는지 확인하는 isFull()
// 결과 반환: true / false
// 가득 찬 상태: top이 4인 경우, (즉, stackSize -1)
// stackSize: 5
// 스택 index: 0,1,2,3,4
public boolean isFull() {
return top == stackSize-1;
}
// 스택에 데이터 삽입하는 push()
// (1) 삽입 전에 Overflow 발생하는지 확인: isEmpty() 호출해서 결과 받아서 확인
// (2) Full이 아니면 top을 하나 증가한 위치에 데이터 삽입 ++top
// 삽입하기 위해 데이터 매개변수 받음
// 직접 스택에 삽입하고 종료 -> 반환값 없음
public void push(char item) {
if(isFull()) {
System.out.println("Stack Full. Overflow");
}
else{
// 초기값이 -1이므로, push 할 때 먼저 1 증가
stackArr[++top] = item;
}
}
// 스택에 데이터를 삭제하는 pop()
// Empty가 아니면 top 위치에 있는 데이터 삭제
// 삭제 후 top 1 감소시켜 :top--
//
public char pop() {
if(isEmpty()) {
System.out.println("Stack Empty. UnderFlow");
return 'E'; // 형식적인 return 값
}
else{
// top 위치에 있는 데이터 반환하고 top을 1 감소시킴
return stackArr[top--];
}
}
// 스택의 최상위 데이터를 출력하는 peek()
// (1) 먼저 스택이 비었는지 확인
// (2) 최상위 데이터 (top 위치에 있는 데이터) 반환
// 최상위 데이터(문자) 반환하므로 반환형 있음
public char peek() {
if(isEmpty()){
System.out.println("Stack Empty");
return 'E';
}
else{
// 현재 최상위 위치(top의 위치)의 값 반환
return stackArr[top];
}
}
// 스택의 내용을 비우는 clear()
public void clear() {
top = -1;
}
// 스택의 전체 데이터를 출력하는 showStack()
// 출력만 하고 반환값 얻음
// 먼저 출력하지 전에 스택이 비었는지 확인
// 스택에 있는 모든 요소의 값 출력 (배열의 모든 요소의 값 출력)
public void showStack() {
if(isEmpty()) {
System.out.println("Stack Empty");
}
else {
System.out.print("Stack items: ");
for(int i = 0; i <= top; i++){
System.out.print(i + ":" + stackArr[i] + " ");
}
System.out.println("\ntop : "+ top);
}
}
}
MyStackMain.java
package Stack;
public class MyStackMain {
public static void main(String[] args) {
// 스택 크기 설정
int stackSize = 5;
MyStack stk = new MyStack(stackSize);
System.out.print("Stack 초기 상태: ");
stk.showStack();
System.out.println("\npop 수행");
stk.pop();
System.out.println("\na, b, c push 수행");
stk.push('a');
stk.push('b');
stk.push('c');
stk.showStack();
System.out.println("\n최상위 값: " + stk.peek());
System.out.println("\nd, e push 수행");
stk.push('d');
stk.push('e');
stk.showStack();
System.out.println("\nf push 수행");
stk.push('f');
System.out.println("\npop 2번 수행");
System.out.println("pop한 값: "+stk.pop());
System.out.println("pop한 값: "+stk.pop());
stk.showStack();
System.out.println("\nclear 수행");
stk.clear();
stk.showStack();
}
}
[OUTPUT]
Stack 초기 상태: Stack Empty
pop 수행
Stack Empty. UnderFlow
a, b, c push 수행
Stack items: 0:a 1:b 2:c
top : 2
최상위 값: c
d, e push 수행
Stack items: 0:a 1:b 2:c 3:d 4:e
top : 4
f push 수행
Stack Full. Overflow
pop 2번 수행
pop한 값: e
pop한 값: d
Stack items: 0:a 1:b 2:c
top : 2
clear 수행
Stack Empty
StackTest.java (java.util.Stack 사용)
package Stack;
import java.util.Stack;
public class StackTest {
public static void main(String[] args) {
Stack<String> stk = new Stack<String>();
stk.push("홍길동");
stk.push("이몽룡");
stk.push("성춘향");
for(int i = 0; i < stk.size(); i++) {
System.out.println(i + ": " + stk.get(i));
}
System.out.println("스택 크키: "+ stk.size());
System.out.println("최상위 값: "+stk.peek());
System.out.println("이몽룡 들어 있는가? : "+stk.contains("이몽룡"));
System.out.println("pop 수행: "+stk.pop());
for(int i = 0; i<stk.size(); i++){
System.out.println(i + " : "+ stk.get(i));
}
System.out.println("clear 수행");
stk.clear();
System.out.println("empty? : "+ stk.empty());
}
}
[OUTPUT]
0: 홍길동
1: 이몽룡
2: 성춘향
스택 크키: 3
최상위 값: 성춘향
이몽룡 들어 있는가? : true
pop 수행: 성춘향
0 : 홍길동
1 : 이몽룡
clear 수행
empty? : true
