12. Data Structures ( Stacks & Queues )

https://eglife.tistory.com/30

11. Data Structures ( Arrays & Linked Lists )

 

 

Data의 또 다른 구조인 Stack 과 Queue에 대해 알아보는 시간!

 

Stack 과 Queue 구조의 특징 도식화

 

 

Stack

 

- ex) 식판 쌓고 가져가기 --> Las it First out , 키보드에서 Back Space --> 마지막에 쓴 문자를 지운다.

- ex) 프로그래밍에서 괄호를 쌓기 --> 괄호 열 때마다 Stack 쌓고 닫을 때마다 Stack에서 뺀다. 쌓은만큼 닫아야 No Error

 

- Stack Terminology : push - add , pop - delete, peek - retrieve the most recent item

 

Stack Implementation

 

class stack():
    def __init__(self):
        self.data = []
        self.top = -1
    def push(self,x):
        self.data.append(x)
        self.top += 1
    def peek(self):
        if not self.is_empty():
            return self.data[self.top]
        else : return None
    def pop(self):
        if not self.is_empty():
            del self.data[self.top]
            self.top -= 1
    def is_empty(self):
        return (self.top == -1)
a=stack()
a.push(3)
a.push(31)
a.push(2)
a.pop()
a.push(11)
print(a.peek())
a.is_empty()
11
False

 

 

Linked List 로 Stack 구조 만들어 보기

 

 

 

- Linked List만 잘 구현해 놓았다면 이것을 이용해서 Stack 구현이 가능하다.

( Linked List에서 insert 함수를 0번째 index에 넣도록 우리가 Stack Class에 선언을 해 놓았기 때문)

 

- 0 번째에 Data를 추가하고, 읽고, 삭제하면 된다.

 

- Linked List에서 empty 확인은 첫 번째 Data가 None인지 체크하면 된다.

 

Stack Time Complexity

 

 

 

- 쓰고 읽고 삭제하는 것 전부 O(1)이라 효율적이지만, STACK 조건을 만족하는 상황에서만 쓸 수 있다.

 

 

Stack 구조를 쓰는 예시

 

- 길 찾기 P에서 Z까지 가는 길이 있는지 확인하는 문제 / Stack의 Push, Pop으로 해결

 

 

- 괄호가 잘 열렸다가 닫혔는지 Well - Form 체크

 

 

 

- 시간 날 때 Code 구현을 한 번 해보자...

 

 

Queue(선착순)

 

- Queue Terminology : enque - Add , peek - Retrieve the oldest item, deque - delete

 

class queue():
    def __init__(self):
        self.data = []
        self.last = -1
    def enque(self,x):
        self.data.append(x)
        self.last += 1
    def deque(self):
        if not self.is_empty():
            del self.data[0]
            self.last-=1
    def peek(self):
        if not self.is_empty():
            return self.data[0]
    def is_empty(self):
        return (self.last == -1)
test = queue()
test.enque(3)
test.enque(9)
test.enque(6)
test.deque()
print(test.peek())
test.is_empty()
9
False

 

-  Queue Time Complexity ?

 

 

 

- 제일 Oldest 하나만 Deque 했을 뿐인데, 기존에 있던 것들이 빈 자리로 왼쪽 한 칸씩 shift를 해야하므로 O(N)이 걸린다. Queue / Peak는 Stack과 같이 O(1) !

 

Linked list로 Queue 구조 구현

 

 

- Queue가 peak / dequeue 때는 괜찮다가 enqueue에서 Linked list 비효율이 발생한다. O(N)

 

- 그래서 last node를 트래킹하는 방식을 차용해서 이것도 O(1)으로 갈 수 있도록 조치

 

- Queue의 Time Complexity

 

 

 

Queue 적용 예제

 

- Implement Queue using two Stacks

 

 

 

Stack, Queue .. 적절한 자료구조를 적절한 문제에 잘 적용할 수 있어야 한다.

 

실제 생각했던 것들을 코드로도 짤 수 있어야 한다는 것!!

 

아 구찮은데.. 연습이 많이 필요하겠다.

 

실습을 좀 많이 해봐야지