진짜 개발자
본문 바로가기

CS(Computer Science)/자료구조

자료구조 - 스택(Stack)이란

728x90

스택(Stack) 이란

- 스택은 원소의 삽입과 삭제가 "Top"에서만 이루어지도록 제한되어 있는 유한순서 리스트이다.

- 삽입 하는 연산을 Push 

- 삭제 연산을 Pop 이라고 한다.



특징

- 한쪽으로만 자료를 넣고 뺄 수 있는 구조로 되어 있어 마지막에 넣은 값이 가장 먼저 출력된다

 (LIFO 구조 - Last in First Out(후입선출))


활용

1. 컴퓨터 시스템 - 실행시간 스택이라는 것이 있는데 이 스택의 임무는 호출과 복귀에 따른 실행순서를 정확히 

  관리 하는 것이다. 서브 프로그램이 호출되면 시스템은 활성화 레코드 라는 것을 만들어 스택의 TOP에

 삽입한다 활성화 레코드에는 서브 프로그램의 실행이 끝난뒤 제어를 되돌려 주어야 하는 복귀 주소와, 지역변수 등이 들어 있다 때문에 스택의 TOP에는 항상 현재 실행되고 있는 함수의 활성화 레코드가 위치한다.

활성화 레코드를 실행하는 도중에 또 다른 함수를 호출하게 되면 또 다시 그 함수에 대한 활성화 레코드를 

만들어 스택의 TOP에 삽입한 다음 함수를 실행한다 이 함수의 실행이 끝나면 스택의 TOP에 있는 활성화 레코드를 삭제하면서 자연스레 이전 함수의 복귀주소로 제어가 전환된다.


2. 리스트 Reversing - 스택에 리스트의 모든 원소를 집어넣었다가 다시 하나씩 출력하여 삭제하면 리스트가 역순이 된다.




3. 수식 괄호쌍 검사 


4. 후위 표기식


5. 미로찾기


스택의 표현

1. 순차 표현

- top이라는 변수를 통해 top 인덱스를 지시한다

- 초기의 top은 -1 값으로 초기화 하여 빈 스택를 나타낸다


장점

- 간단하게 구현이 가능하다


단점

- 스택의 크기가 불확실 할때에는 확장시 확장연산이 오래걸리므로 안좋다


구현

1) 공백 검사

- 초기 빈 스택의 top을 -1로 초기화 하기로 했으므로

  top을 검사하여 값이 -1 이라면 스택이 비었음을 의미한다


2) 남은 공간 검사

- 스택에 데이터를 삽입할 때마다 top의 인덱스가 1만큼 증가하므로 

  top이 배열의 크기와 같아진다면 스택이 꽉찼음을 의미한다.


3) 삽입

- 삽입시 미리 만들어 놓은 isFull() 함수를 통해 스택의 여유공간이 있는지를 확인한 다음

  삽입전 top의 인덱스를 1증가시킨 다음 해당 위치에 Data를 삽입한다.


4) 삭제

- 삭제 전 역시 만들어 놓은 isEmpty() 함수로 삭제할 데이터가 있는지 확인한 후

  삭제될 데이터를 poped 변수에 저장하고 top의 인덱스를 1만큼 감소 시켜 데이터가 삭제되었음을 표시한다.


5) 전체 코드


2. 연결 표현


장점

- 필요한 메모리 공간만 할당받아 사용이 가능하다(유동적)


단점

- 링크 필드가 필요하므로 추가적인 공간이 필요


구현

1) 노드 클래스 생성

- 데이터를 담을 데이터변수와 스택의 아랫쪽 데이터를 가리킬 참조변수를 가진 Node 클래스를 생성


2) 공백 검사

- Node top 변수가 null 이라면 Stack이 비었음을 의미한다.


3) 삽입

- 삽입시 노드를 생성하고 top이 null이라면 top에 새로운 노드를 넣고

  이외의 경우에는 새로운 노드의 링크에 top의 주소를 넣고

  새로운 노드가 top이 되도록 한다.


3) 삭제

- 삭제시 미리 만들어둔 isEmpty() 메소드를 이용하여 스택이 비었는지를 먼저 확인한 후

  이외의 경우에는 현재 top의 data를 poped 변수에 저장한 후

  top이 가리키는 노드를 한칸 아래로 지정하여 최상단에 있는 노드를 가리키는 참조변수를

  없애 가비지 컬렉팅 대상이 되도록하여 삭제한다


4) 전체코드