백준 10866번
백준 10866번
덱
시간 제한 메모리 제한
0.5 초 (추가 시간 없음) 256 MB
문제
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 0.5 초 (추가 시간 없음) 256 MB 51979 28470 24086 56.165% 문제 정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여덟 가지이다.
push_front X: 정수 X를 덱의 앞에 넣는다. push_back X: 정수 X를 덱의 뒤에 넣는다. pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다. pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 덱에 들어있는 정수의 개수를 출력한다. empty: 덱이 비어있으면 1을, 아니면 0을 출력한다. front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다. back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
해설
이 문제는 카드뭉치와 비슷한 구조인 스택을 이용해서 풀려고한다. 스택의 push와 pop을 두가지로 나누어 일반적인 입력인 front와 스택의 맨 밑에 입력에 다른 스택을 위로 올리는 back을 구현을 하면 간단하다
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#define MAX_STACK_SIZE 100000
typedef int element;
element stack[MAX_STACK_SIZE];
int tops = -1;
int is_empty()
{
return (tops == -1);
}
int is_full()
{
return (tops == (MAX_STACK_SIZE - 1));
}
void push_front(element item)
{
stack[++tops] = item;
}
void push_back(element item)
{
if (tops == -1)
{
stack[++tops] = item;
}
else
{
int i = tops;
while (i >= 0)
{
stack[i + 1] = stack[i];
i--;
}
tops++;
stack[0] = item;
}
}
element pop_front()
{
if (tops == -1) {
return -1;
}
else return stack[tops--];
}
element pop_back()
{
if (tops == -1) {
return -1;
}
if (tops == 0) {
return stack[tops--];
}
else
{
int dume;
dume = stack[0];
for (int i = 1; i <= tops; i++)
{
stack[i - 1] = stack[i];
}
tops--;
return dume;
}
}
element size()
{
return tops + 1;
}
element empty()
{
if (tops == -1) {
return 1;
}
else return 0;
}
element front()
{
if (tops == -1) {
return -1;
}
return stack[tops];
}
element back()
{
if (tops == -1) {
return -1;
}
return stack[0];
}
int main() {
int z;
scanf("%d", &z);
for (int i = 0; i < z; i++)
{
char a[30];
scanf("%s", a);
if (strcmp(a, "push_front") == 0)
{
int b;
scanf("%d", &b);
push_front(b);
}
else if (strcmp(a, "push_back") == 0)
{
int b;
scanf("%d", &b);
push_back(b);
}
else if (strcmp(a, "pop_front") == 0)
{
printf("%d\n", pop_front());
}
else if (strcmp(a, "pop_back") == 0)
{
printf("%d\n", pop_back());
}
else if (strcmp(a, "size") == 0)
{
printf("%d\n", size());
}
else if (strcmp(a, "empty") == 0)
{
printf("%d\n", empty());
}
else if (strcmp(a, "front") == 0)
{
printf("%d\n", front());
}
else if (strcmp(a, "back") == 0)
{
printf("%d\n", back());
}
}
}