[자료구조] 스택 & 큐 - 1(배열) (Stack & Queue Using an Array)

Stack & Queue (Using an Array)

Stack

definition

• LIFO(Last-In-First-Out) 구조
• 나중에 들어간 데이터가 먼저 나오는 구조의 리스트 자료구조

Implementation

1. 배열을 이용하는 방법(global or local)
   • non-circular buffer
   • circular buffer
2. 연결 리스트를 이용하는 방법

Using an Array: non-cicular buffer

• 1차원 배열

• (datatype) stack[stack_size]

• ex) char stack[100]

• variable: top - 0으로 초기화(empty stack)

• 삽입할 때마다 top++

  int main(void)
  {
    int stack[5];
    int top = 0;
    // insert
    stack[top] = 2;
    top++;
    // insert
    stack[top] = 7;
    top++;
    // insert
    stack[top] = 3;
    top++;
    // insert
    stack[top] = 1;
    top++;
    // insert
    stack[top] = 5;
    top++;
    // stack is full(stack_size <= top)
    // If inserting, then overflow
    return 0;
  }

  Using an Array: cicular buffer

• top >= stack_size면 top = 0으로

-> 기존 데이터가 덮어씌워지는 문제 발생

int main(void)
{
    int stack[5];
    int top = 0;
    // insert
    stack[top] = 2;
    top++;
    // insert
    stack[top] = 7;
    top++;
    // insert
    stack[top] = 3;
    top++;
    // insert
    stack[top] = 1;
    top++;
    // insert
    stack[top] = 5;
    top++;
    // stack is full(stack_size <= top)
    top = 0;
    // insert
    stack[top] = 8;

    return 0;
}

Queue

definition

• FIFO(First-In-First-Out 구조)
• 먼저 들어간 데이터가 먼저 나오는 구조의 리스트 자료구조

Implementation

1. 배열을 이용하는 방법(global or local)
   • non-circular buffer
   • circular buffer
2. 연결 리스트를 이용하는 방법

Using an Array: non-cicular buffer

• 1차원 배열
• (datatype) queue[queue_size]
• ex) char queue[100]
• variable: front, rear = 0으로 초기화
• 삽입할 때마다 reat++
• 삭제할 때마다 front++

int main(void)
{
    int queue[3];
    int front = 0;
    int rear = 0;
    // insert
    queue[rear] = 2;
    rear++;
    // insert
    queue[rear] = 7;
    rear++;
    // insert
    queue[rear] = 3;
    rear++;
    // queue is full(queue_size <= rear)
    // If inserting, then overflow
    // delete
    int popData;
    popData = queue[front];
    front++;
    // delete
    popData = queue[front];
    front++;
    // Delete
    popData = queue[front];
    front++;
    // 더 이상 큐를 사용하지 못하는 상태
    // queue_size <= rear = front
    // insert도 delete도 불가능
    return 0;
}

Using an Array: cicular buffer

• front != 0이고 front = rear인 상태에서 insert할 때, rear = 0으로
• front == queue_size이고 rear != 0인 상태에서 delete할 때, front = 0으로

-> 기존 데이터가 덮어씌워지는 문제 발생

int main(void)
{
    int queue[3];
    int front = 0;
    int rear = 0;
    // insert
    queue[rear] = 2;
    rear++;
    // insert
    queue[rear] = 7;
    rear++;
    // insert
    queue[rear] = 3;
    rear++;
    // queue is full(queue_size <= rear)
    // If inserting, then overflow
    // delete
    int popData;
    popData = queue[front];
    front++;
    // delete
    popData = queue[front];
    front++;
    // Delete
    popData = queue[front];
    front++;
    // 더 이상 큐를 사용하지 못하는 상태
    // insert
    rear = 0;
    queue[rear] = 1;
    rear++;
    // delete
    front = 0;
    popData = queue[front];
    front++;

    return 0;
}