소개

안녕하세요 👋 밖에 할 말이 없습니다.
배너에 있는 이 사람이 누구인지 궁금하다면 알고리즘 개념의 발명가인 Khwarizmi입니다.
앞으로 더 발전된 시리즈를 시작할 예정이니 꼭 팔로우 해주세요.

스택 및 큐

배열을 이용한 Stack 구현

사용해야 하는 요소의 최대 개수를 알아야 하는 배열의 문제, 크기를 예측할 수 없다면 linkedlist를 사용하세요.

스택은 마지막 요소만 가져올 수 있고 첫 번째 입력이 마지막 출력임을 의미합니다.

int stack[max];
int top = -1; // mean stack is empty
void push(int item) 
{
    if (top == max-1) printf("overflow");
    else stack[++top] = item; // ++top will increment top first
    return;
}

int pop()
{
    int temp
    if(top == -1) 
    {
        printf("underflow");
        return -1;
    }
    else temp = stack[top--];
    return temp;
}

스택의 연결된 목록 구현

헤드는 새 노드에 연결됩니다.

struct node
{
    int i;
    struct node *link;
};

void push(int item)
{
    struct node *p = (struct node*)malloc(sizeof(struct node));
    if(p == NULL)
    {
        printf("error of malloc");
        return;
    }
    p->data = item;
    p->link = head;
    head = p;
}

추진 시간은 O(1)

int pop()
{
    int item;
    struct node *p;
    if(head == NULL)
    {
        printf("underflow");
        return -1;
    }
    item = head->i;
    p = head;
    head = head->next;
    free(p);
    return item;
}

팝은 O(1)

순환 배열을 사용하는 대기열

원형 배열인 경우에도 원형 배열로 시각화합니다.

전면과 후면은 모두 0 요소를 가리킵니다. 4개의 정수 배열이 있다고 가정해 보겠습니다.

첫 번째 유형 후면이 이미 n-1에 다시 도달하면 후면이 이동할 요소를 넣어야 합니다+1. n-1에 배치해야 하므로 (후면+1) mod n을 사용합니다. 후면 점선 의미 여기에서 통과합니다. 0에서 n-1로 시작합니다.

// delete element
int dequeue()
{
    if(front==rear)
    {
        printf("Q is empty");
        return -1;
    }
    else
    {
        front = (front+1) mod n;
        item = q[front];
        return item;
    }
}

// insert element
void enqueue(item)
{
    rear = (rear+1) mod n;
    if(front == rear)
    {
        printf("Q is full");
        if(rear == 0 ) rear = n-1;
        else rear = rear-1;
        return;
    }
    else
    {
        q[rear] = item;
        return;
    }
}

다음과 같은 경우 대기열이 가득 찰 것입니다.
(rear+1) mod n == front
다음과 같은 경우 대기열이 비어 있습니다.
rear == front