[자료구조] 14 스택과 큐

📌 스택 Stack

선형 리스트의 특별한 형태 

책 또는 접시 같은 것들을 쌓아두었다고 생각 

접시를 쌓을 때 쌓게 되면 맨 위에 쌓고 뺄 때도 맨 위에서 빼게 된다는 것 기억 

 

👉 Stack 은 LIFO 

Last In First Out : 나중에 들어간 원소가 가장 먼저 나온다 

 

❓어디에 사용

함수 호출 관리, function call , 문법 검사 syntax checking , 연산식 평사 expression evaluation 

 

✔️ push : 원소를 추가하는 연산 

✔️ Pop : 원소를 삭제하는 연산 

연산	Stack ( 0,1,2,3,4,5)	top
초기 상태		-1
PUSH a	a	0
PUSH b	a b	1
PUSH c	a b c	2
POP c	a b	1
PUSH d,e	a b d e	3
POP e	a b d	2
POP d	a b	1

 

👉 top = -1 : 초기 상태, 스택이 비어 있다는 뜻 

👉 full stack = stack의 top 포인터 값이 STACK_SIZE - 1 (배열의 상한 경계) 일 경우

위와 같은 경우 STACK_SIZE 가 6이므로 TOP이 5가 되면 full 

 

#define STACK_SIZE 100
int stack[STACK_SIZE];

int top = -1;
void push(int item);
int pop();
void print_stack();
void main()
{
    push(3); //3, top = 0
    push(4); //3 4, top = 1
    push(5); //3 4 5, top = 2
    pop(); //return stack[1], top = 1
    print_stack(); //3 4
    pop(); //return stack[0], top = 0
    print_stack(); //3
    pop(); //return stack[-1], top = -1
    print_stack(); //
    pop(); //return -999, empty!
    print_stack(); //
    printf("finish\n");
}

void print_stack(){ //stack print
    int i;
    for (i=0; i <=top; i++){
        printf("%d ", stack[i]);
    }
    printf("\n");
}

void push(int item){ //push
    if ( top >= STACK_SIZE-1){ 
        printf ("stack full!");
        return; //상한 경계선 넘으면 full
    }
    stack[++top] = item; //next stack에 item push
    print_stack();
}

int pop(){
    if (top < 0){ //stack empty
        printf ("empty stack!");
        return -999; //오류 return
    }
    return stack[top--];
}

// 결과
// 3 
// 3 4 
// 3 4 5 
// 3 4 
// 3 

// empty stack!
// finish

 

 

 

📌 Queue 큐 

처리를 기다리고 있는 원소나 작업들의 리스트 

👉 선형 리스트이지만 FIFO 

First In First Out : 먼저 들어간 원소가 먼저 삭제된다 

앞과 뒤에 구멍이 뚫려 있어서 큐에 삽입하면 뒤로 들어가고 삭제는 앞에서부터 되는듯한 구조

 

front👇				rear👇
A	B	C	D	E

Q = [ a0, a1, a2, a3, a4 ] 일 때 맨 앞원소 a0을 가리키는 front와 a4를 가리키는 rear

 

#define QUEUE_SIZE 100
int queue[QUEUE_SIZE];
int rear = -1;
int front = -1;

void main(){
    int temp; 
    addq(3); //3, rear = 0
    addq(5); //3 5, rear = 2
    addq(7);  //3 5 7, rear = 3
    temp = deleteq(); //return queue[0], front = 0, temp = 3
    print_queue(); //5, rear = 2
}

void print_queue(){
    int i;
    for ( i=front+1; i<= rear; i++){
        printf("%d ", queue[i]);
    }
    printf("\n");
}

void addq(int item){
    if (rear == QUEUE_SIZE -1){
        printf( "full Queue !");
        return;
    }
    queue[++rear] = item;
    print_queue();
}

int deleteq(){
    if (front == rear){
        printf( " empty Queue!");
        return -999;
    }
    return queue[++front];
}

//결과
3
3 5
3 5 7 
5 7

 

 

 

📌 순환 큐 Circular Queue

큐의 오른쪽 끝을 반대편 끝과 연결하여 원소가 이동할 필요 없이 전체 공간을 사용

빙글빙글 돌아간다

#include <stdio.h>
#define Q_SIZE 100
int front, rear;
int cqueue[Q_SIZE];
void addcq(int item);
int deletecq();
void print_queue();

void main()
{
    int temp;
    front = rear = 0; //queue와 다르다, 0부터 시작

    addcq(1); //1, 
    addcq(2); //1 2 
    addcq(3); //1 2 3
    addcq(4); //1 2 3 4
    temp = deletecq(); //temp = cqueue[1] = 1
    print_queue(); //2 3 4, front = 2
    temp = deletecq(); //temp = cqueue[2] = 2
    print_queue(); //3 4, front = 3
    temp = deletecq(); //temp = cqueue[3] = 3
    print_queue(); //4
    temp = deletecq();//temp = cqueue[4] = 4
    print_queue(); //
}

void print_queue(){
    int i;
    for (i = front + 1; i<= rear; i++){
        printf("%d ",cqueue[i]);
    }
    printf("\n");
}

void addcq(int item){
    rear = (rear + 1) % Q_SIZE;
    if (front == rear) { 
        printf("full Queue!");
        rear = rear - 1 ;
        return;
    }
    cqueue[rear] = item;
    print_queue();
}

int deletecq(){
    if(front == rear){
        printf("empty Queue!");
        return -999;
    }
    front = ( front + 1 ) % Q_SIZE;
    return cqueue[front];
}

//결과 
1 
1 2 
1 2 3 
1 2 3 4 
2 3 4 
3 4 
4