스택(Stack)

• top에서 모든 삽입과 삭제가 일어나는 순서 리스트
• 후입선출(Last-In-First-Out)

• PUSH

void	push(int	item)	{	//전역	stack에	item을	삽입
		if(top	>=	MAX-1)
					stackFull();
		stack[++top]	=	item;
}

• POP

int	pop()	{	//stack의	최상위	원소를	삭제하고	반환
		if(top	==	-1)	
					stackEmpty();
		return	stack[top--];
}

후위표기수식 계산법

• $식 X = ((A + B) * (C - D) / E) + (F * G)$

1. 전위 표기법
   • X + / + A B – C D E F G
2. 중위 표기법
   • A + B C - D / E + F G
3. 후위 표기법
   • X A B + C D - E / F G + =

(선형)큐

한쪽 끝에서 push가 일어나고 그 반대쪽 끝에서 pop이 일어나는 순서리스트

• 선입선출(First-In-First-Out)

• 삽입

  void	addq(int	queue[],	int	item)	{	//삽입
  		if(rear	==	MAX-1)	//꽉찼으면
  					queueFull();
  		queue[++rear]	=	item;
  }

  int	is_full(int	queue[])	{
  			if(rear	==	MAX-1)	return	1;
  			else	return	0;
  }

• 삭제

  int	deleteq(int	queue[])	{
  		if(front	==	rear)	//비었으면
  					queueEmpty();
  		return	queue[++front];
  }

  int	is_empty(int	queue[])	{
  			if(front	==	rear)	return	1;
  			else	return	0;
  }

원형큐

큐가 배열의 끝을 둘러싸게 함

• 큐에서 MAX-1개의 원소를 삽입할 수 있음(포화상태와 공백상태의 구분을 위함)
• 장점 : 원소의 이동 없이 오버플로우 문제 해결
• 반드시 빈 방 하나가 있어야 함

• 삽입

void	addq(int	queue[],	int	item)	{	//삽입
		rear	=	(rear+1)	%	MAX;
		if(rear	==	front)	
					queueFull();
		queue[rear]	=	item;
}

• 삭제

int	deleteq(int	queue[])	{	//삭제
		if(front	==	rear)	//비었으면
					queueEmpty();
		front	=	(front+1)	%	MAX;
		return	queue[front];
}