[자료구조] 스택(Stack) 실습 (feat. 배열)

 

스택(Stack)

배열을 기반으로 하는 스택 구현은 자료구조 중 매우 쉬운편이다! 홧팅

스택의 개념이 궁금하다면?

[자료구조] 스택(Stack)

 

배열 기반 Stack 소스 코드

---

📌ArrayBaseStack.h

//출처 : 윤성우의 열혈 자료구조
//ArrayBaseStack.h
#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);			//스택의 init연산(초기화)
int SIsEmpty(Stack * pstack);			//스택의 isEmpty연산(비었는지 확인)
void SPush(Stack * pstack, Data data);		//스택의 push 연산(추가)
Data SPop(Stack * pstack);			//스택의 pop 연산(제거)
Data Speek(Stack * pstack);			//스택의 peek 연산(topIndex 반환)

#endif

 

📌ArrayBaseStack.c

//출처 : 윤성우의 열혈 자료구조
//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){
  pstack->topIndex += 1;
  pstack->stackArr[pstack->topIndex] = data;
}

Data SPop(Stack * pstack){
  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

//출처 : 윤성우의 열혈 자료구조
//ArrayBaseStackMain.c
#include <stdio.h>
#include "ArrayBaseStack.h"

int main(void){

  // 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;
}

 

 

 

배열 기반 Stack 설명

---

📌스택 초기화(init)

int StackInit(Stack * pstack){
  pstack->topIndex = -1;		//topIndex의 -1은 빈 상태를 의미한다.
}

가장 먼저 해야할 초기화 작업은 간단하게 "마지막에 저장된 데이터의 위치를 가리키는 topIndex"만 해주면 된다.

topIndex = -1이 되어야 스택이 비게 된다.

topIndex에 0을 저장하면 배열 인덱스 0에 데이터가 저장됨을 의미하기 때문에 0이 아닌 -1로 초기화 해야 한다.

 

📌스택이 비어있는지 확인(IsEmpty)

int SIsEmpty(Stack * pstack){
  if(pstack->topIndex == -1)	//스택이 비어있다면
    return TRUE;
  else
    return FALSE;
}

topIndex가 -1이면 스택이 비어있다는 의미이니 TRUE를 반환하고 그게 아니면 FALSE를 반환한다.

 

📌스택에 값 넣기 및 빼기(push & pop)

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];	//삭제되는 데이터 반환
}

스택에 값을 넣거나 뺄 때 PUSH와 POP함수를 사용한다. 자세한 설명은 아래 그림 참고!

스택에 데이터를 넣는 PUSH 연산이 실행되면

⭐push() : 데이터를 추가할 때마다 topIndex를 1씩 늘려준다.

 

스택의 데이터를 꺼내는 POP 연산이 실행되면

⭐pop() : 데이터를 삭제할 때마다 topIndex를 1씩 감소시킨다.

 

📌맨 위 데이터 반환(peek)

Data SPeek(Stack * pstack){		//peek 연산 담당 함수
  if(SIsEmpty(pstack)){
    printf("Stack Memory Error!");
    exit(-1);
  }
  
  return pstack->stackArr[pstack->topIndex];	//맨 위에 저장된 데이터 반환
}

프로그램을 구현하다 보면 스택이 반환할 다음 데이터를 확인할 필요가 간혹 있다. 그때마다 pop 함수를 호출하면 데이터를 확인할 수 있지만 확인과 동시에 소멸이 되니 "확인은 하되 소멸시키지 않는 함수"가 필요하다. 그 역할이 바로 peek 함수이다. 

 

References

📚 윤성우의 열혈 자료구조 : C언어를 이용한 자료구조 학습서

http://www.kyobobook.co.kr/product/detailViewKor.laf?mallGb=KOR&ejkGb=KOR&barcode=9788996094067 

윤성우의 열혈 자료구조 - 교보문고