https://www.acmicpc.net/problem/10845
10845번: 큐
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지
www.acmicpc.net
문제
정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여섯 가지이다.
- push X: 정수 X를 큐에 넣는 연산이다.
- pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- size: 큐에 들어있는 정수의 개수를 출력한다.
- empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
- front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
큐 : 일상생활에서 흔히 볼 수 있는 자료구조. 대중교통 탈떄 줄을 서는 것 ( 먼저 들어온 사람이 먼저 타는 것)이
큐의 흔한 예이다. First-in First_out 구조의 자료구조이다.
큐의 Enqueue 연산 : 큐에서 데이터를 넣는 연산
큐의 Dequeue연산 : 큐에서 데이터를 꺼내는 연산
위의 그림처럼 1,2 데이터를 Enqueue 후 Dequeue 연산을 하면 처음에 들어왔던(First-in) 1이 먼저 나가는(First-out)것을 볼 수 있다.
위의 그림은 그림이 굉장히 못생겼다.. 스택의 Enqueue 연산을 구현해본 것이다. 처음 변수 Front,Rear은 0이다.
데이터가 하나씩 삽입될떄마다 Rear의 변수값을 하나씩 증가시킨다.
스택의 Dequeue연산은 Front값을 하나씩 증가시키면서 데이터를 삭제한다.
선형 큐에서 다음과 같은 상황이 있을 때 문제가 생긴다.Rear변수가 배열의 마지막 인덱스이고 앞쪽에서 Dequeue연산을 했을 때 생기는 빈공간을 활용 할 수 없다.
이러한 선형 큐의 문제점을 해결하기 위해 원형 큐를 소개하고자 한다.
원형 큐는 배열의 효과적인 활용을 위해서 Rear과 Front를 회전시키는 것이다. 이때 Rear,Front가 배열의 끝에 도달하면 다시 맨 앞으로 이동시킨다.
앞에서 언급한 것처럼 Enqueue연산시 Rear변수를 1 증가시키고 데이터를 삽입한다.
Dequeue 연산시 Front변수를 1 증가시킨다.
전체 소스 코드
#include <stdio.h>
#define True 1
#define False 0
#include<string.h>
#define LEN 100000
typedef struct _cQueue{
int size; //큐의 크기
int front;
int rear;
int arr[LEN];
}CQUEUE;
typedef CQUEUE Queue;
void Queueinit(Queue *pq){ //큐의 초기화
pq->front = 0;
pq->rear = 0;
pq->size = 0;
}
int Empty(Queue *pq){ //큐가 비어있는 경우 -> front와 rear이 같은 값일떄
if(pq->front == pq->rear){
return True;
}
else{
return False;
}
}
int Nextindex(int pos){ // 큐의 다음위치에 해당하는 인덱스 값 반환
if(pos == LEN - 1 ){
return 0; //큐의 끝에 도달했을때 0으로 이동(앞으로 이동한다)
}
else{
return pos = pos + 1; //큐의 다음위치에 해당하는 인덱스 값 반환
}
}
int Front(Queue *pq){
if(Empty(pq)){
return -1; //비어있으면 -1반환
}
else{
return pq->arr[pq->front+1];
}
}
int Back(Queue *pq){ //rear인덱스의 큐 값 반환
if(Empty(pq)){
return -1;
}
else{
return pq->arr[pq->rear];
}
}
int Size(Queue *pq){
if(Empty(pq)){ //큐의 크기 반환
return 0;
}else{
return pq->size;
}}
void Push(Queue *pq,int data){
pq->rear = Nextindex(pq->rear); //큐의 Enqueue연산
pq->arr[pq->rear] = data; //Rear값 1 증가시키고 큐 값 반환
pq->size = pq->size + 1;
}
int Pop(Queue *pq){ //큐의 Dequeue 연산
if(Empty(pq)){
return -1;
}
else{
pq->size = pq->size - 1;
pq->front = Nextindex(pq->front); //front값 1 증가시키고 큐 값 반환
int rdata = pq->arr[pq->front];
return rdata;
}
}
int main(void){
Queue q;
Queueinit(&q);
char array[6];
int n;
scanf("%d",&n);
for(int i = 0;i<n;i++){
scanf("%s",array);
if(strcmp(array,"push") == 0){
int x;
scanf("%d",&x);
Push(&q,x);
}
else if(strcmp(array,"pop") == 0){
printf("%d\n",Pop(&q));
}
else if(strcmp(array,"size") == 0){
printf("%d\n",Size(&q));
}
else if(strcmp(array,"empty") == 0){
printf("%d\n",Empty(&q));
}
else if(strcmp(array,"front") == 0){
printf("%d\n",Front(&q));
}
else if(strcmp(array,"back") == 0){
printf("%d\n",Back(&q));
}
}
}
'자료구조' 카테고리의 다른 글
| 백준 11899번 C언어 (0) | 2021.09.19 |
|---|---|
| 백준 4949번 C언어 (0) | 2021.09.17 |
| 백준 20001번 c언어 (0) | 2021.09.15 |
| 자료구조 - 백준 10828번 스택(C언어) (0) | 2021.09.13 |
| 자료구조 - 17608번 C언어 (0) | 2021.09.12 |