Computer ScienceData Structure

5. 스택과큐

a. 스택 Stack

차례대로 삽입하고 최근에 저장된 값을 삭제(FILO)

push스택에 값 추가
pop가장 나중에 push된 값을 스택에서 제거하고 반환
top가장 나중에 push된 값을 제거하지 않고 반환
__len__스택의 저장된 요소 갯수를 반환
isEmpty스택에 요소가 존재하는지 참거짓
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# stack_queue.py 에 저장
class Stack:
	def __init__(self):
		self.items = []	# 데이터 저장을 위한 리스트 준비
	def push(self, val):
		self.items.append(val)
	def pop(self):
		try:	# pop할 아이템이 없으면
			return self.items.pop()
		except IndexError:	# indexError 발생
			print("Stack is empty")
	def top(self):
		try:
			return self.items[-1]
		except IndexError:
			print("Stack is empty")
	def __len__(self):	# len()로 호출하면 stack의 item 수 반환
 		return len(self.items)
	def isEmpty(self):
		return self.__len__() == 0

# for test
S = Stack()
S.push(10)
S.push(2)
print(S.top())
print(S.pop())
print(len(S))
print(S.isEmpty())

b. 스택 활용

b-1. 괄호짝 맞추기

입력 값 : 괄호로 이뤄져 있는 문자열 ex. ()()()

반환 값 : 괄호 짝이 맞는지 참 거짓 ex. True

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Stack:
	def __init__(self):
		self.item=[]
	def push(self, a):
		self.item.append(a)
	def pop(self):
		try:
			return self.item.pop()
		except IndexError:
			print('Stack is empty.')
	def top(self):
		try:
			return self.item[-1]
		except IndexError:
			print('Stack is empty.')
	def __len__(self):
		return len(self.item)
	def isEmpty(self):
		return len(self.item)==0
	
# pseudo code
def parChecker(parSeq):
	S=Stack()
	for i in parSeq:
		if i =='(':
			S.push('(')
		elif i ==')':
			if S.isEmpty():
				print(False)
				return False
			else : 
				S.pop()
	if S.isEmpty():
		print(True)
		return True
	else : 
		print(False)
		return False
parSeq=list(input())
parChecker(parSeq)

b-2. infix 수식을 postfix로 바꾸기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Stack:
	def __init__(self):
				self.items = []
	def push(self, val):
				self.items.append(val)
	def pop(self):
		try:
			return self.items.pop()
		except IndexError:
			print("Stack is empty")
	def top(self):
		try:
			return self.items[-1]
		except IndexError:
			print("Stack is empty")
	def __len__(self):
		return len(self.items)
	def isEmpty(self):
		return self.__len__() == 0
def infix_to_postfix(infix):
	opstack = Stack()
	outstack = []
	token_list = infix.split()
			# 연산자의 우선순위 설정
	prec = {}
	prec['('] = 0
	prec['+'] = 1
	prec['-'] = 1
	prec['*'] = 2
	prec['/'] = 2
	prec['^'] = 3
	for token in token_list:
		if token == '(':
			opstack.push(token)
		elif token == ')':
			while True:
				if opstack.top()=='(':
				    opstack.pop()
				    break
				else :
					outstack.append(opstack.pop())
		elif token in '+-/*^':
			while True:
				if opstack.isEmpty():
					opstack.push(token)
					break
				elif prec[opstack.top()]>=prec[token]:
					    outstack.append(opstack.pop())
				else:
					opstack.push(token)
					break
		else: # operand일 때
			outstack.append(token)
			# opstack 에 남은 모든 연산자를 pop 후 outstack에 append
	for i in range(opstack.__len__()):
		outstack.append(opstack.pop())
	return " ".join(outstack)

infix_expr = input()
postfix_expr = infix_to_postfix(infix_expr)
print(postfix_expr)

b-3. Postfix 계산

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Stack:
	def __init__(self):
		self.items=[]
	def push(self, val):
		return self.items.append(val)
	def pop(self):
		try:
			return self.items.pop()
		except IndexError:
			print('stack is empty')
	def top(self):
		try:
			return self.items[self.items.len()-1]
		except IndexError:
			print('stack is empty')
	def __len__(self):
		return self.items.len()
def compute_postfix(postfix):
	opstack = Stack()
	token_list = postfix.split()
	for i in token_list:
		if i in '+-*/^':
			a=opstack.pop()
			b=opstack.pop()
			if i =='+':
				opstack.push(a+b)
			elif i =='-':
				opstack.push(b-a)
			elif i =='*':
				opstack.push(a*b)
			elif i =='/':
				opstack.push(b/a)
			elif i =='^':
				opstack.push(b**a)
		else:
			opstack.push(int(i))
	print('%.4f'%opstack.pop())

postfix=input()
compute_postfix(postfix)

c. 인터뷰 문제

1. 스택을 하나 혹은 두개 사용해 push, pop, min 세 연산 모두 O(1) 시간에 수행되도록 하려면?

2. 스택 두 개를 써서 큐를 구현해라.(enqueue, dequeue를 구현하라)

a. 큐 Queue

가장 최근에 저장된 값 다음에 저장.

반환은 가장 먼저 저장된 값부터. FIFO(First in First out)원칙.

enqueue큐의 오른쪽에 삽입(push와 같음)
dequeue가장 왼쪽에 저장된 값을 삭제 후 리턴
front가장 왼쪽에 저장된 값을 삭제하지 않고 리턴
isEmpty큐가 비어져있는지 참거짓
len큐의 요소 갯수 반환
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Queue:
     def __init__(self):
         self.items=[]
         self.front_index=0 #다음 dequeue될 값의 인덱스
     def enqueue(self, val):
         self.items.append(val)
     def dequeue(self):
         if len(self.items)==0 or self.front_index==len(self.items):
             print("Queue is empty")
         else : 
             x = self.items[self.front_index]
             self.front_index +=1
             return x
     def front(self):
         if len(self.items) ==0 or self.front_index == len(self.items):
             print("queue is empty")
         else:
             return self.items[self.front_index]
     def __len__(self):
         return len(self.items)-self.front_index
     def isEmpty(self):
         return len(self)

dequeue를 상수시간에 실행하기 위해선 dequeue가 될 값의 인덱스를 저장하고 관리해야 한다.

-> dequeue가 되면, 그 값을 실제로 지우는 것이 아닌 front_index값을 하나 늘려가며 다음 dequeue 될 예정 값의 인덱스를 가르키도록 관리한다.

실제로 dequeue될 때마다 값을 삭제시키면, 모든 값들을 한 칸씩 왼쪽으로 이동하는 시간이 소요되게 된다.O(n)

a-1. 큐 활용 : Josephus game

1
2
3
4
5
6
7
8
9
10
import Queue #큐 클래스 import. 이 부분은 달라질 수 있음
def Josephus(n, k):
    Q=Queue()
    for v in range(1, n+1):
        Q.enqueue(v)
    while len(Q)>1:
        for i in range(1, k):
            Q.enqueue(Q.dequeue())
        Q.dequeue() #k번째 수 제거
    return Q.dequeue()

b. Dequeue

왼쪽과 오른쪽에서 모두 삽입과 삭제가 가능한 큐

두 가지 버전의 pop과 push 연산을 구현

python collections 모듈에 deque 클래스로 구현되어 있음(덱으로 발음)

오른쪽 push : append / 왼쪽 push : appendleft

오른쪽 pop : pop / 왼쪽 pop : popleft

Share