스택(Stacks)

자료(data element)를 보관할 수 있는 (선형)구조
단, 넣을 때에는 한 쪽 끝에서 밀어 넣어야 하고 -> push
꺼낼 때에는 같은 쪽에서 뽑아 꺼내야 하는 제약이 있음 -> pull
Last in First out의 특징을 가진다.
스택에 데이터를 저장하는 것은 바닥에 책을 쌓고 꺼내는 과정과 유사하다.
stack underflow = 꺼낼 수 없는 것을 꺼내려 할때
stack overflow = 더 넣을 수 없는 상황에서 넣으려 할때 발생하는 오류

스택의 추상적 자료구조 구현

size() 현재 스택에 들어 있는 데이터 원소의 수를 구함
isEmpty() 현재 스택이 비어 있는지를 판단
push(x) 데이터 원소 x를 스택에 추가
pop() 스택의 맨 위 혹은 마지막에 저장된 원소를 제거(리턴하면서)
peek() 스택의 맨 위에 저장된 데이터 원소를 반환(제거하지 않은)

#배열로 구현한 스택
class ArrayStack:
	def __init__(self):
    	self.data = []
    def size(self):
    	return len(self.data)
    def isEmpty(self):
    	return self.size() == 0
    def push(self, item):
    	self.data.append(item)
    def pop(self):
    	return self..data.pop()
    def peek(self):
    	return self.data[-1]

수식의 괄호 유효성 검사

올바른 수식은 스택을 이용해서 살펴볼수 있다.
올바르지 않은 수식을 체크해보면
경우의수가
1.열고 닫지 않는 경우 (A+B
2.열지 않았는데 닫은 경우 A+B)
3.괄호가 쌍을 이루지 않은 경우 {(A+B)]

알고리즘 구상

수식을 왼쪽부터 한 글자씩 읽어서
여는 괄호 - (, {, [를 만나면 스택에 푸시
닫는 괄호 - ), }, ]를 만나면
스택이 비어 있으면 올바르지 않은 수식(2의경우)
스택에서 pop을 해서 쌍을 이루는 여는 괄호인지를 검사하고
쌍이 맞지 않다면 올바르지 않은 수식이다(3의경우)
올바른 수식이라면 검사 후 스택이 비어있어야 한다.(1의경우)

수식의 후위 표기법

중위표기법과 후위 표기법

중위 표기법(infix notation)
연산자가 피연산자들의 사이에 위치
(A + B) (C + D)
후위 표기법(postfix notation)
연산자가 피연산자들의 뒤에 위치
AB + CD +

중위 표현식 -> 후위 표현식

알고리즘 설계를 위한 구상
1.피연산자를 만나면 그대로 표시
2.연산자를 만나면 스택 최상단 연산자와 우선 순위를 비교
지금 넣으려는 연산자의 우선 순위가 스택 최상단의 연산자보다 더 높으면 그대로 push
지금 넣으려는 연산자의 우선 순위가 스택 최상단의 연산자와 비교해 작거나 같다면 스택 최상단의 연산자를 출력하고나서 push
3.시작 괄호가 나오면 스택에 push
4.마무리 괄호가 나오면 스택에서 쌍이 맞는 시작 괄호가 나올때까지 스택 상의 모든 연산자를 pop, 그 후 쌍이 맞는 시작 괄호가 나올경우에 그 괄호를 삭제
5.중위 수식의 끝에 도달했다면 스택에 남아있는 모든 연산자를 pop

연산자의 우선순위(내림차순 정렬)

* or / 
+ or -
() or {} or [ ]

패턴을 통한 알고리즘 설계의 문제점 및 특이사항 체크

[중위] A * B + C
[후위] A B * C +

[중위] A + B * C
[후위] A B C * +

[중위] A + B + C
[후위] A B + C +

[중위] (A + B) * C
[후위] A B + C *

[중위] A * (B + C)
[후위] A B C + *

[중위] (A + B) * (C + D)
[후위] A B + C D + *

[중위] (A + (B - C)) * D
[후위] A B C - + D *

[중위] A * (B - (C + D))
[후위] A B C D + - *

알고리즘 설계를 위한 구상에 문제점은 없음을 확인 가능

알고리즘의 설계
연산자의 우선 순위 설정(괄호는 소괄호만 사용한다고 가정)

prec = {
	'*' :3, '/' : 3, 
	'+' :2, '-' : 2,
	'(' : 1
    }

그외의 부분은 구상과 동일한 과정임

코드 작성과 설명

class ArrayStack:

    def __init__(self):
        self.data = []

    def size(self):
        return len(self.data)

    def isEmpty(self):
        return self.size() == 0

    def push(self, item):
        self.data.append(item)

    def pop(self):
        return self.data.pop()

    def peek(self):
        return self.data[-1]

prec = {
    '*': 3, '/': 3,
    '+': 2, '-': 2,
    '(': 1,
}

def solution(S):
    opStack = ArrayStack()
    answer = ''
    #문자열 S를 왼쪽부터 check한다.
    for check in S:
        #'('와 ')'를 처리해준다.
        if check == '(':
            opStack.push(check)
        elif check == ')':
            while opStack.peek() != '(':
                answer += opStack.pop()
            #마지막으로 남은 '('을 없애주기 위해서 넣어준다.
            opStack.pop()
        #남은 경우의 수는 문자열과 연산자이다.
        else:
            #연산자라면
            if check in prec:
                if opStack.isEmpty():
                    opStack.push(check)
                #연산자의 우선순위를 비교해서 스택의 연산자가 현재 넣으려는 연산자보다 더 크거나 같다면
                elif prec[opStack.peek()] >= prec[check]:
                    #스택안에 연산자가 남아있다면 우선순위 비교를 통해서 꺼내준다.
                    while not opStack.isEmpty() and prec[opStack.peek()] >= prec[check]:
                        answer += opStack.pop()
                    #스택의 연산자 우선순위 비교가 끝나고 나서 현재 넣으려는 연산자를 스택에 넣어준다. 
                    opStack.push(check)
                #더 작다면
                else:
                    opStack.push(check)
            #문자열이라면
            else:
                answer += check
    #S문자열의 모든 문자의 check가 끝났다면 스택 안의 연산자들을 pop해서 넣어준다.
    while not opStack.isEmpty():
        answer += opStack.pop()
        
    return answer

후위 표기 수식 계산

후위 표기식의 계산

[후위] A B + C D +
[중위] (A + B) (C + D)

알고리즘의 설계
후위 표현식을 왼쪽부터 한 글자씩 읽어서
피연산자이면 스택에 push
연산자를 만나면 스택에서 pop -> (1), pop -> (2)
(2) 연산 (1)을 순서대로 계산, 이 결과를 스택에 push
수식의 끝에 도달하면 스택에서 결과를 pop

후위표현 수식 계산

후위표현 수식계산은 3단계로 나누어서 이루어진다.
1.입력받은 중위 표현식의 문자열을 리스트로 변환해주는 작업
2.변환된 리스트를 입력받아 후위 표현식의 리스트로 변환해주는 작업
3.후위 표현식의 리스트를 입력받아 계산하는 작업
다만 이 코드는 비연산자를 숫자로 한정하여 알파벳등의 문자를 입력 받는 경우는 생각하지 않고 괄호 또한 소괄호로 한정하여 진행한다.

각 단계를 코드로 작성해보면 아래와 같다.

1. 중위 표현식의 문자열exprStr을 리스트로 만들어주기

#예시로 보는 입력과 출력 
exprStr = '1 * (7 - (2 + 3))'
tokens = [1, '*', '(', 7, '-', '(', 2, '+', 3, ')', ')']

def splitTokens(exprStr):
    tokens = []
    val = 0
    valProcessing = False
    #모든 문자열을 체크
    for c in exprStr:
    	#빈칸은 패스
        if c == ' ':
            continue
        
        #숫자의 나열을 10진수 val값으로 바꿔주기
        if c in '0123456789':
            val = val * 10 + int(c)
            valProcessing = True
            
        #괄호 또는 연산자를 만나는 경우
        else:
            if valProcessing:
                tokens.append(val)
                val = 0
            valProcessing = False
            tokens.append(c)
    #마지막에 남은 수를 더해준다.
    if valProcessing:
        tokens.append(val)
    
    return tokens

2. 중위 표현식의 리스트를 후위 표현식의 리스트로 만들어주기

#예시로 보는 입력과 출력
tokenList = [1, '*', '(', 7, '-', '(', 2, '+', 3, ')', ')']
postfixList = [1, 7, 2, 3, '+', '-', '*']

class ArrayStack:
    def __init__(self):
        self.data = []

    def size(self):
        return len(self.data)

    def isEmpty(self):
        return self.size() == 0

    def push(self, item):
        self.data.append(item)

    def pop(self):
        return self.data.pop()

    def peek(self):
        return self.data[-1]

def infixToPostfix(tokenList):
    prec = {
        '*' : 3,
        '/' : 3,
        '+' : 2,
        '-' : 2,
        '(' : 1
    }
    
    opStack = ArrayStack()
    postfixList = []
    
    for token in tokenList:
        #피연산자를 리스트에 추가, 피연산자는 문자를 제외한 숫자로 한정
        if type(token) is int:
            postfixList.append(token)
            
        #'('와 ')'를 처리해준다.
        elif token == '(':
            opStack.push(token)
            
        elif token == ')':
            while opStack.peek() != '(':
                postfixList.append(opStack.pop())
            opStack.pop()
        
        #남은 경우인 연산자+-*/를 처리
        else:
            # 스택이 비어있을 경우 스택에 push
            if opStack.isEmpty():
                opStack.push(token)
                
            else:
                #스택에 값이 존재한다면 우선순위 비교를 반복
                while opStack.size() > 0:
                    #연산자의 우선순위를 비교해서 스택의 연산자가 현재 넣으려는 연산자보다 더 크거나 같다면 pop
                    if prec[opStack.peek()] >= prec[token]:
                        postfixList.append(opStack.pop())
                    else:
                        break
                #현재 넣으려는 연산자의 우선순위가 남은 스택의 연산자의 우선순위보다 더 큰경우에 push 
                opStack.push(token)
    
    #입력받은 리스트 안의 모든 원소의 체크가 끝났다면 스택 안의 연산자들을 pop해서 넣어준다.
    while not opStack.isEmpty():
        postfixList.append(opStack.pop())
    
    return postfixList

3. 후위 표현식의 리스트를 계산하는 작업

#예시로 보는 입력과 출력
tokenList = [1, 7, 2, 3, '+', '-', '*']
return -> 2

def postfixEval(tokenList):
    valStack = ArrayStack()
    
    for token in tokenList:
        #피연산자를 만나면 스택에 push
        if type(token) is int:
            valStack.push(token)
            
        #연산자를 만나면 순서를 맞춰서 계산
        elif token == '+':
            n1 = valStack.pop()
            n2 = valStack.pop()
            valStack.push(n2+n1)
        
        elif token == '-':
            n1 = valStack.pop()
            n2 = valStack.pop()
            valStack.push(n2-n1)
            
        elif token == '*':
            n1 = valStack.pop()
            n2 = valStack.pop()
            valStack.push(n2*n1)
            
        elif token == '/':
            n1 = valStack.pop()
            n2 = valStack.pop()
            valStack.push(int(n2/n1))
        
    return valStack.pop()

큐(Queues)

자료(data element)를 보관할 수 있는 (선형) 구조
단, 넣을 때에는 한 쪽 끝에서 밀어 넣어야 하고
꺼낼 때에는 반대 쪽에서 뽑아 꺼내야 하는 제약이 있음
선입선출First in First Out의 특징을 가짐

큐의 추상적 자료구조 구현

1. 배열을 이용하여 구현
   • python 리스트와 메서드들을 이용
2. 연결 리스트를 이용하여 구현
   • 양방향 연결 리스트 이용

연산의 정의

size() - 원소의 수
isEmpty() - 현재 큐가 비어있는 지를 판단
enqueue(x) - 원소 x를 큐에 추가
dequeue() - 맨 앞에 저장된 원소를 제거, 반환
peek() - 맨 앞에 저장된 원소를 반환

배열로 구현한 큐의 연산 복잡도

dequeue()의 시간 복잡도는 다른 연산과는 다르게 O(n)의 복잡도를 가진다.(다른 연산은 모두 O(1)) 맨 앞의 원소를 꺼내고 나서 삭제하기 때문에 모든 원소들의 배열을 다시 정리해야 하기 때문이다.
만약 이중 연결 리스트로 큐를 구현하면 dequeue() 연산의 시간 복잡도를 해결할 수 있다.

#배열로 구현한 큐, 정말 쉽고 간편하다
class ArrayQueue:
    def __init__(self):
        self.data = []

    def size(self):
        return len(self.data)

    def isEmpty(self):
        return self.size() == 0

    def enqueue(self, item):
        self.data.append(item)

    def dequeue(self):
        return self.data.pop(0)

    def peek(self):
        return self.data[0]

#양방향 연결 리스트로 구현한 큐
#양방향 연결 리스트를 먼저 정의하고
class Node:

    def __init__(self, item):
        self.data = item
        self.prev = None
        self.next = None

class DoublyLinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = Node(None)
        self.head.prev = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None

    def __repr__(self):
        if self.nodeCount == 0:
            return 'LinkedList: empty'

        s = ''
        curr = self.head
        while curr.next.next:
            curr = curr.next
            s += repr(curr.data)
            if curr.next.next is not None:
                s += ' -> '
        return s

    def getLength(self):
        return self.nodeCount

    def traverse(self):
        result = []
        curr = self.head
        while curr.next.next:
            curr = curr.next
            result.append(curr.data)
        return result

    def reverse(self):
        result = []
        curr = self.tail
        while curr.prev.prev:
            curr = curr.prev
            result.append(curr.data)
        return result

    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None

        if pos > self.nodeCount // 2:
            i = 0
            curr = self.tail
            while i < self.nodeCount - pos + 1:
                curr = curr.prev
                i += 1
        else:
            i = 0
            curr = self.head
            while i < pos:
                curr = curr.next
                i += 1

        return curr

    def insertAfter(self, prev, newNode):
        next = prev.next
        newNode.prev = prev
        newNode.next = next
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True

    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)

    def popAfter(self, prev):
        curr = prev.next
        next = curr.next
        prev.next = next
        next.prev = prev
        self.nodeCount -= 1
        return curr.data

    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError('Index out of range')

        prev = self.getAt(pos - 1)
        return self.popAfter(prev)

    def concat(self, L):
        self.tail.prev.next = L.head.next
        L.head.next.prev = self.tail.prev
        self.tail = L.tail

        self.nodeCount += L.nodeCount

#큐 클래스를 정의한다.
class LinkedListQueue:

    def __init__(self):
        self.data = DoublyLinkedList()

    def size(self):
        return self.data.nodeCount

    def isEmpty(self):
        return self.data.nodeCount==0

    def enqueue(self, item):
        node = Node(item)
        self.data.insertAt(self.size()+1,node)

    def dequeue(self):
        return self.data.popAt(1)

    def peek(self):
        return self.data.head.next.data

환형 큐(Circular Queue)

큐의 활용

자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로(asynchronously) 일어나는 경우
먼저 쌓인 자료를 순서대로 처리하는 상황(?)
자료를 이용하는 작업이 여러 곳에서 일어나는 경우
컴퓨터 시스템에서 주로 활용된다고 한다
어려운 알고리즘에서 활용이 되기 때문에 연습문제로 쉽게 다루기가 어렵다고 한다

환형 큐(Circular Queue)

정해진 개수의 저장 공간을 빙 돌려가며 이용
배열의 한계를 극복하기 위해서 사용한다.
rear와 front를 활용해서 정해진 크기의 배열을 환형으로 재활용한다.
큐가 가득차면 더이상 데이터를 넣을 수 없기 때문에 큐의 개수를 확인하는 것이 중요하다.
따라서 isFull()연산을 추가해준다.

class CircularQueue:
    #초기화의 단계에서는 배열의 크기와 front rear위치를 정의한다.
    def __init__(self, n):
        self.maxCount = n
        self.data = [None] * n
        self.count = 0
        self.front = -1
        self.rear = -1
        
    def size(self):
        return self.count
    
    def isEmpty(self):
        return self.count == 0
    
    def isFull(self):
        return self.count == self.maxCount
    

    # enqueue에서는 rear값이 최대에 도달했을때 다시 처음으로 돌아갈 수 있도록 설정해주어야한다.
    def enqueue(self, x):
        if self.isFull():
            raise IndexError('Queue full')
        
        self.rear = (self.rear + 1) % self.maxCount
        self.data[self.rear] = x
        self.count += 1

    # dequeue에서는 front값을 적절하게 설정해주어야 한다.
    def dequeue(self):
        if self.isEmpty():
            raise IndexError('Queue empty')

        self.front = (self.front + 1) % self.maxCount
        x = self.data[self.front]
        self.count -= 1
        return x

    # 큐의 값을 꺼내지 않고 보는 연산
    def peek(self):
        if self.isEmpty():
            raise IndexError('Queue empty')
        return self.data[(self.front + 1) % self.maxCount]

우선순위 큐(Priority Queue)

큐가 firt in first out 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식

Enqueue 6 7 3 2
Dequeue 2 3 6 7

우선순위 큐의 구현

1. Enqueue할 때 우선순위 순서를 유지하도록
2. Dequeue할 때 우선순위가 높은 것을 선택
   2의 방식은 정리가 안된 리스트에서는 모든 원소를 탐색하게 되므로 1의 방식이 좀더 유리하다. 1의 방식은 양방향 연결 리스트를 사용하는게 좀더 유리하다.

#앞의 양방향 링크드 리스트 코드는 생략
class PriorityQueue:
    def __init__(self, x):
        self.queue = DoublyLinkedList()
    
    def size(self):
        return self.queue.getLength()

    def isEmpty(self):
        return self.size() == 0
        
    #enqueue의 x는 숫자로만 한정해서 노드 간의 우선순위는 이 숫자들의 크기를 비교하는 것으로 가정한다.
    def enqueue(self, x):
        newNode = Node(x)
        
        curr = self.queue.head
        
        # 아래 코드를 실행해보면 더 큰 숫자가 더 큰 우선순위를 가지게 된다. 
        # 가령 3 6 7 2 순서로 enqueue를 하고 traverse()를 해보면 7 6 3 2가 출력된다.
        while curr.next != self.queue.tail and x < curr.next.data :
            curr = curr.next

        self.queue.insertAfter(curr, newNode)
        
    def dequeue(self):
        return self.queue.popAt(self.queue.getLength())


    def peek(self):
        return self.queue.getAt(self.queue.getLength()).data