Python에서 스택을 사용하여 대기열을 다른 대기열로 정렬할 수 있는지 확인

처음 n개의 자연수(정렬되지 않음)가 있는 대기열이 있다고 가정합니다. 주어진 Queue 요소가 스택을 사용하여 다른 Queue에서 감소하지 않는 순서로 정렬될 수 있는지 확인해야 합니다. 이 문제를 해결하기 위해 다음 작업을 사용할 수 있습니다. -

• 스택에서 요소 푸시 또는 팝
• 주어진 대기열에서 요소를 삭제합니다.
• 다른 대기열에 요소를 삽입합니다.

따라서 입력이 Que =[6, 1, 2, 3, 4, 5]와 같으면 Que에서 6을 꺼낸 다음 스택에 푸시할 수 있으므로 출력은 True가 됩니다. 이제 나머지 모든 요소를 ​​Que에서 다른 큐로 팝한 다음 스택에서 6을 팝하고 두 번째 큐로 푸시하면 새 큐의 모든 요소가 감소하지 않는 순서로 정렬됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• n :=큐의 크기
• stk :=새 스택
• exp_val :=1
• 앞:=null
• que가 비어 있지 않은 동안 do
  • front :=que의 앞 요소
  • que에서 앞 요소 제거
  • front가 exp_val과 같으면
    • exp_val :=exp_val + 1
  • 그렇지 않으면
    • stk가 비어 있으면
      • stk로 푸시 프론트
    • 그렇지 않으면 stk가 비어 있지 않고 stk의 맨 위
    • 거짓을 반환
  • 그렇지 않으면
    • stk로 푸시 프론트
• stk가 비어 있지 않고 스택의 맨 위가 exp_val과 같을 때 do
  • stk에서 팝
  • exp_val :=exp_val + 1

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

from queue import Queue
def solve(que):
   n = que.qsize()
   stk = []
   exp_val = 1
   front = None
   while (not que.empty()):
      front = que.queue[0]
      que.get()
      if (front == exp_val):
         exp_val += 1
      else:
         if (len(stk) == 0):
            stk.append(front)
         elif (len(stk) != 0 and stk[-1] < front):
            return False
         else:
            stk.append(front)
   while (len(stk) != 0 and stk[-1] == exp_val):
      stk.pop()
      exp_val += 1
   if (exp_val - 1 == n and len(stk) == 0):
      return True
   return False
que = Queue()
items = [6, 1, 2, 3, 4, 5]
for i in items:
   que.put(i)
print(solve(que))

입력

[6, 1, 2, 3, 4, 5]

출력

True