스택

이번에 소개하는 스택은 리스트와 마찬가지로 대표적인 선형 자료구조 이다.

 

스택을 도구를 이용해 설명을 하자면 '쌓아진 상자 더미'나 '쟁반 위에 쌓인 접시'로 비유할 수 있다.

 

즉 스택은 다음과 특성을 지닌다.

"먼저 들어간 것이 나중에 나온다"

이렇듯 스택은 나중에 들어간 것이 먼저 나오는 구조이므로 '후입선출' 방식의 자료구조로 불리고, 영어로 'LIFO(Last-In, First-Out)구조의 자료구조'라고도 불린다.

 

스택의 ADT를 정의해 보자.

앞서 살펴본 리스트 자료구조의 ADT는 필요에 따라서 그 정의 내용에 약간 씩 차이가 있다. 그에 비해 스택의 ADT는 상대적으로 정형화된편이다.

 

스택을 대표하는 넣고, 꺼내고, 들여다 보는 연산을 가리켜, push, pop, peek라 한다. 떄문에 스택의 ADT는 다음과 같이 정의가 되며, 이것이 스택의 보편적인 ADT이다. 

 

void StackInit(Stack *pstack);

-스택의 초기화를 진행한다.

-스택 생성 후 제일먼저 호출되어야 하는 함수이다.

 

int SIsEmpty(Stack *pstack)

-스택이 빈 경우 TRUE(1)을, 그렇지 않은 경우 FALSE(0)을 반환한다.

 

void SPush(Stack *pstack, Data data)

-스택에 데이터를 저장한다. 매개 변수 data로 전달된 값을 저장한다.

 

Data SPop(Stack *pstack);

-마지막에 저장된 요소를 삭제한다.

-삭제된 데이터는 반환이 된다.

-본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

 

Data SPeek(stack *pstack);

-마지막에 저장된 요소를 반환하되 삭제하지 않는다.

-본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

 

---

스택의 배열기반 구현

 

데이터를 추가하는 과정을 살펴보자.

topIndex= -1

0

1

2

3

4

5

->Push 'A'

 

A

A가 top이므로

topIndex= 0

->Push 'Z'

A

Z

topIndex= 1

Z가 top

 

위 과정에서 주목할 것 두가지는 다음과 같다.

인덱스 0의 배열 요소가 '스택의 바닥'으로 정의되었다.

마지막에 저장된 데이터의 위치를 기억해야한다.  

위의 표를 세로로 세워 생각을 해야한다.

 

우선 인덱스 0의 배열 요소를 스택의 바닥으로 둔 이유는 다음과 같다.

"인덱스 0의 요소를 스택의 바닥으로 정의하면, 배열의 길이에 상관 없이 언제나 인덱스 0의 요소가 스택의 바닥이 된다."

 

그리고 위 과정에서는 가장 최근에 저장된, 다시 말해서 가정 위에 저장된 데이터를 Top으로 가리키고 있으며, 이 Top이 가리키는 위치의 인덱스 값을 변수 topIndex에 저장하고 있다.(실제로 Top은 변수 topIndex를 의미한다). 이렇듯 마지막에 저장된 데이터의 위치를 별도로 기억해둬야 다음과 같이 push연산과 pop연산을 쉽게 완성할 수 있다.

 

push : Top을 위로 한칸 올리고, Top이 가리키는 위치에 데이터 저장

pop : Top이 가리키는 데이터를 반환하고, Top을 아래로 한 칸 내림

 

이렇듯 배열 기반 스택은 그 구조가 단순하다. 이를 기반으로 스택의 헤더파일의 정의해보자.

#ifndef __AB_STACK_H__
#define __AB_STACK_H__

#define TRUE 1
#define FALSE 0
#define STACK_LEN 100

typedef int Data;

typedef struct _arrayStack
{
	Data stackArr[STACK_LEN];
    int topIndex;
}ArrayStack;

typedef ArrayStack Stack;

void StackInit(Stack *pstack);  //스택의 초기화
int SIsEmpty(Stack *pstack);  //스택이 비었는지 확인

void SPush(Stack *pstack, Data dta);  //스택의 push연산
Data SPop(Stack *pstack);  //스택의 pop연산
Data SPeek(Stack *pstack);  //스택의 peek연산

#endif

 

배열 기반 스택의 구현

스택을 표현한 다음 구조체의 정의를 보면 StackInit 함수를 무엇으로 채워야 할지 알 수 있다.

 

typedef struct _arrayStack

{
  Data stackArr[STACK_LEN];

  int topIndex;

}ArrayStack;

 

이 중에서 초기화할 멤버는 가장 마지막에 저장된 데이터의 위치를 가리키는 topIndex 하나이다. 따라서 StackInit 함수는 다음과 같이 정의된다.

 

void StackInit(Stack *pstack)

{
  pstack->topIndex= -1;  //topIndex의 -1은 빈 상태를 의미함

}

 

topIndex에 0이 저장되면, 이는 인덱스 0의 위치에 마지막 데이터가 저장되었음을 뜻하는 것이 된다. 따라서 topIndex를 0이 아닌 -1로 초기화 해야한다.

이어서 SIsEmpty 함수의 정의를 보자. 이 함수는 스택이 비었는지 확인할 때 호출하는 함수이다. 스택이 비어있는 경우 topIndex의 값이 -1이니, 이 함수는 다음과 같이 정의 되어야 한다.

 

int SisEmpty(Stack *pstack)
{
  if(pstack->topIndex == -1)  //스택이 비었다면

    return TRUE;

else

  return FALSE;

}

이제 스택의 핵심인 SPush 함수와 SPop 함수를 보일 차례인데, 이 둘 역시 다음과 같이 간단히 정의가 된다.

 

void SPush(Stack *pstack, Data data)  //push연산 담당 함수

{
  pstack->topIndex +=1;  //데이터 추가를 위한 인덱스 값 증가

  pstack->stackArr[pstack->topIndex] = data;  //데이터 저장

}

 

Data SPop(Stack *pstack)  //pop 연산 담당 함수

{
  int rIdx;

 

  if(SIsEmpty(pstack)){
  printf("Stack Memory Error!");

  exit(-1);

}

 

rIdx= pstack->topIndex;  //삭제할 데이터가 저장된 인덱스 값 저장

  pstack->topIndex -= 1;  //pop 연산의 결과로 topIndex 값 하나 감소

 

 return pstack->stackArr[rIdx];  //삭제되는 데이터 반환

}

 

꺼낸다는 의미의 pop에는 삭제와 반환의 의미가 함께 담겨있 다. 꺼냈으니 삭제가 된것이고, 꺼냇으니 반환도 이뤄지는 것이다.

그리고 topIndex의 값을 근거로 하여 데이터를 젖아하니, 이 변수에 저장된 값을 하나 감소시키는 것만으로도 데이터의 소멸은 완성이된다.

 

이제 마지막으로 Speek 함수를 정의할 차례인데, 이 함수는 SPop 함수와 달리 반환한 데이터를 소멸시키지 않으므로 다음과 같이 간단히 정의가 가능하다.

Data SPeek(Stack *pstack)  //peek연산 담당 함수

{

  if(SIsEmpty(pstak))

  {

    printf("Stack Memory Error!");

    exit(-1);

  }

   retunr pstack->stackArr[pstack->topIndex];  //맨 위에 저장된 데이터 반환

}

 

프로그램을 구현하다 보면 스택이 반환할 다음 데이터를 확인할 필요가 간혹 있다. 그런데 그때마다 pop함수를 호추하면 확인가 동시에 소멸이 되니, 확인을 하되 소멸시키지 않는 함수가 필요하다. 그래서 위와 같은 peek 연산을 담당하는 함수를 스택의 정의에 포함하기도 한다.

그럼 지금까지 소개한 함수들을 하나의 소스파일로 묶어보자.

 

//ArrayBaseStack.c
#include <stdio.h>
#include <stdlib.h>
#include "ArrayBaseStack.h"

void StackInit(Stack *pstack)
{
	pstack->topIndex= -1;
}

int SIsEmpty(Stack *pstack)
{
	if(pstack->topIndex ==-1)
	      return TRUE;
  	else
   		return FALSE;
}

void SPush(Stack *pstack, Data data)
{
	int rIdx;
    
    if(SIsEmpty(pstack))
    {
		printf("Stack Memory Error!");
        exit(-1);
   	}
    
    rIdx= pstack->topIndex;
    pstack->topIndex -= 1;
    
    return pstack ->stackArr[rIdx];
}

Data SPeek(Stack *pstack)
{
	if(SIsEmpty(pstack))
    {
    	printf("Stack Memory Error!");
        exit(-1);
   	}
    
    return pstack->stackArr[pstack->topIndex];
}

//ArrayBaseStackMain.c
#include <stdio.h>
#include "ArrayBaseStack.h"

int main()
{
	//Stack의 생성 및 초기화
    Stack stack;
    StackInit(&stack);
    
    //데이터 넣기
    SPush(&stack, 1); SPush(&stack, 2);
    SPush(&stack, 3); SPush(&stack, 4);
    SPush(&stack, 5); 
    
    //데이터 꺼내기
    while(!SIsEmpty(&stack))
    	printf("%d ", SPop(&stack));
        
    return 0;
}
=====================실행 결과===================
5 4 3 2 1    

실행결과에서는 입력된 데이터가 역순으로 출력됨을 보이고 있다. 그리고 이것이 스택의 가장 중요한 특성이다

 

---

스택의 연결 리스트 기반 구현

기능적인 부분만 고려한다면 배열은 대부분 연결리스트로 교체가 가능하다. 배열도 연결리스트도 기본적인 선형 자료구조 이기 때문이다.

 

연결리스트 기반 스택의 논리와 헤더파일의 정의

앞서 구현한 스택에서 배열을 연결 리스트로 변경할 경우, 연결 리스트가 갖는 특징이 그대로 스택에 반영된다. 하지만 연결 리스트를 기반으로 스택을 구현한다고 하면 부담을 느끼는 경우가 많다. 연결 리스트도 어려운데 이것을 이용해서 스택을 구현해야 하기 때문에 뭔가 두 배로 고민을 해야 한다고 생각하기 때문이다. 

 

"스택도 연결리스트이다. 다만 저장된 순서의 역순으로 조회(삭제)가 가능한 연결 리스트 일뿐이다."

 

이렇게 메모리 구조만 놓고 보면 이것이 스택을 구현한것인지, 단순 연결리스트를 구현한 것인지 알 수 없다. 다만 과거에 했던 노드를 머리에 추가하는 형태로 구현한 연결리스트 같은 메모리 구조를 바탕으로 push연산과 pop연산이 포함된 ADT를 갖는다면 이것이 스택이 되는 것이다. 그럼 위의 연결리스트의 모델과 앞서 정의한 스택 ADT를 기준으로 연결리스트 기반의 스택을 구현해보자.

 

위의 과정에서 보이듯이 스택을 구현하기 위해서 필요한 것은 포인터 변수 head하나이니, 연결리스트기반의 스택을 위한 헤더파일은 다음과 같이 정의할 수 있다.

//ListBaseStack.h
#ifndef __LB_STACK_H__
#define __LB_STACK_H__

#define TRUE 1
#define FALSE 0

typedef int Data;

typedef struct _node  //연결 리스트의 노드를 표현한 구조체
{
	Data data;
   	struct_node *next;
}Node;

typedef struct _listStack  //연결 리스트 기반 스택을 표현한 구조체
{	
	Node *head;
}ListStack;

typedef ListStack Stack;

void StackInit(Stack *pstacK);  //스택의 초기화
int SIsEmpty(Stack *pstack);  //스택이 비었는지 확인

void SPush(Stack *pstack, Data data);  // 스택의 push연산
Data SPop(Stack *pstack);  //스택의 pop연산
Data SPeek(Stack *pstack);  //스택의 peek연산

#endif

위의 헤더파일에 선언된 함수의 종류와 그 기능은 앞서 보인 배열 기반 스택의 경우와 다르지 않다. 내부 구현이 배열에서 연결 리스트로만 바뀌는 것이니 이는 당연한 일이다.

 

---

연결리스트의 기반의 스택의 구변

 

void StackInit(Stack *pstack) 

{

  pstack->head =NULL;   //포인터 변수 head는 NULL로 초기화

}

 

int SIsEmpty(Stack *pstack)

{

  if(pstack->head ==NULL)  //스택이 비면 head에는 NULL 이 저장된다

     return TRUE;

  else

  return FALSE;

}

 

위의 함수 정의에서 보이듯이, 포인터 변수 head는 새로 추가된 노드를 가리켜야 하므로, 비어있는 상태를 표현하기 위해 NULL로 초기화를 진행하였다. 그리고 스택이 비어있는 경우 head에는 NULL이 저장되므로, head가 NULL일 떄 TRUE를 반환하도록 SIsEmpty함수를 정의하였다.

이어서 SPush 함수와 SPop 함수를 정의할 차례인데, SPush함수는 리스트의 머리에 새 노드를 추가하는 함수이니 당므과 같이 정의해야 한다.

 

void SPush(Stack *pstack, Data  data)

{

  Node *newNode= (Node *)malloc(sizeof(Node));  //새 노드 생성

  

  newNode->data = data;   //새 노드에 데이터 저장

  newNode->next= pstack->head;   // 새노드가 최근에 추가된 노드를 가리킴

  

  pstack->head= newNode;   //포인터 변수 head가 새노드를 가리킴

}

 

반대로 SPop 함수는 포인터 변수 head가 가리키는 노드를 소멸 시키고, 소멸된 노드의 데이터를 반환해야 하므로 다음과 같이 정의해야 한다.

 

Data SPop(Stack *pstack)

{
  Data rdata;

  Node *rnode;

  

  if(SIsEmpty(pstack)){

  printf("Stack Memory Error!");

  exit(-1);

}

 

rdata = pstack->head->data;  //삭제할 노드의 데이터를 임시로 저장

rnode= pstack->head;  //삭제할 노드의 주소 값을 임시로 저장

 

pstack->head= pstack->head->next;  //삭제할 노드의 다음 노드를 head가 가리킴

free(rnode);  //노드 삭제

return rdata;   //삭제된 노드의 데이터 반환

}

 

마지막으로 SPeek함수를 구현하자

Data SPeek(Stack *pstack)

{
  if(SIsempty(pstack)){

   printf("Stack Memory Error!");

   exit(-1);

  }

 

  return pstack->head->data;   //head가 가리키는 노드에 저장된 데이터 변환

}

 

이로써 연결리스트 기반의 스택도 완성하였다. 이제 함수를 소스파일로 묶어 구현해보자.

 

//ListBaseStack.c
#include <stdio.h>
#include <stdlib.h>
#include "ListBaseStack.h"

void StackInit(Stack *pstack)
{
	pstack->head =NULL;
}

int SIsEmpty(Stack *pstack)
{
	if(pstack->head==NULL)
    	return TRUE;
   	else
    	return FALSE;
}

void SPush(Stack *pstack, Data data)
{
	Node *newNode= (Node*)malloc(sizeof(Node));
    
    newNode->data =data;
    newNode->next= pstack->head;
    
    pstack->head =newNode;
}

Data SPop(Stack *pstack)
{
	Data rdata;
    Node *rnode;
    
    if(SIsEmpty(pstack)){
    	printf("Stack Memory Error!");
        exit(-1);
  	}
    
    rdata = pstack->head->data;
    rnode = pstack->head;
    
    pstack->head= pstack->head->next;
    free(rnode);
    
    return rdata;
}

Data SPeek(Stack *pstack)
{
	if(SIsempty(pstack)){
    	printf("Stack Memory Error!");
        exit(-1);
    }
    
    return pstack->head->data;
}

//LishBaseStackMain.c
#include <stdio.h>
#include "ListBaseStack.h"

int main()
{
	//Stack의 생성 및 초기화
    Stack stack;
    StackInit(&stack);
    
    //데이터 넣기
    SPush(&stack, 1); SPush(&stack, 2);
    SPush(&stack, 3); SPush(&stack, 4);
    SPush(&stack, 5);
    
    //데이터 꺼내기
    while(!SIsEmpty(&stack))
    	printf("%d ", SPop(&stack));
        
  	return 0;
}
===========================실행 결과===============================
5 4 3 2 1