[자료구조] 스택(Stack)

  스택(Stack)이란 후입선출(Last In First Out; LIFO), 즉 마지막에 들어온 데이터가 먼저 나가는 구조입니다. 데이터가 입력된 순서의 역순으로 처리되어야 할 때 사용합니다. 예를 들어 함수 콜 스택, 수식 계산, 인터럽트 처리 등이 있습니다. 데이터 추가, 꺼내기, 스택 공간 확인 동작으로 이루어집니다.

  스택의 동작 예시 다음과 같습니다.

↓push()	↑pop()
3(3)	3(1)
2(2)	2(2)
1(1)	1(3)

  일반 숫자는 원소, 괄호 안 숫자는 순서를 의미합니다. 예를 들어, push는 1, 2, 3 순서대로 원소가 삽입되었습니다. 그러나 pop으로 원소를 꺼내고자 할 때에는 3, 2, 1과 같이 삽입할 때의 역순으로 원소를 꺼내게 됩니다. 스택에서는 항목을 위에서 push하고, 스택의 가장 위에 있는 항목을 pop합니다.

  스택 자료구조를 응용하여 풀 수 있는 문제로는 괄호 짝 맞추기, 회문(Palindrome) 검사, 후위 표기법(Postfix notation) 수식 계산, 중위 표기법(Infix notation) 수식의 후위 표기법 변환 등이 있습니다.

  배열로 구현한 스택의 push와 pop 연산은 각각 O(1) 시간이 소요됩니다. 단순 연결 리스트로 구현한 스택 역시 push와 pop연산은 각각 O(1) 시간이 걸립니다. 연결 리스트의 맨 앞부분에서 노드를 삽입하거나 삭제하기 때문입니다. 배열과 단순 연결 리스트로 구현된 스택의 장단점은 리스트를 배열과 단순 연결 리스트로 구현했을 때의 장단점과 동일합니다.

 

  주요 메소드

• push(): 값 추가
• pop(): 값 추출 혹은 제거
• peek(): 스택의 가장 상단 값 출력
• isEmpty(): 스택이 비어있으면 true
• size(): 스택의 크기 출력

 

  ※ "자바와 함께하는 자료구조의 이해"라는 책을 참고하여 쓴 게시글입니다. 책에는 없는 내용을 추가하여 작성된 부분이 있습니다. 문제가 되거나 부정확한 부분이 있다면 알려주시면 감사하겠습니다.

  ※ 책은 게시글보다 정확한 내용을 담고 있으며 코드, 그림, 예제를 이용하여 개념을 자세히 설명합니다.