[자료구조] Queue 와 LinkedList

문제 풀고오기

일상생활에서 쉽게 볼 수 있는 큐의 모습ㅋ

1. 큐의 특징

큐의 특징을 살펴보겠습니다.

 

1). 비선형 자료구조

 큐는 배열처럼 중괄호[]에 번호를 넣어서 참조할 수 있는 선형구조가 아닌 비선형 구조이기 때문에.

일반적으로 Node 를 담는 링크드 리스트로 구현합니다.

 

2). 선입선출(First in First out)

 큐는 대기열이라는 뜻을 가지고 있습니다. 선입선출은 먼저 들어온게 먼저 나간다는 뜻으로, 큐는 현실세계에서도 쉽게 찾아볼 수 있는 자료구조입니다.

 

2. 자료구조 설계

 점심시간에 식당앞에서 밥을 먹기 위해 서 있는 사람들을 생각해봅시다.

대략 다음과 같은 특징을 갖고 있으며 이를 모방하여 괄호에 있는 함수로 구현을 해볼 생각입니다.

 

1). 가장 앞의 사람과 가장 뒤의 사람이 누군지 알 수 있다.( (front(), back() )

2). 줄이 비었는지 꽉 찼는지 알 수 있다. ( empty(), full() )

3). 몇명이 줄을 서 있는지 알 수 있다. ( size() )

4). 사람들이 줄을 선다. ( push(손님번호 int x) )

5). 앞에서부터 차례대로 밥을 먹고 나간다. ( pop() )

 

3. 함수 설계

1). front(), back()  

 새로운 사람이 들어올 때마다 그 사람은 줄의 가장 뒤에 서겠죠?

이를 위해 다음에 만들 push(int x) 함수에서 새로운 사람 x가 들어올 때마다

맨 뒷 사람이 누군지도 갱신해줄 필요가 있을 것 같습니다.

 

front()와 back()함수는 간단히 가장 앞과 가장 뒤에 사람을 출력하면 되겠죠?

 

2). empty()와 full() 

 스택이나 힙 오버플로우가 일어나는 것처럼 초기에 최대 사이즈 보다 많은 데이터를 담으려 하면 에러가 나는 모습을 보신 분들도 계실거라 생각합니다.  이처럼 container(list, stack과 같이 자료를 담는 그릇)를 구현할 때는 항상 컨테이너 안이 비었는지 꽉찼는지를 유의하면서 코드를 작성할 필요가 있습니다. 

 

 다음에 만들 size()함수가 반환하는 값을 가지고 size()가 0이면 empty()함수는 1을 리턴하게 하고

반대로 큐의 사이즈가 max 값에 도달하면 더이상 집어넣을 수 없다는 의미에서 1을 반환하게 해봅시다.

 

3). size()

 큐에는 현재의 데이터 개수를 알고 있는 size라는 int 형 변수가 필요할 것 같습니다. 

size 변수는 데이터를 넣을 때 ++ 하고 뺄 때 -- 하면 되겠죠? 

따라서 크기를 알고 싶을 때는 멤버변수인 size 값을 그대로 리턴하면 될 것 같습니다.

 

4). push(int x) 

public void push(int x)
{
    Node newNode = new Node(x); // 새로운 데이터
    if (empty() == 1)     // 큐가 비었을 경우
    {
        this.front = newNode;
    } else
    {
        Node temp = this.front; // 탐색용 임시 노드가 가장 앞을 가리키게 하고
        while (temp.next != null) // 뒷 사람을 찾아가게 한다.
        {
            temp = temp.next;
        }
        // 갈 때까지 가본 후에는 temp는 가장 뒷사람을 가리키게 된다. 맨 뒷사람에게 나를 연결시키자.
        temp.next = newNode;
    }
    back = newNode; // 추가 후에는 새로 들어온 사람이 가장 뒤에 있다는 표시를 해주자.
    size++; // 큐 사이즈를 하나 늘린다.
}

 

 큐에는 가장 앞을 가리키는 Node front 와 back이 있습니다.

새롭게 들어오는 데이터를 newNode라고 했을 때,

 

 큐가 비어있는 경우와 비어있지 않을 때를 구분하여 데이터를 넣어줄 필요가 있습니다.

비어있을 때는, 단순히 가장 앞과 가장 뒤를 처음 들어온 사람으로 지정해주고 사이즈를 하나 키우면 됩니다.

 

 그리고 큐가 비어있지 않을 경우에는 큐의 비선형적인 특징으로 인해 이전까지 배열에서 [] 를 사용해서 접근하던 방식을 사용할 수 없어, 앞에서부터 차근차근 찾아갈 필요가 있습니다.

 

 이를 위해 검색을 위한 temp Node를 하나 만들고 가장앞에서부터 시작하여 가장 뒷사람을 만날 때(가장 뒷사람의 다음이 null 일 경우)까지 찾아가서 가장 뒷사람의 다음을 새로운 노드로 해줘야 합니다.

 

 처음 하시는 분들은 이 부분이 이해가 잘 안 되실 수도 있습니다. 종이에 적어가면서 손 디버깅을 해보시는 것을 추천드립니다. 큐에 데이터가 2개 정도 있다고 생각하고 하나를 집어넣을 때 while 문이 종료되면 어떤 상태가 되는 지 확인해보세요!

 

 연결이 끝난 이후에는 큐 사이즈를 하나 키우고 가장 뒷사람을 새로 들어온 사람으로 갱신해주세요~

 

5). pop()

 데이터를 꺼냄과 동시에 출력을 하는 방식으로 구현하겠습니다. 큐는 가장 앞에서 (front) 자료를 꺼내는 특징을 갖고 있으므로 가장 앞의 원소인 front Node 의 값을 꺼내기 전에 어딘가에(int front) 저장해둔 다음,

front = front.next; 문장을 통해 가장 앞 사람을 그 다음 사람으로 갱신 해줍시다.

 

이러면 가장 앞과 연결되어 있던 사람이 맨 앞으로 오겠죠?

그리고 데이터를 꺼낸다는 의미에서 size를 하나 줄여주시고 int front 값을 반환하면 되겠습니다.

 

4. 구현하기

-JAVA 버전(링크드 리스트 구현버전)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StringReader;

public class Queue
{
    public static class Node
    {
        Node next;
        int num;
        Node(int num)
        {
            this.num = num;
        }
    }

    public static class Q
    {
        Node front;
        Node back;
        int size;

        Q() {}

        public int front()
        {
            return front == null ? -1 : front.num;
        }
        public int back()
        {
            return back == null ? -1 : back.num;
        }

        public int empty()
        {
            return size == 0 ? 1 : 0;
        }

        public int size()
        {
            return size;
        }

        public void push(int x)
        {
            Node newNode = new Node(x);
            if(empty() == 1)
            {
                this.front = newNode;
            }
            else
            {
                Node temp = this.front;
                while(temp.next != null)
                {
                    temp = temp.next;
                }
                temp.next = newNode;
            }
            back = newNode;
            size++;
        }
        // 가장 앞에 있는 정수를 뺀다.
        public int pop()
        {
            // 큐가 비어있지 않으면
            if(empty() != 1)
            {
                int popNum = this.front.num;
                this.front = this.front.next;
                size--;
                if(size == 0) this.back = null;
                return popNum;
            }
            else
            {
                return -1;
            }
        }
    }

    public static void main(String[] args) throws Exception
    {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        Q q = new Q();
        for (int i = 0; i < N; i++)
        {
            String[] input = br.readLine().split(" ");

            String command = input[0];
            if(input.length == 2)
            {
                // push x
                q.push(Integer.parseInt(input[1]));
            }
            else
            {
                switch(command.charAt(0))
                {
                    // front
                    case 'f':
                        sb.append(q.front());
                        break;
                    // back
                    case 'b':
                        sb.append(q.back());
                        break;
                    // size
                    case 's':
                        sb.append(q.size());
                        break;
                    // empty
                    case 'e':
                        sb.append(q.empty());
                        break;
                    // pop
                    case 'p':
                        sb.append(q.pop());
                        break;
                }
                sb.append("\n");
            }
        }
        System.out.println(sb);
    }
}

- CPP 버전(단순 배열)

#define MAX 10001
#include 

int arr[MAX];
int rear = -1;

int size()  { return rear + 1; }

int empty() { return size() > 0 ? 0 : 1; }
int full()  { return size() == MAX ? 1 : 0; }

int front() { return empty() ? -1 : arr[0]; }
int back() { return empty() ? -1 : arr[rear]; }

int pop()
{
	if (empty()) return -1;
	
	int result = arr[0];
	for (int i = 0; i < rear; i++) arr[i] = arr[i + 1];
	rear--;

	return result;
}
void push(int x)
{
	if (full()) return;
	arr[++rear] = x;
}

int main()
{
	int n, result = 0;
	scanf("%d", &n);
	char inst[6];
	int x = 0;
	
    // 명령어 수행 n == 0 되면 반복문 탈출
	while (n--) {
		scanf("%s", inst);
		if (inst[0] == 'p' && inst[1] == 'u')
		{
			scanf("%d", &x);
			push(x);
		}
		else if (inst[0] == 'p' && inst[1] == 'o')
		{
			printf("%d\n", pop());
		}
		else
		{
			switch (inst[0])
			{
			case 's': result = size(); break;
			case 'e': result = empty(); break;
			case 'b': result = back(); break;
			case 'f': result = front(); break;
			}
			printf("%d\n", result);
		}
	}
	return 0;
}