Python: Stack 구현하기

Stack python으로 구현하기

class Stack:
    def __init__(self):
        self.items =[]
    
    def push(self, value):
        self.items.append(value)
    
    def pop(self):
        if not self.items:
            return None
        return self.items.pop()

stack 구조로 배열 구현하기

class StackArray:
    def get(self, idx):
        if idx < 0 or idx >= self.size:
            raise Exception("Out of Range!")
        #idx 이상의 값을 넣으면 순서가 섞이게 됨

        for i in range(self.size):
            self.stack2.push(self.stack1.pop())
        
        for i in range(idx):
            self.stack1.push(self.stack2.pop())
        
        value = self.stack2.pop()
        
        self.stack1.push(value)
    
        for i in range(self.size - idx - 1):
            self.stack1.push(self.stack2.pop())
        
        return value
    
    def set(self, idx, value):
        if if idx < 0 or idx >= self.size:
            raise Exception("Out of Range!")
        
        for i in range(self.size):
            self.stack2.push(self.stack1.pop())
        
        for i in range(idx):
            self.stack1.push(self.stack2.pop())
        
        self.stack2.pop()
        self.stack1.push(value)
        
        for i in range(self.size - idx -1):
            self.stack1.push(self.stack2.pop())

    def __init__(self, size):
        self.size = size
        self.stack1 = Stack()
        for i in range(size):
            self.stack1.push(None)
        self.stack2 = Stack()

Stack 으로 연결리스트 구현하기

class StackList:
    def move_next(self):
        value = self.stack2.pop()
        
        if value == None:
            return ("End of List")
				#마지막 까지가면 더 이상 데이터가 움직일수 없도록 조건
        
        self.stack1.push(value)

    def get(self):
        value = self.stack1.pop()
        self.stack1.push(value)

        return value

    def add(self, value):
        self.stack1.push(value)

    def delete(self):
        self.stack1.pop()

    def move_front(self):
        while True:
            value = self.stack1.pop()
            if value == None:
                self.stack1.push(self.stack2.pop())
                break
            #break는 반복문 탈출

            self.stack2.push(value)

    def __init__(self):
        self.stack1 = Stack()
        self.stack2 = Stack()

두개의 스택을 만들고 첫번째 스택의 마지막 인덱스가 current 첫번째 인덱스는 head

두번째 인덱스에 뒤의 데이터가 역순으로 저장 되어있음

Stack으로 Queue 구현하기

class StackQueue:
    def enqueue(self, value):
        self.stack1.push(value)
    
    def dequeue(self):
        while True:
            value1 = self.stack1.pop()
            if value1 == None:
                break
            self.stack2.push(value1)
            
        value = self.stack2.pop()
        
        while True:
            value2 = self.stack2.pop()
            if value2 == None:
                break
            self.stack1.push(value2)
        
        return value
				#변수의 저장위치를 생각할 것!
    
    def __init__(self):
        self.stack1 = Stack()
        self.stack2 = Stack()