자료구조 : 스택, 큐, 리스트

 

자료구조란, 데이터를 처리하는 추상적인 구조를 말합니다.

기본적인 데이터들을 효율적으로 처리하기 위해 필요하며,

자료구조 없이는 알고리즘을 수행하는 데 매우 큰 어려움이 따릅니다.

 

오늘은 기초적인 자료구조인 스택과, 큐, 리스트에 대해 정리해보겠습니다.

 

 

 

 

데이터들의 배열, 리스트

리스트란 말 그대로 데이터를 나열한 구조입니다.

크게 ArrayList와 LinkedList, 두가지로 구분합니다.

 

ArrayList

배열리스트라고도 하며, 각 데이터마다 자신의 번호(index)를 가지고 있습니다.

따라서 번호만 안다면, 해당 데이터를 빠르게 찾을수 있습니다.

반면, 배열구조로 되어있기 때문에,

데이터를 뺀다면 이후 데이터들의 인덱스를 모두 하나씩 당겨야하고,

데이터를 추가한다면 이후 데이터들의 인덱스를 모두 하나씩 뒤로 밀어야하는 등

데이터 추가 및 제거시 시간이 걸리게 됩니다. 

또한 배열리스트는 배열을 선언한 뒤 사용하기 때문에, 공간에 제약이 있기도 합니다.

index

1

2

3

4

5

6

7

8

9

ArrayList

arr 1

arr 2

arr 3

arr 4

arr 5

arr 6

arr 7

arr 8

arr 9

LinkedList

연결리스트라고 하며, 각 데이터가 배열이 아닌 가상의 링크(link)로 연결되어있는 리스트입니다.

중간의 데이터를 변경하더라도 해당 부분만 처리하면 되기 때문에

연결리스트에비해 데이터 추가 및 제거가 편합니다.

또한, 각각의 데이터가 가상으로 연결되어있기 때문에 배열의 크기에 제약이 없습니다.

단, 인덱스가 따로 없기 때문에, 데이터 탐색 시 첫 데이터부터 나올때까지 탐색해야하므로

탐색 시에 시간이 걸리게 됩니다.

또한, 데이터마다 다음 데이터를 안내하는 경로가 존재해야하기 때문에, ArrayList에 비해 용량이 조금 더 큽니다.

 

또한 사용자는 ArrayList라면 데이터 전체의 배열을 알 수 있지만,

LinkedList는 시작점, head만 알고있습니다.

head

link

data

link

data

link

data

link

data

link

end

 

LinkedList의 추가 및 제거

LinkedList의 데이터 추가 및 제거에는 순서가 존재합니다.

반드시 뒤의 데이터를 먼저 이어준 뒤, 앞의 데이터를 연결해야된다는 점이죠.

무슨 뜻인지 잘 모르겠다면 예를 들어보겠습니다.

 

data{
    item item;
    data next;
}

LinkedList의 데이터는 다음 데이터를 알려주는 next, 데이터에 포함된 값을 알려주는 item이 존재한다고 하겠습니다.

 

그리고 첫 데이터는 data1이라고 하고, data2가 이어져있다고 가정하겠습니다.

data1

next

data2

만약 data1과 data2 사이에 data3을 추가하려고 한다면

data2와 data3을 연결한 뒤 data1과 data3을 연결해야 합니다.

1

data1

data3

next

data2

2

data1

next

data3

next

data2

data3.next = data2; // data2의 위치를 data3로 먼저 지정
data1.next = data3; // data3를 data1 과 연결

그런데 문제점은, 저희는 data2의 위치를 모릅니다. 우리는 첫 데이터만을 알고 있기 때문이죠

따라서 data2의 위치는 data1.next로 찾아야합니다.

따라서 반드시 먼저 data3의 next에 data2를 지정해야합니다.

data1.next가 data3가 된다면, data2를 찾을 수 없기 때문입니다.

data3.next = data1.next; // data2의 위치 = data1.next를 data3로 먼저 지정
data1.next = data3; // data3를 data1 과 연결

 

마찬가지로, 제거할때도 마찬가지입니다.

data1

next

data2

next

data3

위의 구조에서 data2를 지우려 할때,

data2를 먼저 지우면 data3의 위치를 알 수 없습니다.

data3의 위치는 data2.next로 접근해야하기 때문입니다.

그렇기 때문에, data1의 next를 data3로 연결한 뒤 지워야 합니다.

data1.next = data2.next; // data1과 data3를 먼저 연결
data2.remove(); // data2 삭제

 

리스트의 동작

리스트를 만드려면 크게 몇가지 기능이 필요합니다.

비어있는지 확인하는 기능,

가득 차 있는지 확인하는 기능 (크기가 한정된 리스트일 경우),

특정 인덱스에 데이터를 집어넣는 기능,

특정 인덱스에 데이터를 제거하는 기능,

특정 인덱스의 데이터를 확인하는 기능,

이 외에도 맨 앞이나 뒤에 데이터를 추가 또는 삭제하는 함수를 추가하기도 합니다.

위의 기능은 해당 리스트가 ArrayList 인지, LinkedList인지에 따라 달라지기도 합니다.

 

 

 

 

 

데이터를 쌓아서 담는 스택(Stack)

스택은 데이터를 쌓아서 정리하는 가상 구조입니다.

이게 무슨 소리냐면, 아래에 있는 데이터를 꺼내기 위해서는 위의 데이터를 꺼낸 뒤에 사용할 수 있다는 뜻입니다.

즉 후입선출 (後入先出, LIFO : Last In First Out )의 형태를 가진다는 것입니다.

이로 인해서 가장 마지막에 들어간 데이터가 가장 먼저 나옵니다.

stack을 만들기 위해서는 데이터를 담는 array와 지점을 나타내는 top, 두가지로 표현됩니다.

number top = -1;
data[] arr = data[n];

 

스택의 동작

스택을 만들기 위해서도 몇가지 기능이 필요한데,

스택이 비어있는지 확인하는 기능,

스택이 가득찼는지 확인하는 기능,

스택에 값을 집어넣는 기능,

스택에서 값을 빼내는 기능,

스택 맨 위의 값을 확인하는 기능

 

이를 간단하게는 아래와 같이 구현 가능합니다.

// 비어있는지 확인하는 함수
boolean isEmpty(){
    return top==-1;
}

// 스택이 가득찼는지 확인하는 함수
boolean isMax(){
    return top==max;
}

// 값을 집어넣는 함수
// 성공여부를 확인하기 위해 성공시 1, 실패시 0을 반환
number push(data, stack){
    if(isMax()){
       return 0;
    }
    stack[++top] = data;
    return 1;
}

// 맨 위값을 스택에서 빼내는 함수
data pop(stack){
    if(isEmpty())
    	return NULL;
    return stack[top--];
}

// 맨 위값을 확인하는 함수(stack에서 빼지는 않는다)
data get(stack){
    if(isEmpty())
        return NULL;
    return stack[top];
}

 

 

 

 

 

데이터가 지나는 통로, 큐(Queue)

큐(Queue)는 스택과는 다르게 일종의 통로와 같은 자료구조입니다.

데이터를 꺼낼때 가장 먼저 넣은 데이터 부터 꺼냅니다.

즉, 선입선출 ( 先入先出, FIFO : Fast In First Out )의 형태를 가집니다.

Queue를 만들기 위해서는 데이터를 담는 array와 시작지점을 나타내는 head, 끝을 나타내는 tail가 필요합니다.

보통은 연결리스트의 형식으로 만들긴 하나,

배열리스트를 활용하여 만들기도 합니다.

number head = 0;
number tail = -1;
data[] arr = data[n];

단, 시작점과 끝점이 계속 바뀌기 때문에, 나머지(modulus) 연산자를 활용한 원형 큐의 형태로 만드는 것이 좋습니다.

 

큐의 동작

큐에서 필효한 기능을 확인해보겠습니다.

큐가 비어있는지 확인하는 기능,

큐가 가득찼는지 확인하는 기능,

큐에 값을 집어넣는 기능,

큐에서 값을 빼내는 기능,

큐에서 나올 값을 확인하는 기능

 

이를 표현하면 아래와 같습니다.

// 비어있는지 확인
boolean isEmpty(){
    return head>tail;
}

// 가득찼는지 확인
boolean isMax(){
    return (tail-head)<=n;
}

// 큐에 데이터를 집어넣는 함수
number enqueue(data, queue){
    if(isMax())
        return 0;
    queue[(++tail)%n] = data;
    return 1;
}

// 큐에서 데이터를 빼내는 함수
data dequeue(){
    data data = NULL;
    if(isEmpty())
        return data;
    data = queue[head%n];
    head++;
    return data;
}

//빼낼 데이터를 확인하는 함수
data getQueue(){
    if(isEmpty())
        return NULL;
    return queue[head%n];
}

위의 함수는 배열리스트로 만든 큐로, 길이가 제한된 배열을 활용하기 위해 원형큐를 고려하여 만든 함수입니다.

따라서 연결리스트 형식의 큐를 만든다면, 별도의 함수를 만들어야 합니다.