Stack

Stacks이란?

Stack은 자료를 차곡차곡 쌓는 구조로 LIFO(Last In, First Out) 구조를 가진다. Linked list도 있는데 stack을 쓰는 이유는 함수 호출 순서를 저장할 때와 같이 LIFO 구조가 유리한 경우가 존재하기 때문이다.

Stack의 usage(활용)

Stack이 LIFO 구조를 따르기 때문에 가장 나중에 넣은 것을 먼저 꺼내야 하는 상황에서 유용하다.

• Undo operation (되돌리기 기능): 텍스트 편집기에서 Ctrl+Z와 같이 사용자가 수행한 작업을 stack에 저장해두고 되돌릴 때는 가장 최근 작업부터 순서대로 복원한다.
• Expression evaluation (수식 계산): 계산 중간값이나 연산자를 stack에 쌓아두고 적절한 시점에 pop하여 계산을 수행한다. 괄호나 연산 순서를 처리하는 데 유용한다.
• Function call management (함수 호출 관리): 재귀 함수나 프로그램의 call stack에서 함수 호출 시 상태를 저장하고, 함수가 끝나면 가장 마지막에 호출된 함수부터 복귀한다.

 

Stack 구현: array 기반

전역 변수 선언

#define MAX_SIZE 100

int stack[MAX_SIZE];
int top = -1;  // 스택의 가장 윗부분 인덱스를 가리킴

array를 통해 stack을 구현할 것이다. 따라서 stack은 array로 top은 현재 스택의 상태를 추적하기 위한 index로 전역 변수로 선언해준다.

Stack이 비었는지 확인하는 함수

int isEmpty() {
    return top == -1;
}

top이 가장 맨 위에 존재하는지만 확인해주면 된다.

Stack이 가득 찼는지 확인하는 함수

int isFull() {
    return top == MAX_SIZE - 1;
}

top의 위치가 array의 마지막 index인 MAX_SIZE-1에 도달하면 stack은 가득 차있게 된다.

peek: stack의 가장 위 요소를 확인 (삭제X)

int peek() {
    if (isEmpty()) {
        printf("스택이 비어 있습니다.\n");
        return -1;
    }
    return stack[top];
}

push: stack에 추가

void push(int value){
	if(isFULL()){
    	printf("스택이 가득 찼습니다.");
        return;
    }
    
    top++;
    stack[top] = value;
}

pop: 스택에서 제거

int pop(){
	if(isEmpty()){
    	printf("스택이 비었습니다.");
        return;
    }
    
    return stack[top--];

 

Stack 구현: linked list 기반

전역 변수 선언

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

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* top = NULL;

마찬가지로 top 포인터는 stack의 맨 위 노드를 가리킨다.

push: 스택에 데이터 추가

void push(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("메모리 할당 실패\n");
        return;
    }
    newNode->data = value;
    newNode->next = top;
    top = newNode;
}

pop: 스택에서 데이터 제거

int pop() {
    if (isEmpty()) {
        printf("스택이 비어 있습니다.\n");
        return -1;
    }
    Node* temp = top;
    int poppedValue = temp->data;
    top = top->next;
    free(temp);
    return poppedValue;
}

peek: 스택 맨 위 요소 확인

int peek() {
    if (isEmpty()) {
        printf("스택이 비어 있습니다.\n");
        return -1;
    }
    return top->data;
}

Bracket sequence 검사

Bracket이 나열된 순서를 보며 그 순서가 valid한 것인지를 판단하는 작업이다. 순서는 다음과 같다.

1. '(', '{', '['가 보이면 stack에 push한다.
2. ')', '}', ']'를 만났을 때 stack에 저장된 문자와 쌍을 이룬다면 valid, 하나라도 걸리면 invalid를 출력한다.
3. 모든 문자열에 대하여 반복한다.

// 유효한 괄호 시퀀스인지 검사하는 함수
int isValidBracketSequence(const char* str) {
    for (int i = 0; str[i] != '\0'; i++) {
        char ch = str[i];
        
        if (ch == '(' || ch == '[' || ch == '{') {
            push(ch);
        } else if (ch == ')' || ch == ']' || ch == '}') {
            char topChar = pop();
            if ((ch == ')' && topChar != '(') ||
                (ch == ']' && topChar != '[') ||
                (ch == '}' && topChar != '{')) {
                return 0;  // 유효하지 않음
            }
        }
    }
    return top == -1;  // 스택이 비어 있어야 유효함
}