자료구조 - Stack(스택)

Stack 이란?

후입선출(LIFO : Last-In First-Out)의 특성을 가지는 자료구조(Data Structure)를 일컫는다.

Stack에서의 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없다.

Stack에서 입출력이 이루어지는 부분을 스택 상단(stack top) 이라 하고 반대쪽인 바닥 부분을 스택 하단(stack bottom) 이라고 한다.

Stack에 저장되는 것을 요소(element)라 부르며, Stack에 요소가 하나도 없을 때 그러한 Stack을 공백 스택(empty stack) 이라고 한다.

---

Stack의 연산

• push() : 삽입 연산으로 스택의 맨 위에 item을 추가한다.
• pop() : 삭제 연산으로 스택의 맨 위의 원소를 제거해서 반환한다.
• is_empty() : 스택이 공백상태에 있는지 검사한다.
• is_full() : 스택이 포화상태에 있는지 검사한다.
• peek() : 스택의 맨 위의 원소를 제거하지 않고 반환한다.

---

Stack의 구현

Stack을 구현하는 방법에는 배열을 이용하는 방법과 연결 리스트를 이용하는 방법이 있다.

• 배열은 구현하는 방법은 간단하고 성능이 우수한 반면에 스택의 크기가 고정되는 약점이 있다.

• 연결리스트를 이용하는 방법은 구현이 약간 복잡한 반면, 스택의 크기를 필요에 따라 가변적으로 할 수 있다.

정수 배열 Stack 구현

#include <stdio.h>
#include <stdlib.h>

#define MAX_STACK_SIZE 100     // Stack의 최대 크기
typedef int element;           // Data 자료형
element stack[MAX_STACK_SIZE]; // 1차원 배열
int top = -1;

//공백상태 검출
int is_empty(){
    return (top == -1);
}

//포화상태 검출
int is_full(){
    return(top == (MAX_STACK_SIZE - 1));
}

//삽입 연산
void push(element item){
    if(is_full()){
        fprintf(stderr, "스택 포화 에러");
        return;
    }
    else stack[++top] = item;
}

//삭제 연산
element pop(){
    if(if_empty()){
        fprintf(stderr, "스택 공백 에러");
        exit(1);
    }
    else return stack[top--];
}

//peek function
element peek(){
    if(is_empty()){
        fprintf(stderr, "스택 공백 에러");
        exit(1);
    }
    else return stack[top];
}

int main (void){
    push(1);
    push(2);
    push(3);
    printf("%d\n", pop());
    printf("%d\n", pop());
    printf("%d\n", pop());
    return 0;
}

실행 결과

3
2
1

---

Java에서의 Stack

java에서 Stack은 jata.util.Stack을 import해주면 바로 사용 할 수 있다.

Stack 선언

import java.util.Stack; //import Stack
Stack<Integer> stack = new Stack<>();
Stack<String> stack = new Stack<>();

Stack 메서드

stack.push(5); //stack에 값 5 추가
stack.pop(); //stack의 마지막 push 제거
stack.clear(); //stack 전체 삭제
stack.peek(); //stack의 마지막 push값 확인
stack.size(); //stack의 크기 확인
stack.empty(); //stack의 공백 여부 확인
stack.contains(1); //stack안에 '1'이 들어있으면 true, stack안에 값을 확인