[바미] 자료구조 - 스택(Stack)
스택(Stack)
스택(Stack)은 자료 구조 중 하나로, 데이터가 LIFO(Last In, First Out) 방식으로 관리되는 구조입니다.
즉, 가장 나중에 삽입된 데이터가 가장 먼저 제거되는 구조를 가진 자료 구조죠.
스택의 주요연산
스택은 다음과 같은 주요 연산을 제공합니다.
- Push: 스택의 맨 위에 데이터를 삽입하는 연산.
- Pop: 스택의 맨 위에 있는 데이터를 제거하고 반환하는 연산.
- Peek (or Top): 스택의 맨 위에 있는 데이터를 제거하지 않고 반환하는 연산.
- IsEmpty: 스택이 비어 있는지 확인하는 연산.
- IsFull: 스택이 가득 찼는지 확인하는 연산 (배열 기반 스택의 경우).
코드(Java)
class Stack {
private int[] arr;
private int top;
private int capacity;
// 스택 생성자
public Stack(int size) {
arr = new int[size];
capacity = size;
top = -1;
}
// 스택에 요소를 추가
public void push(int item) {
if (isFull()) {
System.out.println("Stack is full");
return;
}
arr[++top] = item;
}
// 스택에서 요소를 제거
public int pop() {
if (isEmpty()) {
System.out.println("Stack is empty");
return -1;
}
return arr[top--];
}
// 스택이 비어있는지 확인
public boolean isEmpty() {
return top == -1;
}
// 스택이 꽉 찼는지 확인
public boolean isFull() {
return top == capacity - 1;
}
// 스택의 크기 반환
public int size() {
return top + 1;
}
// 스택의 top 요소 확인
public int peek() {
if (isEmpty()) {
System.out.println("Stack is empty");
return -1;
}
return arr[top];
}
}
// 메인 클래스
public class Main {
public static void main(String[] args) {
// 스택의 크기를 5로 설정하여 새로운 스택 생성
Stack stack = new Stack(5);
// 스택에 요소를 추가
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
// 스택의 최상위 요소를 출력
System.out.println("Top element is: " + stack.peek());
// 스택에서 요소를 제거
stack.pop();
// 스택의 최상위 요소를 출력
System.out.println("Top element is: " + stack.peek());
// 스택의 크기를 출력
System.out.println("Stack size is " + stack.size());
// 스택에서 모든 요소를 제거
stack.pop();
stack.pop();
stack.pop();
stack.pop();
// 스택이 비어 있는지 확인하고 출력
if (stack.isEmpty()) {
System.out.println("Stack is empty");
}
}
}코드 설명
Stack 클래스와 Main 클래스로 나뉩니다. 먼저 Stack 클래스부터 설명드리겠습니다.
Stack 클래스
private int[] arr; // 스택의 요소를 저장할 배열
private int top; // 스택의 최상위 요소를 가리키는 인덱스
private int capacity; // 스택의 최대 크기
위에서 각 필드들을 선언해줍니다.
public Stack(int size) {
arr = new int[size];
capacity = size;
top = -1;
}스택 생성자부분입니다. 스택의 크기를 설정하고 배열을 초기화시켰습니다.
top을 -1로 설정함으로써 스택이 비어 있음을 나타냅니다.
public void push(int item) {
if (isFull()) {
System.out.println("Stack is full");
return;
}
arr[++top] = item;
}스택의 요소를 추가하는 메소드 부분입니다. 먼저 스택이 가득 찼는지 확인하는데 가득 차면 메시지를 출력하고 리턴합니다. 그렇지 않으면 top을 증가시키고 해당 위치에 요소를 추가하는 형태입니다.
public int pop() {
if (isEmpty()) {
System.out.println("Stack is empty");
return -1;
}
return arr[top--];
}요소를 제거하는 메소드 부분입니다. 먼저 스택이 비어 있는지 확인하고, 비어 있으면 메시지를 출력하고 -1을 반환하고,
그렇지 않으면 현재 top 위치의 요소를 반환하고 top을 감소시킵니다.
public boolean isEmpty() {
return top == -1;
}
public boolean isFull() {
return top == capacity - 1;
}스택이 꽉 찼는지, 비어있는지 확인하기위해 사용하는 메소드들입니다.
top이 -1이면 스택이 비어있다는 것을, top이 capacity - 1이면 스택이 가득 찼다는 것을 의미합니다.
public int size() {
return top + 1;
}현재 스택의 크기를 반환해주는 메소드입니다.
public int peek() {
if (isEmpty()) {
System.out.println("Stack is empty");
return -1;
}
return arr[top];
}스택의 최상위 요소를 반환해주는 메소드입니다.
먼저 스택이 비어 있는지 확인하고, 비어 있으면 메시지를 출력하고 -1을 반환하고, 그렇지 않으면 현재 top 위치의 요소를 반환해주죠.
Main 클래스
이제 Main 클래스 부분입니다.
Stack stack = new Stack(5);먼저 크기가 5인 새로운 스택을 생성시켜줍니다.
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);그리고 스택이 차례대로 1~5까지 추가할 수 있게 만들어줍니다.
System.out.println("Top element is: " + stack.peek());현재 스택의 최상위 요소를 출력합니다. 현재 최상위 요소는 당연히 5겠죠?
stack.pop();이제 요소 하나를 제거해보겠습니다. 그 후 제거가 제대로 됐는지 확인해 볼까요?
System.out.println("Top element is: " + stack.peek());스택의 최상위 요소를 다시 출력해봅시다. 이제 최상위 요소는 4가 되겠죠?
System.out.println("Stack size is " + stack.size());스택의 현재 크기를 출력해줍니다. 현재 크기는 4가 되겠군요.
stack.pop();
stack.pop();
stack.pop();
stack.pop();이제 이 모든 요소를 제거해봅시다. 4, 3, 2, 1이 차례로 제거될겁니다.
if (stack.isEmpty()) {
System.out.println("Stack is empty");
}이제 스택이 비어있는지 확인하고 비어 있으면 "Stack is empty"를 출력하도록 만들었습니다.
스택은 어느정도의 크기까지 만들어 낼 수 있는가?
주로 사용하는 언어와 환경에 따라 결정되는데 크게 프로그래밍 언어에 따라, 운영 체제, 하드웨어에 따라, 컴파일러, 런타임 설정에 따라 스택의 요소를 제한되고 있습니다.
⚠ 주의
스택의 크기는 제한적이므로, 재귀 함수 호출이 너무 깊어지거나 스택을 과도하게 사용하는 경우 스택 오버플로우(Stack Overflow)가 발생할 수 있습니다.
❓ 스택오버플로우 (Stack Overflow)
프로그램이 할당된 스택 메모리를 초과하여 더 이상 사용할 수 없는 상태를 의미합니다.
프로그래밍 언어에서
Java의 경우 기본적으로 각 스레드마다 고정된 스택의 크기가 있습니다. 각 스레드에 대해 1MB의 스택 크기가 기본적으로 할당되고, -Xss 옵션을 사용하여 크기를 조정할 수 있습니다.
C/C++의 경우 일반적으로 1MB ~ 8MB 사이로 설정되는데 컴파일러나 링커 옵션을 사용하여 크기를 조정할 수 있습니다.
Python의 경우 기본적으로 8MB의 스택 크기가 할당되며 sys.setrecursionlimit() 함수를 사용하여 재귀 한도를 설정할 수 있습니다.
운영 체제 및 하드웨어에서
스택은 메모리의 특정 영역에 할당되며, 운영 체제와 하드웨어의 메모리 구조에 따라 크기가 결정되는데 32bit 시스템과
컴파일러 및 런타임 설정
위 '프로그래밍에서' 부분에서 설명 드린 것처럼 컴파일러 옵션이나 런타임 설정을 통해 스택 크기를 조정할 수 있습니다.