스택(STACK) _ C언어

스택

---

• 마지막에 들어온 것이 먼저 나가는 LIFO ( LAST IN FIRST OUT ) 구조를 가진 자료구조
• 한쪽 끝으로만 자료의 삽입/삭제가 이루어지는 선형자료구조
  
  

  

  출처_https://lee-mandu.tistory.com/462

• 배열 또는 링크드 리스트로 구현 할 수 있음
  검색이 많은 경우 배열로 , 변경 & 등록이 많으면 링크드 리스트로 구현하는 것이 용이 
  ( 배열은 메모리 연속 공간에 데이터 저장 = 검색은 빠르지만 변경 시 느릴 수 있음 )
  ( 링크드 리스트는 메모리 주소만 변경하면 되므로 등록, 수정에는 빠름 , 검색에는 느릴 수 있음 )
  
  
  

출처_https://dev.to/theoutlander/implementing-the-stack-data-structure-in-javascript-4164

•  스택은 최근에 참조된 자료가 다시 참조될 확률을 의미하는 시간지역성을 최고로 활용할 수 있는 자료구조
  
  

스택 사용법

* 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고 TOP으로 정해진 곳을 통해서만 접근 가능

* 정의된 용어들을 무조건 아래와 같이 사용해야하는 법은 없으나 가독성을 위해 아래와 같이 사용하는 것을 추천

---

1.  삽입 ( PUSH ) 
   - 스택에 새로운 자료를 추가하는 연산
   - 스택의 구조상 마지막 데이터 위치에 삽입 
   - 마지막 위치를 표시하는 TOP이라는 변수에 +1 ( TOP의 초기치는 -1 )
   - 스택의 크기는 스택이 저장할 수 있는 크기를 의미&  스택 사이즈보다 더 많은 데이터가 들어오면 OVERFLOW 발생
   - 시간복잡도 O(1)
   
   
2.  삭제 ( POP )
   - 스택에서 제거하는 연산을 의미 
   - 마지막 위치를 표시하는 TOP이라는 변수에 -1
   - 시간복잡도 O(1)
   
   
3. 읽기 ( PEEK ) 
   - 마지막 위치 TOP에 해당하는 데이터를 읽는 연산을 의미
   - 시간복잡도 O(1)
   
   
4. 비어있는지 확인 ( ISEMPTY )
   - 스택이 비어있는지를 확인
5. 스택 크기 ( SIZE / LEVEL)
   - 스택의 크기를 의미
   - 배열 구현의 경우 시간복잡도 O(1), 리스트의 경우 O(n)

스택 구현 코드 예시

//C언어 _ 스택(배열)예시 코드

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct ArrayStackNodeType{ // 배열 내 데이터 구조
    int data;
}ArrayStackNode;


typedef struct ArrayStructType{ //배열 스택의 구조
    int maxCount;
    int top;
    ArrayStackNode *pData; //저장된 자료를 위한 포인터
}ArrayStack;


ArrayStack* createArrayStack(int size){ //스택 생성, size는 스택 크기
    ArrayStack *pReturn = NULL;
    pReturn =(ArrayStack*) malloc(sizeof(ArrayStack));//메모리 할당
    memset(pReturn, 0, sizeof(ArrayStack));//메모리 초기화
    pReturn->maxCount = size; // 최대 자료 개수 설정

    // 스택 내 배열 생성
    pReturn-> pData = (ArrayStackNode*)malloc(sizeof(ArrayStackNode)*size);
    memset(pReturn->pData, 0, sizeof(ArrayStackNode)*size);
    
    pReturn->top = -1; //top의 초기값은 -1

    return pReturn;
}    

//스택 내 데이터가 다 찼는지 검사
int isArrayStackFull(ArrayStack* pStack){ //스택이 꽉 차 있으면 1리턴 아닌 경우는 0리턴
    int ret = 0;

    if(pStack != NULL){ //스택이 비어있지 않으면
        if(pStack->top == pStack->maxCount-1){
            ret = 1;
        }
    }
    return ret;
}

//스택 내 데이터가 비었는지 확인하는 연산
int isArrayStackEmpty(ArrayStack* pStack){ //비어 있으면 1, 비어있지 않으면 0 리턴 (스택 자체가 없어도 1)
    int ret = 0;
    if(pStack != NULL){ 
        if(pStack->top ==-1){
            ret = 1;
        }
    }
    return ret;
}

//스택에 데이터 추가 (push)
int pushStack(ArrayStack* pStack, int data){ // 데이터 추가 실패 시 0 리턴, 성공 시 1 리턴
    int ret = 0;
    if(pStack ==NULL){
        printf("스택이 존재하지 않습니다.\n");
        return 0;
    }

    if(isArrayStackFull(pStack)==0 ){ //아직 스텍에 넣을 공간이 있음
        pStack->pData[++(pStack->top)].data =data;
        // printf("%d %d\n",pStack->top,pStack->pData[pStack->top]);
        ret = 1;
    }else{
        printf("스택이 가득 찼습니다. \n");
    }
    return ret;
}


//스택에 데이터 삭제(pop)
ArrayStackNode* popStack(ArrayStack* pStack){ //삭제 후 삭제한 내용을 반환하게 (반환하지 않아도 됨)
    ArrayStackNode * pReturn = NULL;
    if(isArrayStackEmpty(pStack)==0 && pStack != NULL){
        pReturn = (ArrayStackNode*)malloc(sizeof(ArrayStackNode));
        if(pReturn != NULL){
            pReturn->data=pStack->pData[pStack->top].data;
            pStack-> top --;
        }else{
            printf("오류, 메모리 오류 \n");
        }
    }else{
        printf("스택에 데이터가 없거나 스택이 존재하지 않습니다. \n");
    }
    return pReturn;
}

//스택에 top에 있는 데이터 가져오기 ( peek )
ArrayStackNode* peekStack(ArrayStack* pStack)
{
	ArrayStackNode* pReturn = NULL;
	if (pStack != NULL) {
		if (isArrayStackEmpty(pStack) == 0) {
			pReturn = &(pStack->pData[pStack->top]);
		}else{
            printf("스택 내 데이터가 없습니다.\n");
        }
	}else{
        printf("스택이 존재하지 않습니다. \n");
    }

	return pReturn;
}


//스택 자체를 삭제하는 연산
void deleteArrayStack(ArrayStack* pStack){
    if(pStack != NULL){ //삭제할 스택이 있는지 없는지
        if(pStack-> pData !=NULL){
            free(pStack->pData);
        }
        free(pStack);
        printf("스택이 삭제되었습니다.\n");
    }else{
        printf("스택이 존재하지 않습니다.\n");
    }
}

int main(int argc, char *argv[]) {

    ArrayStack* myStack = createArrayStack(5);
    ArrayStackNode* myReturn = NULL;
    pushStack(myStack, 10);
    pushStack(myStack, 20);
    pushStack(myStack, 30);
    
    myReturn =popStack(myStack);
    if(myReturn!=NULL){
    printf("%d가 삭제되었습니다\n", myReturn->data);
    }

    myReturn=NULL;
    myReturn =popStack(myStack);
    if(myReturn!=NULL){
    printf("%d가 삭제되었습니다\n", myReturn->data);
    }

    myReturn=NULL;
    myReturn =peekStack(myStack);
    if(myReturn!=NULL){
        printf("스택의 마지막 값은 %d\n", myReturn->data);
    }
    
    deleteArrayStack(myStack);
    return 0;
}

 

스택의 활용 예시

---

• 웹 브라우저 방문기록 ( 뒤로가기 ) : 가장 나중에 열린 페이지부터 보여줌
• 역순 문자열 나열 : 가장 나중에 입력된 문자부터 출력
• 실행 취소 : 가장 나중에 실행된 것부터 실행 취소
• 후위 표기법 계산 : 피연산자를 먼저 표시하고 연산자를 나중에 표시하는 방법
                           컴파일러가 사용하는 것으로 스택을 사용하는 예들 중 가장 빈번하게 등장
• 수식의 괄호 검사 : 연산자 우선순위 표현을 위한 괄호 검사