Dev/자료구조

[자료구조][파이썬/Python] 덱 (Deque)

덱(Deque, Double Ended Queue) 덱(Dequeue)은 데이터 값을 저장하는 기본적인 구조로, 일차원의 선형 자료구조이다. 덱은 스택(Stack)과 큐(Queue)의 연산을 모두 지원하는 자료구조로, 양 끝에서 모두 삽입과 삭제가 가능한 큐라고 생각하면 된다. 나머지 부가적인 덱의 길이를 반환하는 연산이나 덱이 비어있는지 확인하는 연산 등은 스택과 큐에 구현되어 있는 연산들과 유사하게 구현된다. Python의 모듈을 이용하기 큐를 설명할 때 언급했지만 collections라는 모듈에 deque라는 클래스로 이미 구현되어 있다. 여기서 특별한 점은 양 끝에서 삽입과 삭제를 할 수 있어야 하므로 양방향 연결리스트(Doubly Linked List)로 구성되어 있다. 단순히 값을 삽입하고 삭..

[자료구조][파이썬/Python] 큐(Queue)

큐(Queue) 큐(Queue)는 데이터 값을 저장하는 기본적인 구조로, 일차원의 선형 자료구조이다. 기본적으로 값을 저장하는 연산 enqueue와 저장된 값을 꺼내는 연산 dequeue가 제공되어야 한다. 부가적으로 큐의 길이를 반환하는 연산이나 큐가 비어있는지 확인하는 연산, 큐의 가장 아래에 있는 값이 무엇인지 확인하는 연산을 추가할 수도 있다. 가장 먼저 들어간 값이 가장 먼저 나오게 되는 원칙(First In First Out, FIFO)을 따른다. 클래스로 구현하기 & 리스트 메서드 활용하기 스택과 큐는 매우 유사한 형태이고 따르고 있는 원칙만 약간 달라 설명도, 특징도, 구현하는 방식도 유사한 점이 많다. 그래서 큐도 마찬가지로 클래스로 구현하는 일반적인 방법은 (1) 양방향 연결리스트(Do..

[자료구조][파이썬/Python] 스택(Stack)

스택(Stack) 스택(Stack)은 데이터 값을 저장하는 기본적인 구조로, 일차원의 선형 자료구조이다. 기본적으로 값을 저장하는 연산 push와 저장된 값을 꺼내는 연산 pop이 제공되어야 한다. 부가적으로 스택의 길이를 반환하는 연산이나 스택이 비어있는지 확인하는 연산, 스택의 가장 위에 있는 값이 무엇인지 확인하는 연산을 추가할 수도 있다. 가장 나중에 들어간 값이 가장 먼저 나오게 되는 원칙(Last In First Out, LIFO)을 따른다. 클래스로 구현하기 일반적으로 클래스로 구현하는 방법은 (1) 양방향 연결리스트(Doubly Linked List)를 통해 구현하는 방법, (2) Python 내 리스트 메서드로 구현하는 방법이 존재한다. 다만, 실제로 코딩테스트 문제를 풀 때 어떻게 빠르..