[자료구조](5)[스택]

스택

스택: LIFO방식의 자료구조
먼저 들어온 것이 나중에 나간다

스택의 쓰임
ctrl+z
수식의 valid 평가 (괄호 판별)
함수 호출 관리

스택 ADT

• 데이터 <element, next_pointer>
  스택도 연결 리스트의 일종
• top: 스택의 맨 끝을 가리키는 포인터
• 연산
  push(): 스택의 맨 위에 데이터 넣기
  pop(): 스택의 맨 위에 있는 데이터 가져오고 스택에서 삭제
  peek(): 스택의 맨 위에 있는 데이터 가져오기만 하기
  isFull(): 스택이 가득 찼는지 확인 <- 연결 리스트면 굳이?
  isEmpty(): 스택이 비었는지 확인 <- 연결 리스트면 굳이?

 

배열로 만든 스택

기본 골조는 다음과 같다.

const int MAX_SIZE = 5;
int stack[MAX_SIZE];
int top = -1; //스택이 비어있다는 뜻

isEmpty, isFull

bool isEmpty(int &top){
    if (top == -1){return true;}
    else {return false;}
}

bool isFull(int &top){
    if (top == MAX_SIZE-1){return true;}
    else {return false;}
}

push

void push(int value){
    if (isFull(top) == true)
        return;
    else{
        top += 1;
        stack[top] = value;
    }
}

peek

int peek(int &top){
    if (isEmpty(top) == true)
        return 0;
    else{
        int value = stack[top];
        return value;
    }
}

pop

int pop(int &top){
    if (isEmpty(top) == true)
        return 0;
    else{
        int value = stack[top];
        top -= 1;
        return value;
    }
}

 

연결 리스트로 만든 스택

연결리스트에서 자료 삽입, 삭제에 제한이 생김 -> 특정 분야에서 더 효율적

일단 골조는 연결 리스트와 같다.
□ <- □ <- □ <- □
                      ↑ top

typedef struct node {
    int data; //int형 데이터 담음
    struct node* next; //node를 가리키는 포인터 선언
} Node;

Node* makeNode(int data){
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;  
    return newNode;
}

push

연결리스트의 맨 끝에 넣어주면 된다.

Node* push(int data, Node** top){
    Node* newNode = makeNode(data);
    newNode->next = *top;
    *top = newNode;
}

peek

top으로 접근하면 된다.

int peek(Node** top) {
    if (*top == NULL) {
        printf("Stack is empty!\n");
        return -1;
    }
    return (*top)->data;  
}

pop

peek과 비슷하나 스택에서 지우는 역할까지

int pop(Node** top) {
    if (*top == NULL) {
        printf("Stack is empty!\n");
        return -1;
    }
    int value = (*top)->data;
    Node* temp = *top;
    *top = temp->next; 
    free(temp); //할당한 다음 무조건 free!!
    return value;
}