스택(stack)은 "쌓아놓은 더미"란 뜻을 갖는 제한적으로 접근할 수 있는 자료구조이다.

접근 방법이 제한적인 이유는 삽입, 검색, 삭제를 위한 접근이 항상 목록의 끝에서만 일어나기 때문이다.

스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 후입선출(LIFO - Last In First Out) 선형구조이다.

자료를 추가하는 것을 push 라고 하고 자료를 삭제하는 것을 pop 이라고 하는데,

이때 삭제되는 자료는 가장 최근에 push한 자료부터 제거된다. * 참고 문제 : 1102 : 스택 (stack)

<그림출처 : wiki>

stk를 스택, data를 스택에 저장된 원소(element)라고 할 때,

스택에 다음과 같은 연산을 정의할 수 있다.

다음 연산은 STL-Stack 을 참고한 것이다.

1. empty() : 스택이 비었다면 1(true)을 그렇지 않다면 0(false)을 반환한다.

2. size() : 스택에 담긴 원소의 개수를 반환한다.

3. top() : 최근 스택에 담긴 원소를 반환한다. 반환된 원소는 삭제되지 않는다.

4. push(data) : 스택에 data를 추가한다.

5. pop() : 최근 스택에 추가한 원소를 삭제한다. 삭제할 원소가 없는 경우 아무일도 하지 않는다.

아래 프로그램은 스택자료구조를 링크드 리스트로 구현한 것이다.

main.cpp와 user.cpp를 분석하고 user.cpp의 각 함수를 완성하시오.

/// === user.cpp ===
 
#ifndef NULL
#define NULL 0
#endif
const int SIZE = 100010;
struct Node{
    int num;
    Node* next;
}buf[SIZE];
int bcnt;
 
struct Stack{
    Node*head;
    int cnt;
}stkObject;
 
Stack* newStack(){
 
}
 
void delStack(Stack*stk){
 
}
 
bool empty(Stack*stk){
 
}
 
int size(Stack*stk){
 
}
 
int top(Stack*stk){
 
}
 
void push(Stack*stk, int num){
 
}
 
void pop(Stack*stk){
 
}
 
 
 
/// === main.cpp ===
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
typedef struct Node Node;
typedef struct Stack Stack;
 
extern Stack* newStack();
extern void delStack(Stack*stk);
 
extern bool empty(Stack*stk);
extern int size(Stack*stk);
extern int top(Stack*stk);
extern void push(Stack*stk, int);
extern void pop(Stack*stk);
 
 
int main(){
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
 
    setbuf(stdout, NULL);
 
    Stack* stk = newStack();
    int N;
    char cmd[10];
    int num, i;
    scanf("%d", &N);
    for(i=0;i<N;++i){
        scanf("%s", cmd);
        if(cmd[0] == 'e'){             /// 1. empty
            printf("%d\n", empty(stk));
        }
        else if(cmd[0] == 's'){        /// 2. size
            int ret = size(stk);
            printf("%d\n", ret);
        }
        else if(cmd[0] == 't'){        /// 3. top
            if(empty(stk)){
                puts("except!");
            }
            else{
                printf("%d\n", top(stk));
            }
        }
        else {
            if(cmd[1] == 'u'){         /// 4. push
                scanf("%d", &num);
                push(stk, num);
            }
            else{                      /// 5. pop
                pop(stk);
            }
        }
    }
 
    delStack(stk);
    return 0;
}

#3690 upload 1083 done 737 how_to_reg 508 component_exchange Interactive

stack api timer 2s memory 256MB

#3690
Interactive

stack api 2s 256MB