[DAY 10] Stack And Queue

Stack의 개념

Stack은 쌓아 놓은 접시와 같은 자료구조다

마지막에 쌓은 접시가 먼저 사용되듯, 나중에 입력된 자료가 먼저 처리된다

이것을 후입선출(LIFO : Last In First Out)이라 부른다

Push : 스택에 자료를 넣는 동작이다

Pop : 스택에서 자료를 꺼내는 동작이다

Stack 분석

스택은 1차원 배열을 사용하여 구현한다. 스택의 방식을 살펴보자(그림)

#. Stack은 Shift를 할 필요가 없다! top 포인터가 마지막을 가리키고 있으면 full이고 처음을 가리키고 있으면 empty다.

#define SIZE    5
#include <stdio.h>
 
typedef struct _stack {
    int data[SIZE];
    int top;
} Stack;
 
int Push(Stack *s, int data);
int Pop(Stack *s, int *data);
void IsFull(Stack *s);
void IsEmpty(Stack *s);
 
void main()
{
    Stack stack;
    int container;
    int i;
 
    stack.top = 0;
 
    Push(&stack, 10);    Push(&stack, 20);
    Push(&stack, 30);    Push(&stack, 40);
    Push(&stack, 50);
    
    // push한 데이터 모두 출력
    for (i = 0; i < SIZE; i++) {
        printf("%d \t", stack.data[i]);
    }
 
    puts("");
 
    // 1개씩 pop해서 출력해본다
    Pop(&stack, &container);
    printf("%d \t", container);
 
    Pop(&stack, &container);
    printf("%d \t", container);
 
    Pop(&stack, &container);
    printf("%d \t", container);
 
    Pop(&stack, &container);
    printf("%d \t", container);
 
    // confirm stack underflow
    Pop(&stack, &container);
    printf("%d \t", container);
}
 
int Push(Stack *s, int data)
{
    IsFull(&s);
 
    s->data[s->top++] = data;
 
    return 1;
}
 
int Pop(Stack *s, int *data)
{
    IsEmpty(&s);
 
    *data = s->data[--s->top];
 
    return 1;
}
 
void IsFull(Stack *s)
{
    if (s->top == SIZE) {
        puts("stack overflow!");
        return 0;
    }        
}
 
void IsEmpty(Stack *s)
{
    if (s->top == 0) {
        puts("stack underflow!");
        return 0;
    }
}

Depth First Search

깊이우선탐색(DFS)

Queue의 개념

데이터 큐는 말 그대로 줄서기 자료구조다. 먼저 줄을 선 데이터가 먼저 처리된다.

이것을 선입선출이라 부른다

Enqueue : 데이터를 큐에 넣는 동작이다

Dequeue : 큐에서 데이터를 꺼내는 동작이다

선형 Queue 분석

선형큐는 1차원 배열을 사용하여 구현한다. 선형큐의 방식을 살펴보자

선형큐를 쓰면 Shift를 써야 한다. 안그러면 메모리 낭비가 심하다

그래서 환형 큐를 많이 쓴다

#define SIZE    100
#include <stdio.h>
 
typedef struct _queue {
    int data[SIZE];
    int front;
    int rear;
} Queue;
 
int Enqueue(Queue *q, int data);
int Dequeue(Queue *q, int *data);
 
void main()
{
    Queue queue;
    int i;
    int value;
 
    // initialization
    for (i = 0; i < SIZE; i++) {
        queue.data[i] = 0;
    }
    queue.front = 0;
    queue.rear = 0;
 
    Enqueue(&queue, 10);    Enqueue(&queue, 20);
    Enqueue(&queue, 30);    Enqueue(&queue, 40);
 
    Dequeue(&queue, &value);
    printf("Dequeue data : %d \n", value);
 
    Dequeue(&queue, &value);
    printf("Dequeue data : %d \n", value);
 
    for (i = 0; i < 4; i++) {
        printf("%d \t", queue.data[i]);
    }
}
 
int Enqueue(Queue *q, int data)
{
    int c;
 
    // 데이터가 가득 찬 경우
    if (q->rear == SIZE)
        return 0;
 
    // 그렇지 않으면 Enqueue 진행
    q->data[q->rear++] = data;
 
    // Shift 작업
    if ((q->rear == SIZE) && (q->front != 0)) {
        for (c = 0; c < SIZE - q->front; c++) {
            q->data[c] = q->data[q->front + c];
        }
 
        // Shift에 의한 front와 rear의 위치 변경
        q->rear = SIZE - q->front;
        q->front = 0;
    }
 
    // 정상적 반환
    return 1;
}
 
int Dequeue(Queue *q, int *data)
{
    if (q->front == q->rear)
        return 0;
 
    *data = q->data[q->front++];
 
    // 초기 상태로 돌리는 작업
    if (q->front == SIZE) {
        q->front = 0;
        q->rear = 0;
    }
 
    return 1;
}

환형 큐의 문제점

front == rear이면 full인지 empty인지 구분할 수가 없다!

Breadth First Search

queue를 이용한다

#. DFS BFS

#. 개인과제

스택을 이용하여 괄호를 포함하는 계산식 처리 프로그램을 작성한다(후위표기법).

단, 숫자는 자연수만 입력하며 연산은 덧셈과 뺄셈만 처리한다

Expression> 113 + 11 - (32 - (9 - 2 + 6))

Result: 105

후위표기법 수식변환 알고리즘(Edsder W. Dijstra)

1. 피연산자는 그대로 출력한다

2. 연산자는 '(' 전까지 Pop하여 출력 후, 스택에 Push한다

3. '('는 스택에 Push한다

4. ')'는 '(' 전까지 Pop하여 출력 후, '('을 Pop하여 함께 제거한다

후위표기법 수식계산

피연산자는 Push하고, 연산자는 피연산자 두 개를 Pop하여 계산 후 Push한다.