파이썬 스택(Stack), 큐(Queue) 구현하기
파이썬 스택(Stack), 큐(Queue) 구현하기 — #파이썬스택 #파이썬큐 #파이썬stack #파이썬queue AI스쿨 msa기반 java 백엔드 코스 중에 공부한 내용을...
#파이썬스택 #파이썬큐 #파이썬stack #파이썬queue
AI스쿨 msa기반 java 백엔드 코스 중에 공부한 내용을 작성하였습니다
파이썬으로 스택과 큐 구현하기
이전글을 통해 파이썬으로 배열을 구현하는 방법읇 배웠는데요. 배열을 구현할때 클래스를 사용하여 구현을 하였습니다. 이번에도 마찬가지로 스택과 큐를 클래스를 이용하여 구현해 볼거에요.
배열보다 훨씬 간단하게 구현 가능하니 천천히 따라오세요~
스택 구현하기
이전글에서 자료구조의 순수 기능에 대해 다뤄보았는데요. 스택의 순수 기능으로는 두가지가 있다고 말씀 드렸습니다. 값을 넣는 기능과 맨마지막 값을 빼는 기능입니다.
스택 기능 뼈대 만들기
| class Stack: def \_\_init\_\_(self): pass def push(self, value): pass def pop(self): pass |
|---|
자료구조를 구현할때는 우선 기본적인 기능의 뼈대를 먼저 만드는 것이 좋습니다. 저는 push, pop함수를 미리 만들어 두었습니다.
push 구현
| class Stack: def \_\_init\_\_(self): self.data = \[\] def push(self, value): self.data.append(value) def pop(self): pass |
|---|
pop의 경우는 간단하게 구현이 가능합니다. 그냥 뒤에서 부터 차곡 차곡 값을 쌓아가면 됩니다.
pop 구현
맨 나중값 순서로 값을 뺀다.
| class Stack: def \_\_init\_\_(self): self.data = \[\] def push(self, value): self.data.append(value) def pop(self): last\_value = self.data.pop() return last\_value |
|---|
스택의 특징은 값을 제거할 때 맨 마지막 값부터 제거한다고 하였습니다. pop()메서드를 사용하여 값을 제거해주면 되고, 추가로 마지막 갑은 반환 해줘야 합니다.
순수 기능을 가진 스택의 구현이 모두 끝났습니다.
큐 구현하기
큐의 기능 역시 두가지입니다. 값을 넣는다, 값을 뺀다(처음값 부터). 선입선출 방식이라고 설명 드렸었습니다. 두가지 기능을 중점으로 큐를 구현해봅시다.
큐 기능 뼈대 만들기
| class Queue: def \_\_init\_\_(self): pass def push(self, value): pass def pop(self): pass |
|---|
기능 뼈대 만들고 하나씩 구현해 봅시다!
push/pop 구현
두가지 방법
//
Queue의 기능은 크게 두가지 방법으로 구현이 가능합니다. 데이터를 어떻게 쌓아서 어떻게 제거할지에 따라 나뉩니다. 우선 첫번째 방법입니다. 이 방법을 push1이라 지칭하겠습니다. pop1과 연계해서 보시면됩니다.
데이터를 뒤로 쌓는 방법
| class Queue: def \_\_init\_\_(self): self.data = \[\] def push1(self, value): new\_list = \[value\] + self.data self.data = new\_list def pop1(self): first\_value = self.data.pop() return first\_value |
|---|
첫번째는 push함수를 매번 새로 만드는 방법입니다. 가령 1을 처음에 넣으면 \[1\]이 데이터로 저장됩니다. 이후에 2를 넣게되면 \[2 = value\] + \[1\] 배열 연산으로 \[2, 1\]이 데이터에 저장됩니다. 이런 방법으로 맨 마지막 자리로 데이터를 넣을 수 있습니다.
데이터 제거시에는 먼저 들어온 순서대로 뒤로 쌓이는 구조로 pop()함수를 사용해서 빠른 삭제가 가능합니다. 단점은 매번 리스트를 새로 만들어야 하므로 생성시 시간이 오래걸립니다.
데이터를 앞으로 쌓는 방법
| class Queue: def \_\_init\_\_(self): self.data = \[\] def push(self, value): self.data.append(value) def pop(self): self.data.pop(0) |
|---|
데이터를 앞에서 부터 쌓는 방법입니다. 앞서 Stack과 동일한 방법인데요. 일반적으로 많이 사용하는 방법이기도 합니다. push사용시 매번 리스트를 새로 만들지 않아도 되어 성능이 좋습니다. 단점으로는 pop(0)을 사용하게 될 경우 앞선 케이스의 pop()보다는 시간이 오래 걸릴 수 있습니다.
자료구조를 다양한 방법으로 구현하며 천천히 감을 익혀보세요!