알고리즘 - Stack, Queue (선형 큐, 원형 큐, 알고리즘 코드)

스택

'먼저 들어간 것이 나중에 나오는 자료구조'

Last In First Out (LIFO) 구조이다. 

스택은 배열과 연결 리스트로 나타낼 수 있다. 

 

스택

스택의 구성 

- 상단 (top) : 스택에서 제일 나중에 입력된 데이터의 위치

- 하단 (bottom) : 스택에서 제일 먼저 입력된 데이터의 위치

- 요소 (element) : 스택에 저장되는 데이터 그 자체

- 공백 (empty stack) : 아무런 데이터도 갖고 있지 않은 스택

 

 

 

스택의 연산

push() : 스택에 데이터를 추가한다.

pop() : 스택에서 데이터를 삭제한다.

is_empty(s) : 스택이 공백상태인지 검사한다.

is_full(s) : 스택이 포화상태인지 검사한다.

create() : 스택을 생성한다.

peek(s) : 요소를 스택에서 삭제하지 않고 보기만 하는 연산이다.

 

 

 

push 연산

void push(int value){       //스택에 데이터 삽입
    if(IsFull()==true)      //스택이 가득 차면
        printf("스택이 가득 찼습니다.");
    else                    //빈 공간이 있으면
        stack[++top]=value; 
}

 

pop 연산

int pop(){                  //데이터 빼기
    if(IsEmpty()==true)    
        printf("스택이 비었습니다.");
    else                   
        return stack[top--];    
}

 

is_empty() 연산

int IsEmpty(){    
    if(top<0)      
        return true;
    else   
        return false;
   }

 

is_full 연산

int IsFull(){       
    if(top>=MAX_STACK_SIZE-1)   
        return true;          
    else                
        return false;
}

 

 

 

큐

First In First Out (FIFO) 구조이다. 

 

배열로 구현하게 되면 제한된 공간에서 data가 한 쪽으로만 이동하여 한계에 이르는 Drifting(표류) 현상 발생한다. 

선형큐, 원형큐가 있다.

 

선형큐

 

is_empty()

int IsEmpty(void){
    if(front==rear)//front와 rear가 같으면 큐는 비어있는 상태 
        return true;
    else return false;
}

 

 

is_full()

int IsFull(void){
    int tmp=(rear+1)%MAX; 
    if(tmp==front)
        return true;
    else
        return false;
}

 

 

add()

void addq(int value){
    if(IsFull())
        printf("Queue is Full.\n");
    else{
rear = (rear+1)%MAX;
 queue[rear]=value;
 }

 

 

delete()

int deleteq(){
    if(IsEmpty())
        printf("Queue is Empty.\n");
    else{
        front = (front+1)%MAX;
        return queue[front];
    }
}

 

 

원형큐