자료구조 : Stack & Queue(1)

이번 포스팅에서는 Stack과 Queue라는 자료구조에 대해 알아보자.

Stack

• Insert/Delete만 제공
• Push/Pop이라고 부름
• Last in, First out(나중에 들어오는게, 먼저 나가는 것)
• 성능: Push: O(1), Pop: O(1)(넣는것을 push, 빼는것을 pop)

Queue

• Insert/Delete만 제공
• First in, First out( 먼저 들어오는게, 먼저 나가는 것)
• 성능: Insert O(1) , Delete O(1)

Stack 구현

 

Stack Pointer는 값이 다음에 들어올 자리를 뜻한다.

Stack Code

int Stack[N];
int SP;
 
int init() {SP = 0}
 
int isEmpty() {return SP == 0;}
 
int Push()
{
    Stack[SP] = x; SP++;
}
 
int Pop()
{
    SP--; return Stack[SP];
}

 

Queue 구현

Stack과 다르게 Queue는 Head와 Tail 두개가 필요하다. 앞서 다룬 stack보다 좀더 생각할 거리가 늘어나게 된다. 

만약 새 값이 insert 될때 Tail과 Head는 어떻게 될까? head는 그대로 있고 Tail은 위로 한칸 움직일 것이다.

반대로 값이 delete 되면 Head가 위로 한칸 올라갈것이다.

 

 

그렇다면 다음과 같은 상황에서 Tail에 새 값이 새로 insert가 되면 어떻게 될까? 간단하다 제일 밑의 빈공간에 Tail이 가리키게 된다. 아래의 그림과 같이 말이다.

 

그러면 이 상황에서 좀 더 나아가서 생각해보자. 여기서 값을 꽉차도록 넣으면 다음과 같은 상황이 발생한다.

Tail 과 Head가 겹치는 일이 발생한다. 그리고 이 상태에서 값을 하나씩 제거 한다고 해보자 하나씩 제거해 가다보면

결과 적으로 이렇게 될 것이다. 뭔가 이상함을 느끼지 않았는가 ? 그렇다 Tail과 Head로 꽉차 있을 때랑 비어있을 때 구별을 할 수 없게 된다. 이것은 Queue에서 오래된 이슈이며 이것을 해결하는 방법 또한 간단한 편이다.

해결방법은 꽉 차기전에 값을 받지 않게 만들면 된다.

 

Queue Code

int Queue[N];
int Head, Tail;
 
int init() {
    Head = 0;
    Tail = 0;
}
 
int isEmpty() { return Head == Tail ; }
 
int insert(int x) {
 
    Queue[Tail] = x;
    Tail ++;
    Tail = Tail % N;
}
 
int delete(){
    
    int oldHead = Head;
    Head++; Head = Head % N ;
    return Queue[oldHead];
}

간단하게 Stack과 Queue에 대해 알아보았다. 이제 스택과 큐로 무엇을 활용할 수 있는지 다음 포스팅에서 알아보도록 하겠다.