3. Stack/Queue

1. 1개의 배열로 3개의 스택

index가 나머지가 0,1,2

 

2. 최솟값을 반환하는 min 연산 추가

push, pop, min 은 O(1)

 

스택 하나 더 선언(M)

def push(x):
	if x<S.top():
    	M.append(x)
    else:
    	M.append(S.top())
    S.append(x)
    
    
def pop():
	if len(S) > 0:
      x = S.pop()
      M.pop()
      return x
    
def min():
	if len(M) > 0:
      return M[-1]

 

3. 일정 용량을 초과하는 경우 새로운 스택 생성

class stackList():
	def __init__(lim):
    	self.stacks = [[]]
        self.stacknum = 0
        self.limit = lim
        
    def push(x):
    	if len(self.stacks[-1]) > self.limit :
        	self.stacks.append([])
            self.stacknum += 1
    	
        self.stacks[-1].append(x)

	def pop():
        if len(self.stacks[-1]) > 0:
        	x = self.stacks[-1].pop()
        if self.stacks[-1] == 0:
        	self.stacks.pop()
          	self.stacknum -= 1
        return x


SetOfStack = stackList(M)

 

4. stack 2개로 큐 하나 구현

class Q:
	def __init__():
    	self.S1 = []
        self.S2 = []
        
    def push(x):
    	self.S1.append(x)
        
    def pop():
    	for i in range(len(S1)-1):
        	self.S2.append(self.S1.pop())
        x = S1.pop()
        for j in range(len(S2)):
        	self.S1.apppend(self.S2.pop())
        return x

 

5. 스택 정렬

def getMax(S, sorted):
	if not S: return sorted
    M = 0
	for i in range(len(S)):
    	x = S.pop()
    	if M < x:
        	M = x
            sorted.append(x)
        else:
        	S.append(x)
	getMax(S, sorted)

 

6. cat and dog queue

큐 2개 이용

큐에 넣을 때 들어온 시간도 같이 저장.