스택(Stack)

1) 스택(Stack)

  -  자료(Data element)를 단방향을 보관할 수 있는 (선형) 구조 

  - 단방향이므로 자료를 넣고(Push) 꺼낼 때(Pop) 한 쪽으로만 수행해야하는 제약이 있음 => 후입선출(LIFO)

 

  ※ Stack에서 발생하는 오류

    - 비어 있는 스택에서 데이터 원소를 꺼내려 할 때 → Stack Underflow

    -  꽉 찬 스택에 데이터 원소를 넣으려 할 때  → Stack Overflow

 

2) 스택의 추상적 자료구조 구현  

  ① 배열(array, list)을 이용하여 구현 → Python List 와 method들을 이용

class ArrayStack :
	def size(self) :				# 현재 스택에 들어 있는 데이터 원소의 수
    	return len(self.data)
    
    	def isEmpty(self) :				# 현재 스택이 비어 있는지를 판단
    		return self.size() == 0
   
    	def push(self, item) :				# 데이터 원소 itme을 스택에 추가
    		return self.data.append(item)
    
    	def pop(self) :					# 스택의 맨 위에 저장된 데이터 원소를 제거 및 반환
    		return self,data.pop()
    
    	def peek(self) :				# 스택의  맨 위에 저장된 데이터 원소를 반환 (제거 X)
    		return self.data[-1]

  ② 연결 리스트(Linked List)를 이용하여 구현 → 양방향 연결 리스트 이용

class LinkedListStack:

	def __init__(self):
		self.data = DoublyLinkedList()

	def size(self):
		return self.data.getLength()

	def isEmpty(self):
		return self.size() == 0

	def push(self, item):
		node = Node(item)
		self.data.insertAt(self.size() + 1, node)

	def pop(self):
		return self.data.popAt(self.size())

	def peek(self):
		return self.data.getAt(self.size()).data