스택(stack), 큐(queue)

스택 (stack)

• 데이터 값을 저장하는 기본적인 구조로 일차원의 선형 (linear) 자료구조
• (배열/리스트와 유사하게) 값을 저장하는 연산과 저장된 값을 꺼내는 연산이 제공됨
• but 매우 제한적인 규칙: LIFO (Last In First Out) -> 가장 최근에 저장된 값이 가장 먼저 나감

stack 용어

• Top: 스택에 가장 최근에 넣은, 스택의 맨 위에 있는 데이터
• Push: 스택에 데이터를 넣는 행위
• Pop: 스택의 맨 위에 있는 데이터를 삭제하는 행위
• empty/full: 스택에 데이터가 꽉 찼는지, 스택에 데이터가 없는지 확인
• size(len): 스택에 들어있는 데이터의 개수 리턴

stack 시간 복잡도 (Big-O 시간)

• 삽입: O(1)
• 삭제: O(1)
• 검색: O(N)

 

# stack 구현

class Stack:
    def __init__(self):
        self.items = []

    def push(self, val):
        self.items.append(val)

    def pop(self):
        try:
            self.items.pop()
        except IndexError: # stack 이 비어 pop 할 item 이 없으면 indexError
            print("Stack is empty")

    def top(self):
        try:
            self.items[-1]
        except IndexError: # stack 이 비어 item 이 없으면 indexError
            print("Stack is empty")

    def __len__(self):
        return len(self.items)

 

 

큐 (queue)

• 데이터 값을 저장하는 기본적인 구조로 일차원의 선형 (linear) 자료구조
• (배열/리스트와 유사하게) 값을 저장하는 연산과 저장된 값을 꺼내는 연산이 제공됨
• but 매우 제한적인 규칙: FIFO (First In First Out) -> 가장 처음에 (오래전에) 저장된 값이 가장 먼저 나감

Queue 용어

• front: 데이터가 나가는 곳, 큐의 맨 앞
• rear: 데이터가 들어오는 곳, 큐의 맨 뒤
• enqueue: 큐에 데이터를 넣는 행위, 큐의 맨 뒤에 데이터를 추가함
• dequeue: 큐에서 데이터를 삭제하는 행위, 큐의 맨 앞에 있는 데이터를 삭제
• empty/full: 큐에 데이터가 꽉 찼는지, 큐에 데이터가 없는지 확인
• size(len): 큐에 들어있는 데이터의 개수 리턴

Queue 시간복잡도 (Big-O 시간)

• 삽입: O(1)
• 삭제: O(1)
• 검색: O(N)

# queue 구현

class Queue:
    def __init__(self):
        self.items = []
        self.front_index = 0 # 다음 dequeue 가 될 index 값 기억

    def enqueue(self, val):
        self.items.append(val)

    def dequeue(self):
        # queue 가 비어 dequeue 할 item 이 없으면 None return 
        if self.front_index == len(self.items): 
            print("Queue is empty")
            return None 
        # dequeue 할 item 이 있으면 다음에 dequeue 할 item 의 index 를 1 증가시키고 0 번 index pop
        else: 
            x = self.items[self.front_index] 
            self.front_index += 1
            self.items.pop(0)
            return x

 

 

데크 (Deque)

• Stack + Queue 의 형태
• Double Ended Queue 의 약어
• 큐와 다르게 양쪽에서 데이터의 삽입/삭제가 가능

Deque 용어

• front/rear: 데크의 맨 앞,
• append: 데크에 데이터를 삽입하는 행위
• pop: 데크에서 데이터를 삭제하는 행위
• empty/full: 데크에 데이터가 꽉 찼는지, 데크에 데이터가 없는지 확인
• size(len): 데크에 있는 데이터의 개수를 리턴

 

Deque 시간복잡도 (Big-O  시간)

• 삽입: O(1)
• 삭제: O(1)
• 검색: O(N)

 

 

 

📖 References 📖

신찬수 교수님 강의자료

https://www.programiz.com/dsa/stack

Stack Data Structure and Implementation in Python, Java and C/C++

https://www.programiz.com/dsa/queue

Queue Data Structure and Implementation in Java, Python and C/C++

https://soft.plusblog.co.kr/24

[Java(자바)] Deque(덱/데크) 자료구조