[자료구조] - 스택 (Stack)

📌스택(Stack)의 개념

LIFO(Last In First Out) 또는 FILO(First In Last Out) 형태로 동작하는 선형 자료 구조

 

 

스택(Stack)의 사전적 의미는 "더미", "쌓다"로 자료 구조의 스택도 데이터를 순차적으로 나열한 구조이다.

가장 최근에 보관한 자료를 꺼내는 방식으로 동작한다. 

 

스택의 연산은 Push와 Pop이 있다.

Push는 삽입 연산으로 가장 위에 원소를 추가하고, Pop은 삭제 연산으로 가장 위의 원소를 반환한다.

Top은 스택의 맨 위에 위치해 있는 원소를 가리킨다.

Push와 Pop은 Top으로 지정된 곳에서만 가능하다. 

따라서 스택의 접근(Push와 Pop)은 한 곳(Top)에서만 일어난다.

 

스택의 예시로는 아래와 같이

접시를 쌓았을 때 맨 위의 제일 마지막으로 쌓은 접시부터 쓰게 되는 것을 생각하면 이해하기 쉽다.

 

 

 

✨스택(Stack)의 특징

• 제일 위의 데이터만 알 수 있다.
• 스택이 담을 수 있는 크기를 초과하여 자료를 Push 하면 스택 오버플로우(Stack Overflow)가 발생한다.
• 스택이 비었을 때 Pop을 하면 스택 언더플로우(Stack Underflow)가 발생한다.

 

 

 

🔨스택(Stack)의 활용 사례

※ 주로 왔던 길을 되돌아갈 때 유용

• 웹 브라우저의 뒤로 가기
• 문서 작업의 Ctrl + z (Undo)
• 역순 문자열 생성
• 후위 표기법 계산
• 함수 호출 시 복귀 저장
• 재귀 함수 호출 시 복귀 저장

 

 

 

💻스택의 연산

• push(item) : 스택에 데이터(item) 추가
• pop() : 스택의 맨 위 원소를 제거하고 반환
• peek() / top() : 스택의 맨 위의 값을 반환 (제거하지 않음)
• clear() : 스택 안 모든 값 강제 초기화 혹은 비어있는지 여부 확인
• empty() / isEmptyStack() : 스택이 비어있는지 여부 확인 (비어있다면 True, 비어있지 않다면 False)
• full() / isFullStack() : 스택이 가득 찼는지 여부 확인 (차 있다면 True, 차있지 않다면 False)
• size() : 현재 스택에 들어있는 원소의 개수 반환 (크기 확인)

 

---

참고

http://www.ktword.co.kr/test/view/view.php?m_temp1=1306

---

⬇ 파이썬으로 스택 간단 구현하기

[자료구조] - Python으로 스택 구현하기