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

오늘은 컴퓨터에서 정말 많이 사용되는 자료구조인 스택에 대해 알아 볼 것이다.

스택(Stack)

스택을 사전에서 찾아보면 더미, 낟가리 를 의미한다고 되어 있다. 스택은 말 그대로 자료들이 더미로 쌓여있는 것과 유사하게 작동을 한다. 예를 들어 창고에 상자들을 쌓는다고 해보자. 가장 먼저 쌓은 상자는 가장 마지막에 꺼낼 수 있다. 가장 최근에 쌓은 상자는 가장 먼저 꺼낼 수 있다. 이러한 형태를 '후입선출'이라고 하며, 스택은 후입선출을 대표하는 자료형이다.

스택은 다양한 곳에 사용된다. 컴퓨터 프로그램을 실행하면 수많은 함수호출이 이루어진다. 함수는 실행이 끝나면 자신을 호출한 함수로 돌아가야하는데 이때 돌아갈 주소를 저장하는 것도 스택이다. 

스택의 구조와 추상자료형

스택은 말그대로 데이터가 들어가는 곳과 나오는 곳이 같은 곳이다. 그래서 보통 아래와 같이 도식화한다.

stack의 구조

스택에는 기본적인 두 가지의 연산이 있다. 하나는 삽입연산으로 push 연산이라고도 한다. 또 하나는 삭제 연산으로 pop 연산이라고 한다. 

/*스택의 추상자료형
객체 : 0개 이상 원소를 가지는 유한 선형리스트*/
//연산:
create(size) //최대크기 size
isfull(s)
	if(원소 == size)
    	return True
	else
    	return False
isempty(s)
	if(원소 == 0)
    	return True
    else
    	return False
push(s, item)
	if(isfull(s))
    	return ERROR_STACKFULL
    스택의 맨 위에 item 추가
pop(s)
	if(isempty(s))
		return ERROR_STACKEMPTY
    스택의 맨 위 item 삭제와 동시에 반환
peek(s)
	if(isempty(s))
    	return ERROR_STACKEMPTY
    스택의 맨 위 item 반환

 

구현 방식은 크게 배열로 구현하는 방법과 연결리스트를 이용해 구현하는 방법이 있다. 

배열로 구현하는 방법 - https://mobuk.tistory.com/22

[자료구조] C - 스택(Stack) - 배열을 이용한 구현