Python Linkedlist로 구현한 Stack

자료구조 Stack

 - 스택이란 한쪽 끝에서만 자료를 넣고 뺄 수 있는 선형구조(LIFO 특징)로 된 자료구조입니다.

 - 스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다

 

• S.top(): 스택의 가장 윗 데이터를 반환한다. 만약 스택이 비었다면 이 연산은 정의불가 상태이다.
• S.pop(): 스택의 가장 윗 데이터를 삭제한다. 스택이 비었다면 연산 정의불가 상태.
• S.push(): 스택의 가장 윗 데이터로 top이 가리키는 자리 위에(top = top + 1) 메모리를 생성, 데이터 x를 넣는다.
• S.empty(): 스택이 비었다면 1을 반환하고,그렇지 않다면 0을 반환한다.

 

 

linked list로 구현하는 stack 자료구조

class Node:
  def __init__(self, data):
      self.data = data
      self.next = None

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

  def push(self, data):
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node

  def pop(self):
    data = None
    if self.isEmpty():
      print("stack is empty")
    else:
      data = self.head.data
      self.head = self.head.next
    return data
    
  def isEmpty(self):
    is_empty = False
    if self.head == None:
      is_empty = True
    return is_empty

  def top(self):

    data = None
    if self.isEmpty():
      print("stack is empty")
    else:
      data = self.head.data
    return data


if __name__ == "__main__":
  a = Stack()
  print(a.top())
  a.push(10)
  print(a.top())
  a.push(20)
  print(a.top())
  a.push(30)
  print(a.top())
  print(a.pop())
  print(a.pop())
  print(a.pop())