Stacks and queues (array-backed)

English

Two ways to hold items

A stack and a queue both hold a line of items, but they differ in which item comes out next.
A stack is LIFO: Last In, First Out — like a pile of plates.
A queue is FIFO: First In, First Out — like a line of people.

한국어

두 가지 항목 저장 방식

스택(stack) 과 큐(queue) 은 모두 항목들의 줄(line)을 유지하지만, 어떤 항목이 먼저 나올지에서 차이가 있습니다.
스택은 LIFO: Last In, First Out — 접시 더미(pile of plates)와 같습니다.
큐는 FIFO: First In, First Out — 사람 줄(people line)과 같습니다.

English

A stack is LIFO

push adds an item on top. pop removes and returns the top item. peek looks at the top without removing it.
The last item you pushed is the first one you pop.
We store the items in an array data and an index top that counts how many are in.

한국어

스택은 LIFO입니다

push는 항목을 맨 위에 더합니다. pop은 맨 위(top) 항목을 제거하여 반환합니다. peek은 제거하지 않고 맨 위 항목만 봅니다.
마지막으로 push한 항목이 가장 먼저 pop됩니다.
항목들은 배열 data와 내부 개수를 세는 인덱스 top에 저장됩니다.

English

Array-backed stack

With top as the count, the top item is at data[top - 1].
push: write at data[top], then top++. pop: top--, then return data[top].
(For these tasks the array is big enough; you do not need to check for "full".)

한국어

배열 기반 스택(array-backed stack)

top가 개수(count)라면, 맨 위(top) 항목은 data[top - 1]에 위치합니다.
push: data[top]에 쓰기, 이후 top++. pop: top--, 이후 data[top] 반환.
(이 작업들에서는 배열 크기가 충분히 커서 '满了' 상태 검사는 필요 없습니다.)

English

A queue is FIFO

enqueue adds an item at the back. dequeue removes and returns the item at the front.
The first item you enqueue is the first one you dequeue.
We keep two indexes: front (next to leave) and back (next free slot).

한국어

큐는 FIFO입니다

enqueue는 항목을 뒤에 추가합니다. dequeue는 앞의 항목을 제거하여 반환합니다.
첫 번째로 enqueue된 항목이 가장 먼저 dequeue됩니다.
두 개의 인덱스를 유지합니다: front (나갈 차례인 next to leave)와 back (다음 빈 슬롯 next free slot).

English

Array-backed queue

enqueue: write at data[back], then back++. dequeue: read data[front], then front++, and return it.
front chases back as items come and go.
(For these tasks the array is big enough; you do not need to wrap around or check for "empty".)

한국어

배열 기반 큐(array-backed queue)

enqueue: data[back]에 쓰기, 이후 back++. dequeue: data[front] 읽기, 이후 front++, 그리고 이를 반환합니다.
항목이 들어오고 나감에 따라 front가 back을 쫓아갑니다.
(이 작업들에서는 배열 크기가 충분히 커서 원형(wrap around)이나 '빈(empty)' 상태 검사는 필요 없습니다.)

English

Common mistakes

A stack is last-in-first-out; a queue is first-in-first-out.
Check the structure is not empty before you pop or dequeue.

한국어

흔한 실수

스택은 last-in-first-out이고, 큐는 first-in-first-out입니다.
pop하거나 dequeue하기 전에 구조체가 비어 있지 않은지 확인하십시오.

English

Now you try

The Stack and Queue structs are given in the starter. Use s->top, q->front, and q->back.
Do not write a main — the checker provides one.

한국어

이제 직접 해보기

Stack와 Queue 구조체는 스타터에 이미 제공되어 있습니다. s->top, q->front, 그리고 q->back를 사용하십시오.
main을 작성하지 마세요; 검증程序가 제공해 줍니다.

Explore · ⁨탐색하기⁩

Stacks and queues

A stack is LIFO; a queue is FIFO. Step through the operations.

The Stack struct (with data and a count top) is given. Complete void push(Stack *s, int v) and int pop(Stack *s) so the stack is LIFO. Do not write a main.

typedef struct {
    int data[64];
    int top;
} Stack;

/* push and pop so the stack is LIFO. Do not write main(). */
void push(Stack *s, int v) {
    /* store v at data[top], then top++ */
}

int pop(Stack *s) {
    return 0;   /* top--, then return data[top] */
}

Click Run to see the output here. · ⁨출력을 보려면 '실행'을 클릭하세요.⁩

The Stack struct is given. Complete int peek(const Stack *s) so it returns the top item without removing it. Assume the stack is not empty. Do not write a main.

typedef struct {
    int data[64];
    int top;
} Stack;

/* Return the top item without removing it. Do not write main(). */
int peek(const Stack *s) {
    return 0;   /* the top item is at data[top - 1] */
}

Click Run to see the output here. · ⁨출력을 보려면 '실행'을 클릭하세요.⁩

The Queue struct (with data, front, and back) is given. Complete void enqueue(Queue *q, int v) and int dequeue(Queue *q) so the queue is FIFO. Do not write a main.

typedef struct {
    int data[64];
    int front;
    int back;
} Queue;

/* enqueue and dequeue so the queue is FIFO. Do not write main(). */
void enqueue(Queue *q, int v) {
    /* store v at data[back], then back++ */
}

int dequeue(Queue *q) {
    return 0;   /* read data[front], then front++ */
}

Click Run to see the output here. · ⁨출력을 보려면 '실행'을 클릭하세요.⁩

Two ways to hold items

두 가지 항목 저장 방식

A stack is LIFO

스택은 LIFO입니다

Array-backed stack

배열 기반 스택(array-backed stack)

A queue is FIFO

큐는 FIFO입니다

Array-backed queue

배열 기반 큐(array-backed queue)

Common mistakes

흔한 실수

Now you try

이제 직접 해보기

Stacks and queues

Handout · ⁨교재 자료⁩

Log in or create account · ⁨로그인 또는 계정 만들기⁩

Your subject · ⁨현재 과목⁩

All sections · ⁨모든 섹션⁩

Feedback & help · ⁨피드백 및 도움말⁩