간단하게 파이썬으로 구현했다.
스택 리스트를 두 개 만들어서 하나는 입력할 때 쓰는 스택, 하나는 queue에서 dequeue 할 때 사용하는 스택이다.
스택이든 큐든 push 할 때는 순서대로 들어가니 들어갈 때는 스택과 같다.
하지만 pop 할 때는 스택과 큐가 방식이 다르니 이중 스택을 이용해 큐와 같은 기능을 하게 한다.
class Stack(object):
stack_in = []
stack_out = []
# 입력할 땐 stack_in 으로 나올때 out 에 넣어서
def enqueue(self, item):
self.stack_in.append(item)
enqueue는 스택과 같이 뒤 부터 append로 채워 넣음
def dequeue(self):
if not self.stack_in:
print("it is empty")
else:
if not self.stack_out:
while self.stack_in:
self.stack_out.append(self.stack_in.pop())
return self.stack_out.pop()
-
먼저 지금까지 입력 스택이 비어있다면 dequeue를 할 수 없으므로 현재 스택 요소가 하나라도 있는 지 확인해야 함.
-
스택 out이 없으면 stack_in을 돌면서 모든 요소를 stack_out에 넣어줌
버그 : dequeue를 두번 하면 stack_in을 모두 pop 해버리기 때문에 두 번 dequeue를 하면 it is empty 가 나와버린다.
가설은 앞 두 개 원소가 나와야 하지만.
버그를 수정하려면 pop이 아니라 del 마지막 원소를 써서 수정해주어야 함
def dequeue(self):
if not self.stack_in:
print("it is empty")
else:
if not self.stack_out:
for i in range(1, len(self.stack_in)+1):
self.stack_out.append(self.stack_in[-i])
del self.stack_in[-1]
return self.stack_out.pop()
위와 같이 수정해주어서 stack_out의 뒤에서부터 삭제하는게 queue의 앞부터 삭제 하는 것과 같은 효과를 내게 해줌
버그 추가 : enqueue를 dequeue를 한 후 하게 되면 stack_out은 동기화 되지 않아, 값에 오류가 생긴다. dequeue를 할 때 마다 stack_in과 stack_out을 동기화 시켜주기 위해 stack_out을 초기화하고 stack_in을 재할당할 필요가 있음.
결국 삭제의 시간복잡도가 급격하게 올라가 버리게 되었다.
def dequeue(self):
if not self.stack_in:
print("it is empty")
else:
if self.stack_out:
self.stack_out = []
for i in range(1, len(self.stack_in)+1):
self.stack_out.append(self.stack_in[-i])
tmp = self.stack_out.pop()
self.stack_in = []
for i in range(1, len(self.stack_out)+1):
self.stack_in.append(self.stack_out[-i])
return tmp
이렇게 코드를 수정하면 stack_out의 stack_in 동기화 문제는 해결된다.
하지만 stack_out에서 pop을 했으므로 다시 stack_out에서 stack_in으로 동기화를 다시 해줘야함
def show_list(self):
return self.stack_in
def index(self, idx):
if len(self.stack_in) < idx:
print("index overflow the list size")
else:
return self.stack_in[idx]
위와 같이 list를 보는 메소드와 인덱스를 통해 list 요소를 조회하는 메소드를 각각 추가해준다.
위와 같이 처리하면 더 이상 확인되는 버그는 없다.
def test():
stack = Stack()
stack.enqueue(1)
stack.enqueue(2)
stack.enqueue(3)
stack.enqueue(4)
print(stack.show_list())
print(stack.dequeue())
print(stack.dequeue())
print(stack.stack_in)
print(stack.stack_out)
print(stack.show_list())
print(stack.dequeue())
stack.enqueue(5)
print(stack.dequeue())
print(stack.show_list())
stack.enqueue(10)
stack.enqueue(11)
print(stack.index(1))
print(stack.show_list())
test()
결과 값 :
[1, 2, 3, 4]
1
2
[3, 4]
[4, 3]
[3, 4]
3
4
[5]
10
[5, 10, 11]삽입의 시간복잡도는 O(1)
삭제의 시간복잡도는 O(n)
삭제할 때마다 stack_out을 초기화해서 stack_in을 계속 옮겨주고 또 stack_in 을 stack_out으로 동기화 두 번 하므로 시간이 많이 소모된다. 공간도 역시 두 배
조회의 시간복잡도는 O(1) 인덱스를 통해 바로 접근 가능
핵심은 리스트의 맨 앞 원소를 삭제하는 시간
vs
stack_in을 stack_out으로 동기화 시키고 pop을 한 후 stack_out을 다시 stack_in 으로 동기화 해주는 시간
