순차리스트

● 스택

스택은 한쪽 끝에서만 삽입과 삭제 작업이 일어나므로 제일 나중에 들어온 원소가 제일 먼저 삭제되는 특성을 가지고 있다. ( LIFO : Last-in First-Out )

초기 top의 값을 -1로 초기화 하는 것이 관건!!
#define MAX_STACK_SIZE 100
int stack[MAX_STACK_SIZE];
int top = -1;                                //전역변수

if ( top == -1 )                           -> 스택이 비어있는 상태
if ( top == MAX_STACK_SIZE-1 )    -> 스택이 꽉 차 있는 상태

① 노드 삽입

void push(int item)
{
      if (top >= MAX_STACK_SIZE - 1)
         printf("Stack is overflow !!!\n");
      else {
         top++;
         stack[top] = item;
      }
}

② 노드 삭제

int pop()
{
      if (top == -1)
            printf("Stack is empty!!!");
      else return stack[top--];
}

● 후위표기식 연산 프로그램( 스택 )

표기식 ex )   ab/c-de*+ac*-

#include <stdio.h>
#include <stdlib.h>
#define MAX_EXPR_SIZE 50
#define MAX_STACK_SIZE 30

char pexpr[MAX_EXPR_SIZE];
int stack[MAX_STACK_SIZE];
int top;

int delete_stack();
void add_stack(int data);
int is_operator(char c);
int cal(void);

main()
{
    printf("input the expression as a postfix notation : \n");
    gets(pexpr);
    printf("Evaluation Value : %d\n", cal());
}

int delete_stack()
{
    if ( top == -1 ){
        printf("Stack is empty. \n");
    exit(1);
    }
    return stack[top--];
}

void add_stack(int data)
{
    if ( top >= MAX_STACK_SIZE-1) {
        printf("Stack is full. \n");
        exit(1);
    }
    stack[++top] = data;
}

int is_operator(char c)
{
    if ( c == '+' || c == '-' || c == '*' || c == '/')
        return 1;
    else
        return 0;
}

int cal(void)
{
    char symbol;
    int op1, op2, n=0;
    top = -1;

    symbol = pexpr[n++];
    while ( symbol != '\0') {
        if ( is_operator(symbol)) {
            op2 = delete_stack();
            op1 = delete_stack();

switch ( symbol ) {
    case '+' : add_stack(op1+op2);
        break;
    case '-' : add_stack(op1-op2);
        break;
    case '*' : add_stack(op1*op2);
        break;
    case '/' : add_stack(op1/op2);
        break;
    }
}
else
    add_stack(symbol-'0'); // 스택에 삽입
symbol = pexpr[n++];

}

return delete_stack();

}

● 큐

큐(queue)는 한쪽 끝에서 데이터가 삽입되고 그 반대쪽 끝에서 삭제가 일어나는 순서 리스트이다.
제일 먼저 삽입된 원소가 제일먼저 삭제되기 때문에 선입선출(first-in-first-out : FIFO) 리스트라고도 한다.

#define MAX_QUEUE_SIZE 100
typedef struct {
     int job_num;
     char grade;
} element;
element queue[MAX_QUEUE_SIZE];
int rear = -1;        -> 후방
int front = -1;       -> 전방

front와 rear의 값이 같은 경우 큐가 비어 있는 상태
rear가 MAX_QUEUE_SIZE-1 인 경우 큐가 꽉 찬 상태

① 노드 삽입

void addq(element item)
{
    if ( rear == MAX_QUEUE_SIZE-1)
        printf("QUEUE is full!!");
    else
        queue[++rear] = item;
}

② 노드 삭제

element deleteq()
{

    if (front == rear)
        printf("Queue is Empty");
    else
        return queue[++front];
}

● 원형큐

원형큐는 원형으로 취급하여 큐를 효율적으로 표현이 가능해진다. front는항상 큐의 첫 번째 원소로부터 시계
반대방향으로 하나 앞 위치를 가리키게 한다.
큐와는 다르게 front와 rear 값을 0으로 초기화한다.

#define MAX_QUEUE_SIZE 10
typedef struct {
     int job_num;
     char grade;
} element;
element queue[MAX_QUEUE_SIZE];
int rear = 0;        -> 후방
int front = 0;       -> 전방

① 노드 삽입

void caddq ( element item )
{
    int next_rear = (rear + 1) % MAX_QUEUE_SIZE;
    if ( next_rear == front )
        printf("Queue is Full!!");
    else {
        rear = next_rear;
        queue[rear] = item;
    }
}

② 노드 삭제

element cdeleteq()
{
    if (front == rear)
        printf("Queue is empty!!!");
    else {
        front = (front + 1) % MAX_QUEUE_SIZE;
        return queue[front];
    }
}


● 순차 리스트 구조의 단점

① 리스트의 중간에 자료를 삽입, 삭제하기 어렵다.      ->  삽입과 삭제시 자료의 이동이 필요함
② 리스트의 크기나 모양을 바꾸는데 문제가 있다.       ->  크기를 재설정하고 컴파일 해야함
③ 리스트의 크기가 가변적이라면 최대 크기를 산정해서
    미리 준비해야 하므로 기억장소를 낭비하게 된다.