Review 9 - Queues & Stacks

https://eglife.tistory.com/77

Review 8 - Python Data Structure

Array와 Linked List의 특성은 잘 알고 있으면 편하다

 

사실 지난 시간에 큐와 스택을 다 다뤄보려했지만, 분량 조절 실패

 

간단히 Queue, Stack을 다루고 넘어가보자

 

 

1. Queues ( F irst I n F irst O ut )

 

먼저 enqueued 된 element가 먼저 dequeued 된다.

 

필요한 Method? 1.enqueue , 2.dequeue

 

이런걸 Array , Linked List 같은 것으로 구현할 수 있어야 한다.

 

 

2. Stacks ( L ast I n F irst O ut)

 

나중에 1. Push 된 것들이 먼저 2. Pop 된다.

 

=> 가장 최근 것을 복구하는 Undo(Ctrl + z), Parentheses matching( ),{ },[ ] 에 Stack 구조가 쓰인다.

 

그리고 function chain을 보면, 가장 늦게 call된 function이 먼저 pop 되기 때문에 function의 memory 관리를 Stack구조로 한다. 효율적인 메모리공간 관리가 가능하다.

 

 

3. Implementation

 

Python에선 따로 Array를 쓸 수 없어서.. 고오급 구조인 List로 Queue, Stack을 한 번 나타내 보았다.

 

요건 쉽지

 

class arrayq:
    def __init__(self) -> None :
        self.q = []
        self.size = 0
    def enqueue(self,v : int) -> None :
        self.v = v
        self.q = [v] + self.q
        self.size += 1
    def dequeue(self) -> None:
        if self.size == 0 : return
        self.q = self.q[:-1]
        self.size -= 1
    def getSize(self) -> int:
        return self.size
# test
Q = arrayq()
Q.enqueue(3)
Q.enqueue(4)
print(Q.q)
Q.enqueue(1)
Q.enqueue(2)
print(Q.q)
Q.dequeue()
​
print(Q.q)
print("size:",Q.getSize())
​
[4, 3]
[2, 1, 4, 3]
[2, 1, 4]
size: 3

class arrays:
    def __init__(self) -> None :
        self.s = []
        self.size = 0
    def push(self,v : int) -> None :
        self.v = v
        self.s.append(self.v)
        self.size += 1
    def pop(self) -> None:
        if self.size == 0 : return
        self.s = self.s[:-1]
        self.size -= 1
    def getSize(self) -> int:
        return self.size

#test
S = arrays()
S.push(3)
S.push(4)
print(S.s)
S.push(1)
S.push(2)
print(S.s)
S.pop()
S.pop()
S.pop()
​
print(S.s)
print("size:",S.getSize())
​
[3, 4]
[3, 4, 1, 2]
[3]
size: 1

 

이번엔 Linked List로 한 번 표현해보겠다. 이것이 좀 유의미할듯

 

# 내 맘대로 한 거라 좀 이상하다..
class Node:
    def __init__(self, v : int) -> None :
        self.val = v
        self.next = None
​
class SLLq:
    def __init__(self) -> None :        
        self.size = 0
        self.first = None
    
    def add(self, v : int) -> None :
        newNode = Node(v)
        self.size += 1
        
        if self.first == None :
            self.first = newNode
        
        else:
            newNode.next = self.first
            self.first = newNode
    
    def getFirst(self) -> int :
        if self.first : return self.first.val
        else : return None
    
    def remove(self) -> None :
        if self.size == 0 : return
        elif self.size ==1 :
            self.size -=1
            self.first = None
        else :
            curr = self.first
            while curr.next.next : # 의문이긴 하다..
                curr = curr.next
            curr.next = None
            self.size -= 1
            
    def getSize(self) -> int:
        return self.size
    
q = SLLq()
q.remove()
q.add(5)
q.add(6)
q.add(7)
q.add(2)
q.remove()
​
curr = q.first
while curr :
    print(curr.val)
    curr = curr.next
​
​
2
7
6

 

class Node:
    def __init__(self, v : int) -> None :
        self.val = v
        self.next = None
​
class SLLs:
    def __init__(self) -> None :        
        self.size = 0
        self.first = None
    
    def push(self, v : int) -> None :
        newNode = Node(v)
        self.size += 1
        
        if self.first == None :
            self.first = newNode
        
        else:
            newNode.next = self.first
            self.first = newNode
    
    def getTop(self) -> int :
        if self.first : return self.first.val
        else : return None
    
    def pop(self) -> None :
        if self.first == None : return
        else:
            self.first = self.first.next
            self.size -= 1
    def getSize(self) -> int:
        return self.size
    
s = SLLs()
s.push(3)
s.push(6)
s.push(9)
print(s.getTop(),s.getSize())
s.pop()
s.push(11)
print(s.getTop(),s.getSize())
​
​
​
​
​
9 3
11 3

 

Linked List로 구현하기엔 확실히 Stack이 편하다. LIFO인 구조이기 때문이다.

 

뭔가 Queue의 경우 차라리 Head, tail을 통해 관리하는 것이 편할 거 같다.

 

# tail 없는 버전 ( enqueue 할 때 while문이 필요하다 )
class Node:
    def __init__(self,v : int) -> None :
        self.val = v
        self.next = None
​
class LLQ:
    def __init__(self) :
        self.size = 0
        self.head = None
        self.tail = None
        
    def enqueue(self,v : int) -> None :
        newNode = Node(v)
        self.size += 1
        
        if self.head == None :
            self.head = newNode
        else :
            curr = self.head
            while curr.next:
                curr = curr.next
            curr.next = newNode
    
    def dequeue(self) -> None :
        if self.head == None : return
        
        self.head = self.head.next
        self.size -=1
        
    def getTop(self) -> int:
        if self.head == None : return
        return self.head.val
    
    def getSize(self) -> int:
        return self.size
q = LLQ()
q.enqueue(4)
q.enqueue(7)
q.enqueue(9)
q.enqueue(10)
q.enqueue(11)
​
print(q.getTop(),q.getSize())
q.dequeue()
print(q.getTop(),q.getSize())
q.dequeue()
print(q.getTop(),q.getSize())
​
​
4 5
7 4
9 3

 

# tail 있는 버전
class Node:
    def __init__(self,v : int) -> None :
        self.val = v
        self.next = None
​
class LLQ2:
    def __init__(self) :
        self.size = 0
        self.head = None
        self.tail = None
        
    def enqueue(self,v : int) -> None :
        newNode = Node(v)
        self.size += 1
        
        if self.tail == None:
            self.head = self.tail = newNode
        else:
            self.tail.next = newNode
            self.tail = newNode
    
    def dequeue(self) -> None :
        if self.head == None : return
        
        self.head = self.head.next
        
        if self.head == None :
            self.tail =None
            
        self.size -=1
    def getTop(self) -> int:
        if self.head == None : return
        return self.head.val
    
    def getSize(self) -> int:
        return self.size
2
q = LLQ2()
q.enqueue(4)
q.enqueue(7)
q.enqueue(9)
q.enqueue(10)
q.enqueue(11)
​
print(q.getTop(),q.getSize())
q.dequeue()
print(q.getTop(),q.getSize())
q.dequeue()
print(q.getTop(),q.getSize())
​
​
4 5
7 4
9 3

 

- E. O. D -