[파이썬 기본 데이터 구조] 1. 스택과 큐

 

스택과 큐

 

* 이 글은 네이버 부스트 코스의 인공지능(AI) 기초 다지기 강의를 수강하며 정리한 글입니다.

사담)
얼마전 인턴 모의면접에 우연히 참여할 기회가 생겼는데 스택과 큐를 헷갈려버렸다.
프로젝트 위주로 진행되는 수업이 많았어서 기초를 잊어버린게 틀림없다. 0ㅇ0
다시 초심으로 돌아가 꼼꼼하게 정리해 보자.

 

1) 스택 Stack    (=사다리. 제일 나중에 올라간 사람이 먼저 내려와야 전 사람들이 내려옴)

- 나중에 넣은 데이터를 먼저 반환하도록 설계된 메모리 구조

- LIFO (Last In First Out)

- 기능 : Push, Pop, Top, Empty

- 구현 : List

• Push : 원소를 삽입하는 함수

list.append(element)

• Pop : 제일 나중의 원소를 반환하고 삭제하는 함수

list.pop()

• Top : 제일 마지막 원소를 출력하는 함수
• isEmpty  : 스택이 비었는지 확인하는 함수

 

참고) 클래스를 이용해 스택을 구현해보자.

Class Stack():
    def __init__(self):
        self.stack=[]
    def push(self, element):
        self.stack.append(element)
    def isEmpty(self):
        if(len(self.stack)==0):
            return True
        return False
    def top(self):
        if(self.isEmpty()):
            return -1
        return self.stack[-1]
    def pop(self):
        if(self.isEmpty()):
            return -1
        return self.stack.pop()

 

예제) 스택구조를 활용해 입력된 글자를 역순으로 출력해 보자.

word=input() #문자열 입력
word_list=list(word) #문자열을 리스트로 변환
for word_len in range(len(word_list)):
	word_list.pop()

 

2) 큐 Queue    (=주문. 먼저 들어간 주문을 우선으로 처리)

- 먼저 넣은 데이터를 먼저 반환하도록 설계된 메모리 구조

- FIFO (First In First Out)

- 기능 : Put, Get, isEmpty

- 구현 : List

• Put : 원소를 삽입하는 함수

list.append(element)

• Get: 제일 처음 원소를 반환하고 삭제하는 함수

list.pop(0)

• isEmpty  : 큐가 비었는지 확인하는 함수

 

참고) 클래스를 이용해 큐을 구현해보자.

Class Queue():
    def __init__(self):
        self.queue=[]
    def put(self, element):
        self.queue.append(element)
    def isEmpty(self):
        if(len(self.queue)==0):
            return True
        return False
    def get(self):
        if(self.isEmpty()):
            return -1
        return self.queue.pop(0)

 

3) 파이썬에서 제공하는 큐 모듈

스택은 일반 리스트로도 쉽게 구현할 수 있지만,

큐의 경우 get()함수 실행시 시간 복잡도가 O(1)이 아닌 O(N)이 걸리는 문제가 발생한다.

따라서 deque 모듈을 별도로 사용하면 시간 복잡도를 줄일 수 있다.

 

import queue

import queue
 
#큐 모듈의 큐 클래스 객체 선언
quque_one= queue.Queue()
 
#선언 된 큐 객체에 요소 입력
data.put(element)
 
#큐 객체에서 요소 하나씩 꺼내기 :FIFO
print(data.get())

 

 

import collections.deque

(doubled ended queue로 양방향 링크드 리스트로 구현됨)

from collections import deque
 
#디큐 모듈의 디큐 클래스 객체 선언
queue_two = deque()
 
#선언 된 큐 객체에 요소 입력
##일반
queue_two .append(element)
##왼쪽에 요소 입력
queue_two .appendleft(element)
##중간(list_index)에 요소 입력
queue_two .insert(list_index, element)
 
#선언 된 큐 객체에서 요소 하나씩 꺼내기
##일반
print(queue_two.popleft())
##오른쪽
print(queue_two.pop())