[자료구조] Stack

Stack이란?

스택(stack)은 제한적으로 접근할 수 있는 나열 구조

그 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝먼저내기 목록(Pushdown list)이라고도 한다.

스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다. 꺼내지는 자료는 가장 최근에 보관한 자료부터 나오게 된다.

 

(출처 : Wikipedia - 스택)

 

• Push : 스택에 데이터 추가
• Pop : 스택에서 데이터 빼기

이미지 출처 : Wikipedia

 

• Top : 스택의 최상단을 의미. 이걸 넘어가면 Stack overflow 발생
• 스택에 더 이상 뺄 것이 없을 때 pop을 하면 Stack underflow 발생

스택의 구현방법

• 배열(배열을 이용할 경우 메모리 낭비가 발생할 수 있음)
  1. 스택을 선언하고 크기를 정해줌
  2. 최상단을 의미하는 Top 변수를 생성
  3. 추가할 때는 Top에 1을 더한 값에 데이터를 넣어줌
  4. 뺄 때는 데이터를 빼고 변경된 Top 위치를 업데이트하기 위해 1을 빼줌

• 연결리스트
  1. 스택 구조체를 만들어줌
  2. 포인터 변수를 만들어 다음 노드를 가리킬 수 있도록함
  3. 추가할 떄는 삽입할 노드의 next가 top을 가리키도록함
  4. 삭제할 때는 Top 노드를 두번째 노드로 변경해 주고, 기존 Top을 할당 해제함

 

 

 

 

 

참고 | Wikipedia, fast campus 컴퓨터공학 전공 필수