자료구조 문제 정리 (2) 스택, 큐

 

1. 스택

(1)

자료의 삽입과 삭제가 포인터에 의해 정해진 위치에서 수행되는 것을 제한된 자료구조라 하고, 스택과 큐가 해당된다.

• 스택은 후입선출(LIFO) 형태로 포인터 top이 가리키는 곳에서만 삽입과 삭제를 수행한다
• 큐는 선입선출(FIFO) 형태로 삽입은 포인터 rear가 가리키는 곳에서, 삭제는 포인터 front가 가리키는 곳에서 수행한다.
• 스택은  같은 쪽에서 삽입과 삭제가 수행되고, 큐는 서로 다른 쪽에서 삽입과 삭제가 수행된다.
• 스택과 큐의 주요 작업은 삽입(push) 삭제(pop)이며 시간복잡도는 O(1)이다.
• 스택과 큐 모두 배열이나 연결 리스트로 구현 가능하다.
• 스택은 서브루틴 호출이나 인터럽트 발생 시의 복귀 주소 관리, 순환적 프로그램 처리, 후위 표기 방식, 이진트리 순회, 깊이 우선 탐색 등에 사용된다.
• 큐는 운영체제의 스케줄링, 스풀링, 너비 우선 탐색, 처리기 할당 등에 사용된다.

[삽입, 삭제 연산]

(2)

배열로 구현한 스택 자료구조의 push() 연산과 pop() 연산에 들어가는 코드는?

void push(int d) //삽입 연산
	if( IsFull() ) 
    	printf("STACK FULL\n");
        else
        a[++top] = d; 
        //삽입을 위해서는 top을 먼저 1 증가한 후 삽입을 수행한다
        }

int pop() { //삭제 연산
	if( IsEmpty() )
    	printf("STACK EMPTY\n");
        else
        return a[top--]; 
        //삭제를 위해서는 top이 가리키고 있는 값을 return한 후 top을 1 감소한다.
        }

 

자바로 구현하는 경우는 다음과 같다

public void push(int x) {
	buf[++top] = x;
    }
    
public int pop() {
	return buf[top--];
    }

 

[스택에 삽입]

(3)

스택에서 삽입 연산을 push, 삭제하여 출력하는 연산을 pop이라 할 경우, 순서화된 원소 A,B,C,D에 대해서

다음 순서로 스택 연산을 수행하는 경우 출력되는 결과는?

push, push, pop, push, push, pop, pop, pop

 

push 연산은 스택에 데이터를 삽입하는 연산이고, pop 연산은 스택에서 데이터를 삭제(출력)하는 연산이다.

이 문제에서 삽입되는 순서는 A B C D로 정해져 있다.

각 연산 수행 시의 스택 내용은 다음과 같다.

pop 연산이 수행되어 출력되는 데이터의 순서는 B D C A 이다.

PUSH	PUSH	POP	PUSH	PUSH	POP	POP	POP
				D
	B		C	C	C
A	A	A	A	A	A	A

 

[꺼낼 수 없는 스택 순서]

(4)

스택의 입력으로 4개의 문자 D,C,B,A가 순서대로 들어올 때, 스택 연산 PUSH와 POP에 의해서 출력될 수 없는 결과는?

 

4개의 문자의 삽입 순서는 D,C,B,A 이다.

즉 B를 출력하기 위해서는 이미 D와 C가 먼저 스택에 삽입되어야 한다.

C가 나중에 삽입되었으므로 이 경우에는 D보다 먼저 출력되어야 한다. BDCA 순서로는 출력할 수 없다.

 

 

전위 <-> 후위 표기식 공부하기

 

[스택의 연산]

(5)

후위(postfix) 형식으로 표기된 다음 수식을 스택(stack)으로 처리하는 경우에, 스택의 탑(TOP) 원소의 값을

올바르게 나열한 것은? 단, 연산자(operator)는 한 자리의 숫자로 구성되는 두 개의 피연산자(operand)를 필요로 하는 이진(binary) 연산자이다.

4 5 + 2 3 * -

 

피연산자는 스택에 삽입한다.

연산자를 읽을 경우 스택에서 피연산자 2개를 출력하여 연산 후 결과를 스택에 삽입한다.

				3
	5		2	2	6 (곱하기)
4	4	9 (더하기)	9	9	9	3

 

4, 5, 9, 2, 3, 6, 3 순서로 출력된다 (마지막 연산은 -3이 아니고 3인것 주의하기)

 

(6)

다음은 postfix 수식이다. 이 postfix 수식은 스택을 이용하여 연산을 수행한다. 그리고 ^는 지수 함수 연산자이다.

처음 *(곱하기 연산) 계산이 되고 난 후 스택의 top과 top-1에 있는 두 원소는 무엇인가?

27 3 3 ^ / 2 3 * -

 

		3				3
	3	3	27 (지수 연산)		2	2	6(곱셈)
27	27	27	27	1 (나눗셈)	1	1	1	-5(뺄셈)

 

처음 곱하기 연산이 되고 난후 top은 6이고 top-1은 1이다.

 

(7)

다음 전위(prefix) 표기식의 계산 결과는?

+ - 5 4 X 4 7

 

전위 표기식의 연산은 [ 연산자 피연산자(데이터) 피연산자 ] 묶음을 한 단위로 처리된다

처리된 결과는 피연산자로 인식된다.

맨 처음 연 데 데 나오는 (5-4)를 데이터로 묶고

그 다음 연 데 데 나오는 (4X7)을 데이터로 묶고

1+28을 수행하면 답은 29이다.

 

2. 큐

(1)

• 큐는 FIFO 방식으로 삽입과 삭제가 서로 다른 쪽에서 수행되는 제한된 자료구조이다. 
• Front는 큐의 앞쪽을 가리키는 포인터로 데이터의 삭제에 사용된다.
• Rear는 큐의 뒤쪽을 가리키는 포인터로데이터의 삽입에 사용된다.
• 주요 작업은 삽입과 삭제이며 시간 복잡도는 O(1)이다.
• 배열이나 연결리스트로 구현 가능하다.
• 큐의 크기는 배열을 사용할 경우 미리 정해져있고 연결리스트를 사용할 경우에는 정해져 있지 않다.

EX)

미로 탐색 문제에서 가장 최근에 방문한 길들을 기억할 때 : 스택을 사용한다.

키보드에서 입력된 키 값을 잠시 저장할 때 : 키보드에서 입력된 순서대로 입력되어야 하므로 큐를 사용한다.

 

(2)

원형 큐에 대해서 삽입과 삭제가 일어날 때 수행이 완료된 후 큐의 상태는?

0	1	2	3	4	5
	A	B

1. 원소 C 삽입
2. 원소 D 삽입
3. 두 개의 원소 삭제
4. 원소 E 삽입
5. 하나의 원소 삭제
6. 원소 F 삽입

0	1	2	3	4	5
	A	B	C

0	1	2	3	4	5
	A	B	C	D

0	1	2	3	4	5
			C	D

0	1	2	3	4	5
			C	D	E

0	1	2	3	4	5
				D	E

0	1	2	3	4	5
F				D	E

최종 결과는 위와 같으며, 원소 F를 삽입할 때 큐의 0번에 삽입되는 것을 주의하자

 

(3)

원형 큐에 한 객체를 입력하는 알고리즘에 대한 의사코드

(객체는 rear 쪽에 입력되고 front 쪽에서 출력되며, M은 큐의 크기를 나타내는 정수이다)

 

삽입을 위해 사용되는 포인터는 rear이다. 원형큐이므로 (rear+1)을 큐의 크기로 나눠 나머지로 rear 값을 수정한다 (front는 삭제할 때 사용한다)

원형 큐에 삽입을 하기 위해 큐가 포화상태인지 검사한다. (삭제를 하기 위해서는 공백 상태인지 검사한다)

그리고 객체를 rear 위치에 입력한다.

1. rear 값을 1 증가 : rear = (rear + 1) % M
2. 큐가 포화 상태인지 검사 : (front == rear)
3. 객체를 rear 위치에 입력

 

(4)

• 리스트의 양쪽 끝에서 노드의 삽입과 삭제가 모두 가능한 선형 리스트로, 리스트의 양쪽 끝 노드를 각각 가리키는 두 개의 포인터를 갖는 자료구조는 데크(deque)이다.
• 데크의 스크롤은 입력 제한, shelf는 출력 제한
• 스택은 리스트의 한쪽 끝에서 노드의 삽입과 삭제가 모두 가능한 선형 리스트이다
• 큐는 리스트의 양쪽 끝 노드를 가리키는 포인터를 가지며 한쪽 끝에서 삽입을 하고 다른 한쪽 끝에서 삭제를 하는 선형 리스트이다.
• 연결리스트로 구현된 스택은 그 크기가 가변적이다.
• 배열로 구현된 스택은 구현이 간단하지만 크기가 고정적이다.
• 원형연결리스트는 한 노드에서 다른 모든 노드로 접근이 가능하다.