삼성전자 알고리즘/정올
1. 1102 스택 (stack)
기명준
2019. 5. 9. 22:07
문제 출처 : http://bitly.kr/cA7kzH
정올::Xpert
Stack은 "더미"란 뜻을 가진다. 책 더미, 신문 더미 등에 사용하는 단어이다. 책 더미를 예로 들어 보자. 책 더미를 쌓았다고 했을 때, 이 책 더미에서 책을 가져오는 가장 정상적인 방법은 제일 위에 있는 책을 가져오는 방식이다. 다시 말하면 가장 먼저 들어간 책은 가장 나중에 꺼낼 수 있을 것이다. 이런식으로 자료가 가장 밑에 쌓이고(입력). 자료를 가져올 때(출력)는 가장 위(최근)의 자료를 가져오는 자료구조를 Stack하고 한다. 이러한
www.jungol.co.kr
/**************************************************************
Problem: 1102
User: hbrojun.kim
Language: C++
Result: Success
Time:1 ms
Memory:1740 kb
****************************************************************/
#include <iostream>
using namespace std;
//배열로 구현 http://ehpub.co.kr/c%ec%96%b8%ec%96%b4-%ec%86%8c%ec%8a%a4-%ec%8a%a4%ed%83%9d-%eb%b2%84%ed%8d%bc%ed%81%ac%ea%b8%b0-%ea%b3%a0%ec%a0%95/
#define STACK_SIZE 100
typedef struct stackArray{
int buf[STACK_SIZE];
int stack_size;
}StackArray;
void InitStackArray(StackArray* stack){
stack->stack_size = -1;
}
int IsFullStackArray(StackArray* stack){
return (stack->stack_size+1) == STACK_SIZE;
}
int IsEmptyStackArray(StackArray* stack){
return stack->stack_size == -1;
}
void PushNodeStackArray(StackArray* stack, int data){
if (IsFullStackArray(stack)){
printf("Stack array is full\n");
return;
}
stack->stack_size++;
stack->buf[stack->stack_size] = data; // 데이터보관
}
void PopNodeStackArray(StackArray *stack){
if (IsEmptyStackArray(stack)){
printf("Stack Array is empty.\n");
return;
}
printf("Pop : %d\n", stack->buf[stack->stack_size]);
stack->stack_size--;
}
//포인터로 구현 https://huiyu.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Stack%EC%8A%A4%ED%83%9D-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0
//http://ehpub.co.kr/c%EC%96%B8%EC%96%B4-%EC%86%8C%EC%8A%A4-%EC%8A%A4%ED%83%9D%EC%9D%84-%EC%97%B0%EA%B2%B0%EB%A6%AC%EC%8A%A4%ED%8A%B8%EB%A1%9C-%EA%B5%AC%ED%98%84/
typedef struct node{
int data;
node* prevNode;
}Node;
typedef struct stack{
int size;
Node* top;
}Stack;
//초기화
void Init(Stack* s){
s = new Stack();
s->top = nullptr;
s->size = 0;
}
//push
void PushNode(Stack* stack, int data){
//새로운 노드 생성해준 뒤 그 노드를 top 노드로 이은다.
Node* newNode = new Node();
newNode->data = data; //데이터 설정
newNode->prevNode = stack->top; //새로운 노드의 이전 값은 기존 스택의 top값이 됨.
stack->top = newNode; //새로운 노드가 stack의 top이 됨.
stack->size++;
}
//pop
int IsEmpty(Stack *stack){
return stack->top == nullptr; //nullptr이면 1, 아니면 0
}
void PopNode(Stack* stack){
Node* newNode;
if (IsEmpty(stack)){
printf("empty\n");
return;
}
newNode = stack->top;
printf("%d\n", newNode->data);
stack->top = newNode->prevNode; //top을 newNode(top)의 이전 값으로 설정
delete newNode; //필요없어진 노드니 메모리 해제
stack->size--;
}
int main(){
Stack* stack = new Stack();
Init(stack);
int n; //(첫 줄에 N이 주어진다. N은 주어지는 명령의 수 (1<=N<=100)
scanf("%d", &n);
for (int i = 0; i <= n; ++i){
char tmp[10];
cin.getline(tmp,10);
if (tmp[0] == 'i'){
char char_to_int[4];
for (int j = 0; j < 4; j++){
char_to_int[j] = tmp[j + 2];
}
int tmp_int = atoi(char_to_int);
PushNode(stack, tmp_int);
}
else if (tmp[0] == 'c'){
printf("%d\n", stack->size);
}
else if (tmp[0] == 'o'){
PopNode(stack);
}
}
//PushNode(stack, 1);
//PushNode(stack, 2);
//PushNode(stack, 3);
//PushNode(stack, 4);
//PopNode(stack);
//PopNode(stack);
//PopNode(stack);
//PopNode(stack);
//PopNode(stack);
//StackArray* stackArray = new StackArray();
//InitStackArray(stackArray);
//PushNodeStackArray(stackArray, 1);
//PushNodeStackArray(stackArray, 2);
//PushNodeStackArray(stackArray, 3);
//PushNodeStackArray(stackArray, 4);
//PopNodeStackArray(stackArray);
//PopNodeStackArray(stackArray);
//PopNodeStackArray(stackArray);
//PopNodeStackArray(stackArray);
//PopNodeStackArray(stackArray);
return 0;
}