스택, 큐, 덱이란?
- 데이터 값을 저장하는 기본적인 구조로 일차원의 선형(linear) 자료구조이다.
- (배열/리스트와 유사하게) 값을 저장(insert 또는 set)하는 연산과 저장된 값을 꺼내는(remove 또는 get) 연산이 제공된다. 그러나 매우 제한적인 규칙(LIFO, FIFO)등을 따른다.
스택(Stack): LIFO - 후입선출
- 스택은 가장 최근에 저장된 값 다음에 저장되며, 가장 최근에 저장된 값이 먼저 나간다. - LIFO(Last In First Out) 원칙
- 파이썬은 스택 자료형을 별도로 제공하지는 않지만, 리스트가 사실상 스택의 모든 연산을 지원한다.
![](https://blog.kakaocdn.net/dn/wDNVo/btqW8Gdrxtm/hCSnOxHhyCYEkKiNtN5jm0/img.gif)
class Stack:
def __init__(self):
self.items = [] # 데이터 저장을 위한 리스트 준비
def push(self, val):
self.items.append(val)
def pop(self):
try: # pop할 아이템이 없으면
return self.items.pop()
except IndexError: # indexError 발생
print("Stack is empty")
def top(self):
try:
return self.items[-1]
except IndexError:
print("Stack is empty")
def __len__(self): # len()로 호출하면 stack의 item 수 반환
return len(self.items)
def isEmpty(self):
return self.__len__() == 0
큐(Queue): FIFO - 선입선출
- 큐는 스택과 동일하게 가장 최근에 저장된 값 다음에 새로운 값이 저장되지만 가장 오래전에 저장된 값부터 나간다는 차이가 있다. - FIFO(First In First Out, 선착순) 원칙
- 스택과 마찬가지로 리스트는 큐의 모든 연산을 지원하지만, 리스트는 동적 배열로 구현되어 큐의 연산을 수행하기엔 효율적이지 않다. 따라서 파이썬에서 큐를 구현할 땐 후술할 덱을 사용한다.
![](https://blog.kakaocdn.net/dn/ba7ifb/btqW1sGQsbP/myDAzyoftIePUTv8zWTdZk/img.gif)
class Queue:
def __init__(self):
self.items = []
def enqueue(self,val):
self.items.append(val)
def dequeue(self):
try:
return self.items.pop(0)
except IndexError:
print("Queue is empty")
def front(self):
try:
return self.items[0]
except IndexError:
print("Queue is empty")
def __len__(self):
return len(self.items)
def isEmpty(self):
return len(self)
덱(Dequeue): Stack + Queue
- 덱은 스택과 큐의 연산을 모두 지원하는 자료구조이다.
- 왼쪽과 오른쪽에서 모두 삽입과 삭제가 가능한 큐다.
- 파이썬에선 collections라는 모듈에 deque란 클래스로 덱이 이미 구현되어 있다.
![](https://blog.kakaocdn.net/dn/IhR3o/btqWW918fZM/bmWrR79dbSoKthCiK4nzm0/img.png)
![](https://blog.kakaocdn.net/dn/Bj3gJ/btqXj72lP7i/Z3Ag04quP8UTeZOHUoXoHk/img.gif)
참고
Data Structures with Python(신찬수 저)
파이썬 알고리즘 인터뷰(박상길 저)
'CS > 자료구조' 카테고리의 다른 글
[자료구조] 배열, 리스트(Array, List) (0) | 2021.02.07 |
---|
스택, 큐, 덱이란?
- 데이터 값을 저장하는 기본적인 구조로 일차원의 선형(linear) 자료구조이다.
- (배열/리스트와 유사하게) 값을 저장(insert 또는 set)하는 연산과 저장된 값을 꺼내는(remove 또는 get) 연산이 제공된다. 그러나 매우 제한적인 규칙(LIFO, FIFO)등을 따른다.
스택(Stack): LIFO - 후입선출
- 스택은 가장 최근에 저장된 값 다음에 저장되며, 가장 최근에 저장된 값이 먼저 나간다. - LIFO(Last In First Out) 원칙
- 파이썬은 스택 자료형을 별도로 제공하지는 않지만, 리스트가 사실상 스택의 모든 연산을 지원한다.
![](https://blog.kakaocdn.net/dn/wDNVo/btqW8Gdrxtm/hCSnOxHhyCYEkKiNtN5jm0/img.gif)
class Stack:
def __init__(self):
self.items = [] # 데이터 저장을 위한 리스트 준비
def push(self, val):
self.items.append(val)
def pop(self):
try: # pop할 아이템이 없으면
return self.items.pop()
except IndexError: # indexError 발생
print("Stack is empty")
def top(self):
try:
return self.items[-1]
except IndexError:
print("Stack is empty")
def __len__(self): # len()로 호출하면 stack의 item 수 반환
return len(self.items)
def isEmpty(self):
return self.__len__() == 0
큐(Queue): FIFO - 선입선출
- 큐는 스택과 동일하게 가장 최근에 저장된 값 다음에 새로운 값이 저장되지만 가장 오래전에 저장된 값부터 나간다는 차이가 있다. - FIFO(First In First Out, 선착순) 원칙
- 스택과 마찬가지로 리스트는 큐의 모든 연산을 지원하지만, 리스트는 동적 배열로 구현되어 큐의 연산을 수행하기엔 효율적이지 않다. 따라서 파이썬에서 큐를 구현할 땐 후술할 덱을 사용한다.
![](https://blog.kakaocdn.net/dn/ba7ifb/btqW1sGQsbP/myDAzyoftIePUTv8zWTdZk/img.gif)
class Queue:
def __init__(self):
self.items = []
def enqueue(self,val):
self.items.append(val)
def dequeue(self):
try:
return self.items.pop(0)
except IndexError:
print("Queue is empty")
def front(self):
try:
return self.items[0]
except IndexError:
print("Queue is empty")
def __len__(self):
return len(self.items)
def isEmpty(self):
return len(self)
덱(Dequeue): Stack + Queue
- 덱은 스택과 큐의 연산을 모두 지원하는 자료구조이다.
- 왼쪽과 오른쪽에서 모두 삽입과 삭제가 가능한 큐다.
- 파이썬에선 collections라는 모듈에 deque란 클래스로 덱이 이미 구현되어 있다.
![](https://blog.kakaocdn.net/dn/IhR3o/btqWW918fZM/bmWrR79dbSoKthCiK4nzm0/img.png)
![](https://blog.kakaocdn.net/dn/Bj3gJ/btqXj72lP7i/Z3Ag04quP8UTeZOHUoXoHk/img.gif)
참고
Data Structures with Python(신찬수 저)
파이썬 알고리즘 인터뷰(박상길 저)
'CS > 자료구조' 카테고리의 다른 글
[자료구조] 배열, 리스트(Array, List) (0) | 2021.02.07 |
---|