[3부] 09장 스택, 큐

스택 (stack)

다음과 같은 2가지 주요 연산을 지원하는 요소의 컬렉션으로 사용되는 추상 자료형

• push(): 요소를 컬렉션에 추가함.
• pop(): 아직 제거되지 않은 가장 최근에 삽입된 요소를 제거함. 

stack

FILO (First In Last Out) 구조

스택에서 데이터를 넣는 것은 push, 데이터를 꺼내는 것은 pop 이라고 함. 

push와 pop을 하는 위치를 top 이라고 하고, 스택의 가장 아랫 부분을 bottom 이라고 함. 

 

연결 리스트를 이용한 스택 ADT 구현

연결 리스트를 이용한 스택 ADT 구현

class Node:
    def __init__(self, value, next = None):
        self.value = value
        self.next = next
    
class Stack:
    def __init__(self):
        self.head = None
    
    # self.head가 변하는지 확인하려고 __str__ 사용, stack 과는 관련 없음.
    # def __str__(self):
    #     return '({})'.format(self.head)

    def push(self, value):
        self.head = Node(value, self.head)
        # new_node.next = self.head
        # self.head = new_node
    
    def pop(self):
        if self.is_empty():
            return 'No more value'
        item = self.head.value
        self.head = self.head.next
        return item

    def peek(self):
        if self.is_empty():
            return 'No more value'
        return self.head.value

    def is_empty(self):
        if self.head:
            return False
        return True
    
    def is_not_empty(self):
        if self.head:
            return True
        return False

if __name__ == '__main__':
    stack = Stack()
    stack.push(1)
    stack.push(2)
    stack.push(3)

    print(stack.peek())

    # If stack is not empty, pop()
    while stack.is_not_empty():
        print(stack.pop())

큐 (Queue)

• 한쪽 끝 (rear) 에서는 삽입 연산만 이루어지고, 다른 한쪽 끝 (front) 에서는 삭제 연산만 이루어지는 유한 순서 리스트

FIFO (First In First Out) 구조

큐에서 데이터를 넣는 것은 put, 데이터를 꺼내는 것은 get 이라고 함. 

front 는 데이터를 get 할 수 있는 위치, rear 은 데이터를 put 할 수 있는 위치를 의미함. 

queue

큐의 다른 형식

1. Circular Queue (원형 큐) => 9장 25번 문제 (원형 큐 디자인)
2. Priority Queue (우선 순위 큐) => 10장 27번 문제
3. Deque (Double-Ended Queue) => 10장 26번 문제 (원형 데크 디자인, 이중 연결 리스트 문제)

---

no	title	leedcode	status
20	유효한 괄호	리트코드 20	O
21	중복 문자 제거	리트코드 316	X
22	일일 온도	리트코드 739	X
23	큐를 이용한 스택 구현	리트코드 225	O
24	스택을 이용한 큐 구현	리트코드 232	O (02/17)
25	원형 큐 디자인	리트코드 622	O (02/19)

No.20 유효한 괄호

출처: 리트코드

My Solution) 스택 일치 여부 판별

(책 보고 했음.. 문제를 잘 못 이해했음..)

32ms, 14.2MB
시간 복잡도: O(n)

My Solution) 사실상 책 풀이

My Solution) 사실상 책 풀이

No.21 중복 문자 제거 (아직 못 품)

출처: 리트코드

My Solution)

어떻게 풀어야 하는지 감도 안 잡힘.. 뭔가 스택을 쓰려고 했는데, 모르겠음.....

No.22 일일 온도 (아직 못 품)

출처: 리트코드

My Solution 1) Brute-Force => Time Limit Exceeded

My Solution 1) Brute-Force => Time Limit Exceeded

No.23 큐를 이용한 스택 구현

출처: 리트코드

My Solution) 리스트 사용

24ms, 14.1MB

My Solution) 리스트 사용

My Solution) 리스트 사용

 

책 풀이

Solution 1) push() 할 때 큐를 이용해 재정렬

Solution 1) push() 할 때 큐를 이용해 재정렬

Solution 1) push() 할 때 큐를 이용해 재정렬

No.24 스택을 이용한 큐 구현

출처: 리트코드

My Solution) 스택 2개 사용 (사실 유튜브에서 봤음..)

32ms, 14.4MB

My Solution) 스택 2개 사용 (사실 유튜브에서 봤음..)

My Solution) 스택 2개 사용 (사실 유튜브에서 봤음..)

책 풀이

Solution 1) 스택 2개 사용

32ms, 14.2MB

Solution 1) 스택 2개 사용

No.24 원형 큐 디자인

출처: 리트코드

My Solution)

68ms, 14.7MB

My Solution)