[자료구조] 스택(Stack)

후입선출(LIFO : Last-In First-Out)

가장 최근에 들어온 데이터가 가장 먼저 나가는 것.

각티슈에서 가장 위에 있는 것부터 뽑아 쓰는 것처럼!

입력과 출력이 역순으로 필요한 경우 사용한다. (ex. undo, 함수 호출 스택)

연산

init(stack) : 스택을 초기화한다.

create() : 스택을 생성한다.

push(stack, data) : 데이터를 스택 가장 위에 삽입한다.

pop(stack) : 스택 가장 위의 데이터를 삭제한다.

is_empty(stack) : 스택이 비어있는지 검사한다.

is_full(stack) : 스택이 가득 찼는지 검사한다.

peek(stack) : 스택의 맨 위에 있는 요소를 삭제하지 않고 반환한다.

 

배열을 이용한 스택

#include <iostream>

#define MAX_STACK_SIZE 3

typedef int element;
typedef struct{
    element stack[MAX_STACK_SIZE];
    int top;
}Stack;

void init(Stack *stack){
    stack->top = -1;
}

bool is_empty(Stack *stack){
    return stack->top == -1;
}

bool is_full(Stack *stack){
    return stack->top == MAX_STACK_SIZE-1;
}
void push(Stack *stack, element data){
    if(is_full(stack)){
        std::cerr << "Stack is Full\n";
        exit(-1);
    }
    stack->stack[++stack->top] = data;
}
element pop(Stack *stack){
    if(is_empty(stack)){
        std::cerr << "Stack is Empty\n";
        exit(-1);
    }
    return stack->stack[stack->top--];
}

element peek(Stack *stack){
    if(is_empty(stack)){
        std::cerr << "Stack is Empty\n";
        exit(-1);
    }
    return stack->stack[stack->top];
}

int main(){
    Stack stack;
    
    init(&stack);
    push(&stack, 1);
    push(&stack, 2);
    push(&stack, 3);

    std::cout << is_full(&stack) << "\n";	// 1
    std::cout << pop(&stack) << "\n";		// 3
    std::cout << pop(&stack) << "\n";		// 2
    std::cout << peek(&stack) << "\n";		// 1
    std::cout << pop(&stack) << "\n";		// 1
    std::cout << is_empty(&stack) << "\n";	// 1
}

연결리스트를 이용한 스택

#include <iostream>

typedef int element;
typedef struct StackNode{
    element data;
    StackNode * link;
}StackNode;

typedef struct linkedStack{
    StackNode * top;
}linkedStack;

void init(linkedStack *stack){    
    stack->top = nullptr;
}

bool is_empty(linkedStack *stack){
    return stack->top == nullptr;
}

void push(linkedStack *stack, element data){
    StackNode *temp = (StackNode *)malloc(sizeof(StackNode));

    if(temp == nullptr){
        std::cerr << "Memory Allocation Error\n";
        return;
    }
    temp->data = data;
    temp->link = stack->top;
    stack->top = temp;
}
element pop(linkedStack *stack){
    if(is_empty(stack)){
        std::cerr << "Stack is Empty\n";
        exit(-1);
    }
    StackNode *temp = stack->top;
    stack->top = stack->top->link;

    element data = temp->data;
    free(temp);
    return data;
}

element peek(linkedStack *stack){
    if(is_empty(stack)){
        std::cerr << "Stack is Empty\n";
        exit(-1);
    }
    return stack->top->data;
}

int main(){
    linkedStack stack;
    
    init(&stack);
    push(&stack, 1);
    push(&stack, 2);
    push(&stack, 3);

    std::cout << pop(&stack) << "\n";		// 3
    std::cout << pop(&stack) << "\n";		// 2
    std::cout << peek(&stack) << "\n";		// 1
    std::cout << pop(&stack) << "\n";		// 1
    std::cout << is_empty(&stack) << "\n";	// 1
}