스택, 큐 개념과 구현 in python3

스택의 개념

스택 자료구조는 말 그대로 책을 쌓는 것처럼 쌓아올린 형태의 자료구조를 말한다.
Last in First Out(LIFO) 방식으로 데이터가 출입하며, 따라서 맨 위에 있는 데이터가 가장 최근에 있는 데이터가 된다. 삽입은 Push, 삭제는 Pop이라는 명칭을 쓴다.

큐의 개념

큐 자료구조는 줄이라는 의미를 가지고 있는 단어 그 자체로 선입선출의 특징을 가진다.
First in First Out(FIFO) 방식으로, 큐의 앞단에는 삭제만 일어나고, 뒤에서는 삽입만 일어난다.

큐의 종류

1) 선형 큐
선형 큐는 배열을 선형으로 나타낸 형태이다. 자료의 삽입이나 삭제가 용이하나, 삽입 및 삭제를 반복하다 보면, 맨 마지막 인덱스를 가리키는데 앞에는 비어있을 수 있으나 꽉 찼다고 인식하는 문제점이 발생한다. (이는 삭제 때마다 한 칸 앞으로 데이터를 이동시키지 않아, 인덱스 단위로 큐의 연산을 진행했기 때문)

2) 원형 큐
배열을 원형의 모습을 표현한 것으로 배열의 처음과 끝을 연결한 형태이다. 초기 공백 상태에서 front, rear 값을 0으로 하여 포인터를 움직이며 큐에 데이터를 입력한다.

스택 구현

class Stack:
	def __init__(self):
    		self.items = []			# 데이터 저장을 위한 리스트 준비
        
   	def push(self, val):
    		self.items.append(val)
            
    	def pop(self):
        	try:
            	    return self.items.pop() 	#pop할 아이템이 없으면
            except IndexError:
            	print("Stack is empty")		#indexError 발생
        
        def top(self):
        	try:
                    return self.items[-1]
            	except IndexError:
                    print("Stack is empty")
                    
         def __len__(self):			#len()로 호출하면 stack의 item 수 반환
         	return len(self.items)

큐 구현

class Queue:
	def __init__(self):
    	self.items = []			# 데이터 저장을 위한 리스트 준비
        self.front_index = 0	# 다음 dequeue될 값의 인덱스 기억
        
    def enqueue(self, val):
    	self.items.append(val)
        
    def dequeue(self):
    	if self.front_index == len(self.items):
        	print("Queue is empty")
            return None			# dequeue할 아이템이 없음을 의미
        else: 
       	    x=self.items[self.front_index]
            self.front_index += 1
            return x

** 본 포스트는 아래의 레퍼런스를 바탕으로 만들었습니다.
한국외대 컴퓨터전자시스템 공학부 신찬수 교수님 유투브:
https://www.youtube.com/watch?v=kGZoEShMcSQ&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=13