개념/자료구조

Stack (Array, Linked list 구현)

웅드 2023. 11. 28. 20:20
  • 스택은 쌓는다는 의미로 데이터를 차곡차곡 쌓아 올린 형태의 자료구조이다.
  • LIFO ( Last In First Out ) - 후입 선출의 구조
  • stack에서 삽입 연산은 push
  • stack에서 삭제 연산은 pop

배열로 구현하는 방법 : ArrayStack

  • 데이터 집합을 배열에 저장한다.
  • 스택의 크기를 고정시킬 수 있다.
  • 배열과 Top의 위치를 저장하는 멤버가 필요하다.

 

리스트로 구현하는 방법 : ListStack

  • 데이터 집합을 Linked list에 저장한다.
  • Linked list 특성상 스택 크기가 자유롭다.
  • 스택의 크기를 동적으로 할당할 수 있다.

 

스택의 활용

  • 함수 호출 관리
    • 호출 될때마다 스택에 호출된 함수의 정보가 push되고, 함수가 반환될 때 pop한다.
  • 수식 평가
    • 후위 표기법 수식을 평가할 때 스택을 사용하여 연산자와 피연산자를 관리한다.
  • 웹 브라우저의 뒤로가기
    • 방문한 웹 페이지의 주소가 스택에 저장되어 뒤로가기를 누를 때마다 pop되어 이전 페이지로 이동한다.

스택 ADT ( 추상 데이터 타입 )

  • init() : 스택을 초기화
  • create() : 스택 생성
  • is_empty(s) : 스택이 비어있는지 검사
  • is_full(s) : 스택이 가득 찼는지 검사
  • push(e) : 스택의 맨 위에 요소 e를 추가
  • pop(s) : 스택의 맨 위 요소를 삭제
  • peek(s) : 스택의 맨 위 요소를 삭제하지 않고 반환

스택의 연산

  • top() : 스택 맨 위에 있는 데이터 값 반환
  • push() : 스택에 데이터 삽입
  • pop() : 스택에서 데이터 삭제하여 반환
  • isempty() : 스택에 원소가 없으면 "True", 있으면 "False" 값 반환
  • isfull() : 스택에 원소가 없으면 "False", 있으면 "True" 값 반환

스택의 정적 구현 : 1차원 배열 사용

#define MAX_STACK_SIZE 100
//1차원 배열의 사용
int stack[MAX_STACK_SIZE];
//top의 초기 값은 스택이 비어있을 때 -1 이다.
int top = -1;

//스택의 삽입
void push(int item){

    if(top>= MAX_STACK_SIZE -1){
    	stack_full();
        return;
    }
    stack[++top] = item;
    //top++;
    //stack[top] = item;
}

//push(x)
if is_full(S) then error "overflow"
else top <- top + 1
    data[top] <- x

//스택의 삭제
int pop(){

    if(top == -1) return stack_empty();
    
    return stack[top--];
}

//pop()
if is_empty() then error "underflow"
else e <- data[top]
    top <- top-1
    return e;
    
//스택의 검사
int isempty(){ // 스택이 비어있는지 검사

    if(top < 0) return 1;
    else return 0;
}

int isfull(){ // 스택이 가득 차있는지 검사

    if(top >= MAX_STACK_SIZE -1) return 1;
    else return 0;
}

 

스택의 동적 구현 : Linked list 사용

 

장점 : 크기에 제한이 없다.

단점: 구현이 복잡, 삽입/삭제 시간이 오래 걸린다.

//스택의 생성

//요소의 타입
typedef int element;

typedef struct StackNode{

    //노드의 타입
    element item;
    struct StackNode *link;
} StackNode; 

//연결된 스택 관련 데이터
typedef struct{
    StackNode *top;
} LinkedStackType;

//스택의 삽입
element pop(LinkedStackType *s){

    if( is_Empty(s) ){
        cout << "스택이 비어있음" << endl;
    }
    else{
        Node *temp = (Node *)malloc(sizeof(Node));// 동적 노드 생성
        temp -> data = item; //새로운 노드에 입력할 값 복사
        temp -> link = s-> top // 새로운 노드가 기존의 top 노드를 가르키도록 함
        s-> top = temp // temp 노드가 top 노드로 선언
    }
}

//스택의 삭제
element pop(LinkedStackType *s){

    if( is_empty(s) ){
        cout << "스택이 비어있다." << endl;
    }
    else{
    	StackNode *temp = s -> top; //temp 포인터가 top node를 가르키도록 한다.
        int item = temp -> item; // 삭제할 값을 반환하기 위해 기존의 데이터를 item에 저장
        s -> top = s -> top -> link; // top node는 기존의 top 노드가 가르키는 노드가 된다.
        free(temp); // 동적 메모리 해제
        return item; // 삭제한 값 반환
    }
}
반응형