Lists

1차원 데이터로써 데이터들을 나열해논 것이다.각각의 데이터들이 어떤식으로 나열되어 있는지에 따라 array 방식과 linked list 방식으로 나뉜다.

Array

• 배열로 리스트를 구현하는 방법이고 사용법이 간단하다. 몇 번째 칸에 무슨 정보를 넣는지만 지정해주면 되고 출력도 쉽게 할 수 있다.

• 하지만 칸과 칸 사이에 다른 정보를 삽입하거나 삭제할 때 이 방법으로는 구현하기가 어렵다.

• 또 배열은 항목의 개수에 제한이 있으므로 지정한 개수만큼만 정보를 넣을 수 있다.

Linked list

• 구현이 조금 복잡하다. 그 이유로는 다른 정보와 연결을 해주는 작업도 해야 하기 때문이다.

• 항목과 항목을 연결하는 방식이기 때문에 정보의 삽입과 삭제가 간편하다.
  따라서 크기도 제한되지 않는다.

Stack

• <Stack>헤더파일 필요

값들을 저장하는 방법 중 차례로 쌓는 방법이다.
입,출력이 한군데로만 가능한 컨테이너로 LIFO (Last In, First Out)의 법칙을 따른다. 즉, 꺼낼 수 있는(삭제하는) 값은 그 때 가장 최근에 넣은 값으로 한정된다.

Using an Array

(non-circular buffer)

One-Dementional Array
(datatype) stack[stack_size]

Variable top : 현재 스택의 정보가 있는 층계라 보면 된다. 예를 들어 임의의 숫자가 써있는 접시 5개를 순서대로 쌓았을 때, 맨 위의 접시는 5번째이므로 top=5가 된다.

initially top = -1 (empty stack)
top=-1일때 접시가 없는것과 마찬가지니 그 스텍은 비어있음

자주 사용하는 함수

• push(element) : 스택에 값을 넣는다. 삽입후 top값이 +1 증가한다.
• pop() : 인자를 받지 않지만 마지막으로 넣은 값을 리턴. top값이 -1 감소한다.
• top() : 제일 상단의 값을 꺼내지 않고 리턴만 한다.
• stack_full() : top이 리스트의 꼭대기인지(스택이 꽉 찼는지) 판별. 꽉 차있다면(참) 1 리턴, 그렇지 않으면 0(거짓)을 리턴한다.
• stack_empty() : top이 -1인지(스택이 비어있는지) 판별. -1이면(참) 1, 거짓이면 0을 리턴한다.

Queue

FIFO(First In First Out)의 법칙을 따르며 먼저 넣은 값을 먼저 꺼내는(삭제하는) 방법이다.

Using an Array

non-circular buffer

One-Dementional Array
(datatype) queue[queue_size]

Variable top하나만으로 충분한 스택과 달리 Front와 Rear가 있다. 예를 들어 종이컵이 나오는 기계에 임의의 숫자가 써있는 10개의 컵을 넣었을 때 맨 처음 넣은 종이컵이 front(=0)이고 마지막에 넣은 컵은 rear(=10)이 된다.

initially front = rear = -1 (empty queue) 스택과 마찬가지로 비어있는 큐일땐 front와 rear가 -1이다.

하지만 처음 값이 삽입되었을 땐 front와 rear값 둘다 +1 해서 0으로 바뀌고 그 이후의 삽입될땐 rear값만 늘어난다.

• enqueue(element) : 큐에 값을 넣는다. rear값이 +1 된다.
• dequeue() : 입력값은 없어도 현재 front값 번째에 있는(종이컵에 써있는 임의의 숫자)를 리턴한다.
• queue_full() , queue_empty() : 스택의 경우와 마찬가지로 rear값으로 큐가 꽉 찼는지 비었는지 판단한다.

Circular Queue(Ring Buffer)

---

Trying

#include <stdio.h>
#define MAX_SIZE 10

// global variables
int stack[MAX_SIZE];
int top = -1;

int stack_full()
{
    if (top >= MAX_SIZE - 1)
        return 1;
    return 0; // return 0 only if the above condition is false
}

int stack_empty()
{
    if (top == -1)
        return 1;
    return 0; // return 0 only if the above condition is false
}

void push(int x)
{
    top++;
    stack[top] = x;
}

int pop()
{
    int temp = stack[top];
    top--;
    return temp;
}

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

// helper function: run a series of pushes
// input arguments: int arr[] <- an array from which input values are taken
// input arguments: int num <- total number of elements to push
void run_pushes(int arr[], int num)
{
    for (int i = 0; i < num; i++)
    {
        printf("push(%d) , ", arr[i]);
        if (!stack_full())
        { // if stack is not full (!1 = 0)
            push(arr[i]);
        }
        else
        {
            printf("stack full! ");
        }
        print_stack();
    }
}

// helper function: run a series of pops
// input argument: int num <- total number of elements to pop
void run_pops(int num)
{
    int value;
    for (int i = 0; i < num; i++)
    {
        printf("pop() ");
        if (!stack_empty())
        { // if stack is not empty (!1 = 0)
            value = pop();
            printf("-> %d , ", value);
        }
        else
        {
            printf("stack empty! ");
        }
        print_stack();
    }
}

int main()
{
    int numbers[] = {3, 9, 4, 5, 2, 1, 6, 8, 7, 5, 8};
    print_stack();
    run_pushes(numbers, 5);
    run_pops(3);
    run_pushes(numbers, 10);
    run_pops(11);
}

---

#include <stdio.h>
#define MAX_SIZE 10
 
// global variables
int queue[MAX_SIZE];
int front = -1;
int rear = -1;

int queue_full() {
    if(rear >= MAX_SIZE - 1)
        return 1;
    return 0; // return 0 only if the above condition is false
}

int queue_empty() {
    if(front == -1 || front > rear) // front cannot be greater than rear
        return 1;
    return 0; // return 0 only if the above condition is false
}

void enqueue(int x) {
    rear++;
    queue[rear] = x;
    if(front == -1) // increase front only initially
        front++;
}

int dequeue() {
    int temp = queue[front];
    front++;
    return temp;
}

// helper function: print the current queue
void print_queue() {
    printf("queue = ");
    for(int i=front; i<=rear; i++)
        printf(" %d", queue[i]);
    printf(" (front=%d, rear=%d)\n", front, rear);
}

// helper function: run a series of enqueues
// input arguments: int arr[] <- an array from which input values are taken
// input arguments: int num <- total number of elements to enqueue
void run_enqueues(int arr[], int num) {
    for(int i=0; i<num; i++) {
        printf("enqueue(%d) , ", arr[i]);
        if(!queue_full()) { // if queue is not full (!1 = 0)
            enqueue(arr[i]);
        }
       else {
            printf("queue full! ");
       }
       print_queue();
    }
}

// helper function: run a series of dequeues
// input argument: int num <- total number of elements to dequeue
void run_dequeues(int num) {
    int value;
    for(int i=0; i<num; i++) {
        printf("dequeue() ");
        if(!queue_empty()) { // if queue is not empty (!1 = 0)
            value = dequeue();
            printf("-> %d , ", value);
        }
        else {
            printf("queue empty! ");
        }
        print_queue();
    }
}

int main() {
    int numbers[] = {3, 9, 4, 5, 2, 1, 6, 8, 7, 5, 8};
    print_queue();
    run_enqueues(numbers, 5);
    run_dequeues(3);
    run_enqueues(numbers, 10);
    run_dequeues(11);
    run_enqueues(numbers, 3);
}