Simple Data Structure | Queue, Circular Queue, Stack, N Queens Problem, fraction, prime number, fibonacci, bowling game, binary search

학점교류로 듣는 숙명여대 학점교류

 

자료구조 연습

 

Queue

Circular Queue

Stack

N Queens Problem

fraction

prime number

fibonacci

bowling game

permutation

binary search

hanoi tower

 

---

Queue

# queue
class queue:
    # __init__
    def __init__(self):
        self.que = []
    # empty
    def empty(self):
        return len(self.que)==0   
    # size
    def size(self):
        return len(self.que)
    # enqueue
    def enqueue(self,data):
        self.que.append(data)  
    # dequeue
    def dequeue(self):
        if self.empty():
            print("EMPTY QUEUE")
        else:
            return self.que.pop(0)                
    # view
    def view(self):
        if self.empty:
            print("EMPTY QUEUE")    
        else:
            print(self.que)     
         
    # peek
    def peek(self):
        if self.empty:
            print("EMPTY QUEUE")      
        else:
            return self.que[0]
         
exQUE = queue()
exQUE.enqueue(0)
exQUE.enqueue(1)
exQUE.enqueue(2)
exQUE.enqueue(3)
print(exQUE.dequeue())
print(exQUE.dequeue())
print(exQUE.dequeue())

 

 

Stack

# stack
class stack:
    # __init__
    def __init__(self):
        self.stk = []
        self.top = 0
        self.cnt = 0
    # empty
    def empty(self):
        return len(self.stk) == 0
    # size
    def size(self):
        return len(self.stk)
    # push
    def push(self, data):
        self.stk.append(data)
    # pop
    def pop(self):
        if self.empty():
            print("EMPTY STACK")
        else:
            return self.stk.pop()
    # view
    def view(self):
        print(self.stk)
    # peek
    def peek(self):
        print(self.stk[len(self.stk)-1])
        return self.stk[len(self.stk)-1]

exSTK = stack()
exSTK.push(0)
exSTK.push(1)
exSTK.push(2)
exSTK.push(3)
print(exSTK.pop())
print(exSTK.pop())
print(exSTK.pop())

 

 

fraction

# fraction
class fraction:
    def __init__(self, num, dim):
        self.num = num
        self.dim = dim
        
    # __str__
    def __str__(self):
        return '{0}/{1}'.format(self.num, self.dim)
    
    # __add__
    def __add__(self, frac):
        new = fraction(1,1)
        new.num = self.num * frac.dim + self.dim * frac.num
        new.dim = self.dim * frac.dim
        common = self.gcd(new.num, new.dim)
        new.num //= common
        new.dim //= common
        return new
    
    # multiply
    def multiply(self, frac):
        new = fraction(1,1)
        new.num = self.num * frac.num
        new.dim = self.dim * frac.dim
        common = self.gcd(new.num, new.dim)
        new.num //= common
        new.dim //= common        
        return new
    
    # gcd
    def gcd(self, a, b):
        if b <= 1:
            return a
        else:
            return self.gcd(b, a%b)

f1 = fraction(1, 3)
f2 = fraction(2, 4)

print(f1)
print(f2)
print(f1+f2)  
print(f1.multiply(f2))

prime number

def prime(num):
    primeList = [2]
    for i in range(2, num+1):
        for j in primeList:
            if i % j == 0:
                break
        else:
            primeList.append(i)
    return primeList
print("PRIME")
print(prime(15))
print("PRIME")

fibonacci

# fibonacci
def fibonacci(num):
    if num == 0:
        return 0
    elif num == 1:
        return 1
    else:
        return fibonacci(num-2)+fibonacci(num-1)

 

 

binary search

# binary search

def bSearch(lst, ans, start, end):
    mid = (start + end) // 2
    
    if start <= end:
        if lst[mid] == ans:
            print(mid)
            return mid
            
        elif lst[mid] > ans: 
            bSearch(lst, ans, start, mid)
        else:
            bSearch(lst, ans, mid, end)
            
    else:
        return -1
    
print("BSEARCH")
lst = [1,2,3,4,5,6,7,8,9,10] # 14
bSearch(lst, 9, 0,len(lst)-1)
print("BSEARCH")

hanoi tower

# htower(n,a,b)
def htower(n, a, b):
    if n == 1:
        print(f"{a} -> {b}")
    else:
        c = 6 - a - b
        htower(n-1, a, c)
        print(f"{a} -> {b}")
        htower(n-1, c, b)
        
htower(3, 1, 3)

factorial

# factorial
def factorial(num):
    if num==1 or num==0:
        return 1
    else:
        return factorial(num-1)

gcd

# gcd
def gcd(self, a, b):
        if b <= 1:
            return a
        else:
            return self.gcd(b, a%b)

---

Circular Queue

# Circular Queue

class CQueue:
    # __init__
    def __init__(self, size):
        self.size = size
        self.cq = [None] * self.size 
        # [front]
        # [rear]
        # [none none none none none]
        self.front = 0
        self.rear = 0
        self.count = 0
    # empty
    def empty(self):
        return self.front == self.rear
    # full
    def full(self):
        return self.front == (self.rear + 1) % self.size
    # view
    def view(self):
        return self.cq
    # push
    def push(self, data):
        if self.full():
            print("FULL CQUEUE")
        else:
            
            self.cq[self.rear] = data
            self.rear += 1
    # pop
    def pop(self):
        if self.empty():
            print("EMPTY CQUEUE")
        else:
            data = self.cq[self.front]
            self.cq[self.front] = None
            self.front += 1
            return data

print()
que = CQueue(6)
que.push(1)
que.push(1)
que.push(2)
que.push(3)
que.push(4)
que.push(5)
que.push(6)
print()
print(que.pop())
print(que.pop())
print(que.pop())
print(que.pop())

---

<<<커밍쑨.....>>>>

 

N Queens Problem

 

bowling game

 

permutation