3. 스택과 큐

스택 (Stack)

LIFO (Last-in, First-out)

리스트 한 쪽에서만 삽입과 삭제를 수행하는 자료구조

처음 삽입된 데이터가 가장 나중에 제거된다.

 

int stack[MAX_SIZE];
int top = -1;

void push(int item){
    if(top >= MAX_SIZE-1) stackFull();
    stack[++top = item;
}

int pop(){
    if(top == -1) return stackEmpty();
    return stack[top--];
}

 

	top		stack
push(A)	0		A C
push(B)	1		B
pop()	0
pop()	-1
pop()	stackEmpty()
push(C)	0

 

큐 (queue)

FIFO (First-in, First-out)

리스트에서 먼저 삽입된 데이터가 가장 먼저 삭제되는 자료구조다.

• 삽입되는 곳 : rear
• 삭제되는 곳 : front

 

int rear = 0;
int front = 0;
int queue[MAX_SIZE];

void addq(int item){
    rear = (rear+1);
    if(front == rear) queueFull();
    queue[rear] = item;
}

int deleteq(){
    if(front == rear) return queueEmpty();
    front = (front + 1) % MAX_SIZE;
    return queue[front];
}

 

원형 큐

	front	rear
addq(A)	0	1
addq(B)	0	2
addq(C)	0	3
deleteq()	1	3
deleteq()	2	3
addq(D)	2	4
addq(E)	2	0
addq(F)	2	1
addq(G)	2	2 -> queueFull() * 하나 비었지만 Full!

 

수식의 계산

int t;
int a=1;
int b[3] = {0, 1, 2};
t = &b[2];
if(*t + 2/a || a++ << 2 ^ !a && ++b[2] != 0);

1. b[2] = 2
2. a++ = 2
3. *t = 2
4. !a = 0
5. ++b[2] = 3
6. 2/a = 2
7. (3) + (6) = 4
8. (2) << 2 = 8
9. (8) ^ (4) = 1
10. (5) != 0 = True
11. (9) && (10) = True
12. (7) || (11) = True

 

후위 표기식의 연산

후위 표기식

연산자가 피연산자 뒤에 위치하는 표기법

 

후위 표기식 연산 방법

1. 식을 괄호로 묶는다.
2. 이항 연산자들을 모두 그들의 오른쪽 괄호와 대치
3. 모든 괄호 삭제

ex1) 2+3*4

1. (2 + (3 * 4))
2. (2 (3 4 * +
3. 2 3 4 * +

ex2) 8 / 2 - 3 + 4 * 2

1. (((8 / 2 ) - 3 ) + ( 4 * 2 ) )
2. ((( 8 2 / 3 - ( 4 2 * +
3. 8 2 / 3 - 4 2 * +

 

	stack
Token	[0]	[1]	[2]	top
8	8			0
2	8	2		1
/	4			0
3	4	3		1
-	1			0
4	1	4		1
2	1	4	2	2
*	1	8		1
+	9			0
eos

return 9;

 

중위표기에서 후위표기로의 반환

ex1) a + b * c

1. (a + ( b * c ) )
2. (a (b c * +
3. a b c * +

	stack
Token	[0]	[1]	[2]	[3]	top	output
a	eos				0	a
+	eos	+			1	a
b	eos	+			1	a b
*	eos	+	*		2	a b
c	eos	+	*		2	a b c
eos	eos					a b c * +

 

ex2) a * ( b + c ) / d

	stack
Token	[0]	[1]	[2]	[3]	Top	output
a	eos				0	a
*	eos	*			1	a
(	eos	*	(		1	a
b	eos	*	(		1	a b
+	eos	*	(	+	2	a b
c	eos	*	(	+	2	a b c
)	eos	*			1	a b c +
/	eos	/				a b c + *
d	eos	/				a b c + * d
eos	eos					a b c + * d /