python - 스택(stack)

‍Juhee Kim·2021년 7월 26일
0

스택 (stack)

배열의 끝에서만 데이터를 접근할 수 있는 선형 자료구조
LIFO(Last in First out)

스택이 컴퓨터 프로그램에서 활용되는 예시 : 윈도우 프로그램(컴퓨터종료 시, 가장 먼저 운영체제가 구동되고 가장 마지막으로 종료된다.)

  • push : 스택 맨 끝(맨 위)에 항목을 삽입
  • pop : 스택 맨 끝 항목을 반환하는 동시에 제거
  • top/peek : 스택 맨 끝 항목 조회
  • empty : 스택이 비어 있는지 확인
  • size : 스택 크기 확인

🎯 리스트 메소드를 사용해서 스택만들어보기

stack = [3, 4, 5]
stack.append(6)
stack.append(7)
print(stack)
# 결과 : [3, 4, 5, 6, 7]

stack.pop()
print(stack)
# 결과 : [3, 4, 5, 6]

stack.pop()
print(stack)
# 결과 : [3, 4, 5]

stack.pop()
print(stack)
# 결과 : [3, 4]

위의 코드처럼 push와 pop을 활용해서 공간에 값이 유동적으로 변한다.(동적처리)

코드 구현 - 리스트

class Stack:
    def __init__(self):
        self.data = []    # 동적처리(리스트값이 정해져있지 않음, 대괄호만 선언 및 저장)
        
    def push(self, item): # append 함수를 사용하여 리스트 끝에 값 추가
        self.data.append(item)

    def pop(self): # pop 함수를 사용하여 리스트 끝의 값 삭제
    	value = self.data.pop()
        
        if value is not None:
        	return value
        else :
        	print("Stack is empty")

    def size(self):  #스택 크기 반환
      return len(self.data)

    def peek(self): #리스트 인덱싱을 이용하여 top리스트의 가장 마지막 원소(자료)를 반환시킨다.
      if self.items:
        return self.data[-1]

      else :
        print('The stack is empty')

코드 구현 - 연결리스트 개념과 단순 변수를 사용

  • 아래의 코드는 스택이 내부적으로 어떻게 작동되는지 확인하기 위해 작성되었다.
  • 파이썬에서 자체적으로 제공하는 리스트의 append, pop 메소드를 활용하면 쉽게 구현될 수 있지만,
  • 아래처럼 다른 방법으로도 구현하는 코드를 보면서 스택에 대한 이해도를 높일 수 있다.
class LinkedListNode:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.top = None

    def push(self, data):
        # 신규 노드 생성
        new_node = LinkedListNode(data)
        # 최상단의 노드를 신규 노드 다음 노드로 삽입
        new_node.next = self.top
        # 신규 노드를 최상단에 삽입
        self.top = new_node
        return new_node.data

    def pop(self):
        # 스택이 비어있는지 확인
        if self.top is not None:
            # 최상단의 노드를 삭제할 노드로 삽입
            popped_node = self.top
            # 삭제할 노드 다음 노드를 최상단의 노드로 삽입
            self.top = popped_node.next
            # 삭제할 노드로부터 값 리턴
            return popped_node.data
  • 스택에 내부적으로 값을 쌓고 pop하는 과정을 살펴본다.
s = Stack()

print('push :',s.push(1))
print('push :',s.push(4))
print('push :',s.push(5))
print('pop :',s.pop())    # 마지막 값을 pop한다.
  • 결과
    push : 1
    push : 4
    push : 5
    pop : 5
profile
찐문과생의 빅데이터 생존기🐣 열심히 할래용 (ง •_•)ง

0개의 댓글