[C] 자료구조 스택(stack)

자료구조 중 하나인 스택(stack)에 대한 설명 + c로 구현한 스택 코드에 대한 정리

 

■ 스택(stack)

데이터를 아래에서부터 위로 쌓아 올리는 자료구조
후입 선출(LIFO  :Last-In First Out)

객체 : n개의 요소들의 순서 있는 모임

연산 :

Create  ::= 스택 생성

Empty(s)  ::= 비어 있는지 검사

Full(s)  ::= 가득 차 있는지 검사

Push(s,e) ::= 맨 위에 요소 e 추가

Pop(s)  ::= 맨 위의 요소 삭제

■ 삽입, 삭제 연산

■ 배열로 구현한 큐

• 구조체 선언 및 초기화

typedef int element;
#define MAX_STACK_SIZE100

typedef struct _arraystack {
  element Stack[MAX_STACK_SIZE];
  int nTop;   //
}ArrayStack;

void Init(ArrayStack *pStack)
{
  pStack->nTop = -1; 
// 데이터 없을 경우  Top = -1
}

• Empty, Full

int Empty(ArrayStack *pStack)
{
   if (pStack->nTop == -1) return 1;
   // 스택이 비었는지 검사
   else return 0;
}

int Full(ArrayStack* pStack)
{
    if (pStack->nTop == (MAX_STACK_SIZE-1))
         return 1;// 스택이 가득 차 있는지 검사
    else return 0;
}

• Push

void Push(ArrayStack *pStack, element EData)
{
    if (Full(pStack) == 1) {
       fprintf(stderr, "스택 포화\n");
       return;
    }
    else {
      pStack->nTop++;// Top 증가
      pStack->Stack[pStack->nTop] =  EData;
      // Top에 데이터 저장
     }
}

• Pop

element Pop(ArrayStack *pStack)
{
    if (Empty(pStack) == 1) {
       fprintf(stderr, "스택 공백\n");
       exit(1);
    }
    else {
       return pStack->Stack[(pStack->nTop)--];
    }
}

■ 연결리스트로 구현한 큐

• 노드 정의 및 초기화

typedef int element;

typedef struct _stacknode {
   element EData;
   struct _stacknode *link;
}StackNode;

typedef struct {
   StackNode *top;
}StackType;

void Init(StackType *pStack)
{
   pStack->top = NULL;  // 초기화
}

• Empty

int Empty(StackType *pStack)
{
   return (pStack->top == NULL);
}

• Push

void Push(StackType *pStack, element EData)
{
    StackNode *pNew = NULL;
    pNew = (StackNode *)malloc(sizeof(StackNode))      // 삽입 공간 할당
    if (pNew == NULL) {
        fprintf(stderr, "메모리 할당 에러\n");	
    }
    else {
        pNew->EData = EData;        // 삽입 데이터 저장
        pNew->link = pStack->top;  // 삽입 링크는 TOP이 됨
        pStack->top = pNew;	         // 삽입 노드가 TOP이 됨
    }
}

• Pop

element Pop(StackType *pStack)
{
    StackNode *pRemove = NULL;
    element EData = 0;

    if (Empty(pStack)) {
      fprintf(stderr, "스택이 비어 잇음\n");
      exit(1);
    }
    else {
      pRemove = pStack->top;                     // TOP노드 제거
      EData = pRemove->EData;                  // 삭제 데이터 저장
      pStack->top = pStack->top->link;       // TOP의 링크가 가리키던 값을 TOP으로 함
      free(pRemove);	                       // 메모리 반환

      return EData;
    }
}