스택이란 📚
스택은 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료구조 입니다.
스택은 배열과 다르게 특정 인덱스에 바로 접근이 불가능합니다.
하지만, 스택은 원소의 삭제가 스택의 최상단 top을 통해서만 이루어지기 때문에 삽입과 삭제의 시간복잡도는 O(1)입니다.
LIFO란??
LIFO는 Last In First Out의 줄임말입니다. 번역하자면 후입선출, 즉 마지막에 들어온 것이 가장 먼저 나가는 구조입니다.
예시
철수는 매일매일 책 한권을 모두 읽기 계획을 실천하고 있습니다. 하지만, 정리를 싫어하는 철수는 매일 읽은 책들을 책상 한 켠에 쌓아 올렸습니다. 그러다보니 책들이 산처럼 쌓여버렸습니다. 그 모습을 본 철수 어머니는 철수에게 책상 정리를 하라고 말씀하셨습니다. 철수는 최대한 빨리 정리를 끝내고 싶었지만, 책이 너무 많아 모든 책들을 한 번에 들 수 없었고 한 번에 한 권씩 맨 위에 쌓여있는 책부터 치울 수 밖에 없었습니다.
스택의 대표적인 사용 사례
- 웹 브라우저 뒤로가기
- 실행 취소(undo, ctrl+z)
- 후위 표기법 계산
- 역순 문자열 만들기
- 수식의 괄호 검사
스택을 코드로 구현해보겠습니다 💻
스택은 최상위 위치인 top을 기준으로 데이터 삽입과 삭제가 일어납니다.
스택의 주요 메서드❗️
스택의 주요 메서드는 다음과 같습니다.
push: 스택의 top에 데이터 삽입pop: 스택의 top의 데이터 반환 후 제거peek: 스택의 top의 데이터 반환isFull: 스택이 다 찼는 지 검사(포화 검사)isEmpty: 스택이 비어있는 지 검사(공백 검사)
주요 메서드 중 가장 먼저 만들어야 하는 메서드는 무엇일까요??
바로 isEmpty와 isFull 메서드입니다.
왜냐하면, 스택이 공백이거나 포화 상태이면 push나 pop을 진행할 수 없기 때문입니다.
그렇다면 스택을 C와 Java로 만들어보겠습니다.
C로 만드는 스택
C언어로는 스택을 배열을 사용해 구현하였습니다.
스택의 초기상태는 스택 안에 아무 것도 들어있지 않은 상태이므로 스택의 초기상태를 스택의 top이 -1인 상태로 설정했습니다.
#include <stdio.h>
#include <stdbool.h>
#define MAX_SIZE 100
typedef struct _Stack {
int data[MAX_SIZE];
int top;
} Stack;
void init(Stack* s) {
s -> top = -1;
}
int main(void) {
Stack stack;
init(&stack);
}스택이 공백 상태인지 검사하는 isEmpty 메서드를 구현해보겠습니다.
isEmpty 메서드의 원리는 스택의 top 값을 토대로 판단합니다. 스택의 공백 상태는 top의 값이 -1이라면 스택에 아무것도 들어있지 않는 상태입니다.
/*
isEmpty : 공백 검사 메서드
params : stack포인터, 이유 = 스택에 직접 접근해서 값을 변경해야하기 때문
return : bool, 이유 = 참, 거짓 판별
*/
bool isEmpty(Stack* s) {
return (s->top == -1);
}스택이 포화 상태인지 검사하는 isFull 메서드를 구현해보겠습니다.
스택의 포화 상태는 스택의 top의 값이 스택이 담을 수 있는 최대 원소의 개수 - 1과 같다면 더 이상 스택에 원소를 담을 수 없는 상태입니다.
/*
isFull : 포화 검사 메서드
params : stack포인터, 이유 = 스택에 직접 접근 -> 값 변경
return : bool , 이유 = 참, 거짓 판별
*/
bool isFull(Stack* s) {
return (s->top == (MAX_SIZE - 1));
}다음으로 스택에 원소를 삽입하는 push 메서드를 구현해보겠습니다.
/*
push : 삽입 메서드
params : stack포인터, int형 변수
return : bool
*/
bool push(Stack* s, int item) {
if(isFull(s)){
printf("스택이 다 찼습니다\n");
return false;
}
else {
// ++을 먼저 하는 이유 : 초기 top -1
s->data[++(s->top)] = item;
return true;
}
}다음은 스택에서 원소를 꺼내는 pop 메서드를 구현해보겠습니다.
👉 본 코드는 예제이므로 스택이 비어있다면 -1을 리턴하도록 했습니다. 스택에 -1인 원소가 존재할 수 있기 때문에 실제 구현에서는 다음과 같이 구현하면 안됩니다.
/*
pop : 삭제 메서드
params : stack포인터
return : bool
*/
int pop(Stack* s) {
if(isEmpty(s)){
printf("스택이 비었습니다.\n");
return -1; // 예제여서 -1 리턴
}
else {
return s->data[(s->top)--];
}
}
다음은 스택의 top에 있는 원소를 검색하는 peek 메서드를 구현해보겠습니다.
👉 본 코드는 예제이므로 스택이 비어있다면 -1을 리턴하도록 했습니다. 스택에 -1인 원소가 존재할 수 있기 때문에 실제 구현에서는 다음과 같이 구현하면 안됩니다.
/*
peek : 검색 메서드
params : stack포인터
return : int
*/
int peek(Stack* s) {
if(isEmpty(s)) {
printf("스택이 비었습니다.\n");
return -1;
}
else {
return s->data[(s->top)];
}
}Java로 만드는 스택
Java는 연결리스트(Linked List)방식으로 스택을 구현했습니다.
Java에서는 기본적으로 Stack 자료구조를 제공해주기 때문에 별도로 구현해서 사용할 필요가 없습니다. 하지만, Java로 한번 구현해보는 경험은 좋은 것 같습니다.
연결리스트 방식으로 구현했기 때문에 isFull 메서드는 구현하지 않았습니다.
public class Stack<T> {
class Element {
T data;
Element next;
public Element(T data) {
this.data = data;
}
}
Element top;
boolean isEmpty() {
return top == null;
}
void push(T data) {
Element e = new Element(data);
e.next = top;
top = e;
}
T pop() {
if(isEmpty()) {
throw new NoSuchElementException("스택이 비어있습니다.");
}
T data = top.data;
top = top.next;
return data;
}
T peek() {
if(isEmpty()) {
throw new NoSuchElementException("스택이 비어있습니다.");
}
return top.data;
}
}