4-2. 연결 리스트로 스택, 큐 구현하기

한방향 연결 리스트 내용 참고!

4-1. 한방향 연결 리스트

 

1. 스택 구현

스택이 뭔지 기억이 안 난다면 이 글을 참고하면 좋을 것 같다.

3-1. 스택

스택

 가장 먼저 들어간 것이 가장 나중에 나오는(LIFO) 스택을 연결 리스트로 만들면 O(1) 시간 복잡도를 갖는다.

이때 Linked List의 head를 stack의 top으로 사용한다.

연결 리스트로 구현한 스택

파이썬 코드로 LinkedStack 클래스를 구현해보자. 전체 코드를 살펴본 다음, 부분으로 나눠서 다시 보자.

class Empty(Exception):
	"""Error attempting to access an element from an empty container."""
pass

class LinkedStack:
	"""LIFO Stack implementation using a singly linked list for storage."""
	
    class _Node:
    	"""Lightweight, nonpublic class for storing a singly linked node."""
        __slots__ = '_element', '_next'			# streamline memory usage
        
        def __init__(self, element, next):		# initialize node's fields
        	self._element = element			# reference to user's element
            	self._next = next

	def __init__(self):
    		"""Create an empty stack."""
        	self._head = None
        	self._size = 0

	def __len__(self):
    		"""Return the number of elements in the stack."""
        	return self._size
    
	def is_empty(self):
    		"""Return True if the stack is_empty."""
        	return self._size == 0

	def push(self, e):
    		"""Add element e to the top of the stack."""
        	self._head = self._Node(e, self._head)	# create and link a new node
        	self._size += 1
        
	def top(self):
    		"""Return (but do not remove) the element at the top of the stack.
        	Raise Empty exception if the stack is_empty."""
       		if self.is_empty():
        		raise Empty('Stack is_empty')
        	return self._head._element		# top of stack is at head of list

	def pop(self):
    		"""Remove and return the element from the top of the stack.(i.e., LIFO).
        	Raise Empty exception is the stack is_empty."""
        	if self.is_empty():
        		raise Empty('Stack is_empty')
        	answer = self._head._element
        	self._head = self._head._next		# bypass the former top node
        	self._size -= 1
        	return answer

---

1) 클래스 선언

class Empty(Exception):
	"""Error attempting to access an element from an empty container."""
pass

class LinkedStack:
	"""LIFO Stack implementation using a singly linked list for storage."""

 

2) Node 클래스 선언: Node 클래스를 외부에 보이지 않도록 nonpublic class로 선언

    class _Node:
    	"""Lightweight, nonpublic class for storing a singly linked node."""
        __slots__ = '_element', '_next'			# streamline memory usage
        
        def __init__(self, element, next):		# initialize node's fields
        	self._element = element			# reference to user's element
            	self._next = next

 

3) 초기화

• self._head: head node 관리(단, tail을 별도로 관리하지 않음)
• self._size: 길이 정보를 빠르게 제공하기 위해 별도로 관리

	def __init__(self):
    		"""Create an empty stack."""
        	self._head = None
        	self._size = 0

 

4) 스택에 저장된 요소 개수: self._size를 return

	def __len__(self):
    		"""Return the number of elements in the stack."""
        	return self._size

 

5) 스택이 비었는지 확인: self._size가 0이면 True, 아니면 False로

	def is_empty(self):
    		"""Return True if the stack is_empty."""
        	return self._size == 0

 

6) push: 새로운 노드를 만들어서 head 앞에 추가, 크기도 1 증가.

	def push(self, e):
    		"""Add element e to the top of the stack."""
        	self._head = self._Node(e, self._head)	# create and link a new node
        	self._size += 1

 

7) Top 요소를 반환: 스택이 비어 있으면 Empty Exception 발생, head의 요소 반환

	def top(self):
    		"""Return (but do not remove) the element at the top of the stack.
        	Raise Empty exception if the stack is_empty."""
        	if self.is_empty():
        		raise Empty('Stack is_empty')
        	return self._head._element		# top of stack is at head of list

 

8) pop

• 스택이 비어 있으면 Empty Exception 발생
• head의 다음 요소 반환
• head의 다음 노드를 새로운 head로 지정하고 크기는 1 줄임.

	def pop(self):
    		"""Remove and return the element from the top of the stack.(i.e., LIFO).
        	Raise Empty exception is the stack is_empty."""
        	if self.is_empty():
        		raise Empty('Stack is_empty')
        	answer = self._head._element
        	self._head = self._head._next		# bypass the former top node
        	self._size -= 1
        	return answer

 

2. 성능 분석

연결 리스트로 스택을 구현하면 모든 연산이 O(1) 시간 복잡도를 갖는다.

Operation	Running Time
S.push(e)	O(1)
S.pop()	O(1)
S.top()	O(1)
S.is_empty()	O(1)
len(S)	O(1)

 

3. 큐 구현

큐에 대해서는 이 게시글을 참고!

3-2. 큐

큐

가장 먼저 넣은 것이 가장 먼저 나가는(FIFO) 큐는 연결 리스트로 구현 시 모든 연산이 O(1)이다. 구현 시 Linked List의 head를 front로, tail을 back으로 사용한다.

연결 리스트로 큐 구현하기

파이썬 코드로 LinkedQueue 클래스를 구현해보자.

class Empty(Exception):
	"""Error attempting to access an element from an empty container."""
pass

class LinkedQueue:
	"""FIFO queue implementation using a singly linked list for storage."""
    
    class _Node:
    	"""Lightweight, nonpublic class for storing a singly linked node."""
        __slots__ = '_element', '_next'			# streamline memory usage
        
        def __init__(self, element, next):
        	self._element = element
            	self._next = next

	def __init__(self):
    		"""Create an empty queue."""
        	self._head = None
        	self._tail = None
        	self._size = 0				# number of queue elements

	def __len__(self):
    		"""Return the number of elements in the queue."""
        	return self._size
        
	def is_empty(self):
    		"""Return True if the queue is_empty."""
        	return self._size == 0

	def first(self):
    		"""Return (but do not remove) the element at the front of the queue.
        	Raise Empty exception if the queue is_empty."""
        	if self.is_empty():
        		raise Empty('Queue is_empty')
        	return self._head._element		# front aligned with head of list
        
	def dequeue(self):
    		"""Remove and return the first element of the queue (i.e., FIFO).
        	Raise Empty exception if the queue is_empty."""
       		if self.is_empty():
        		raise Empty('Queue is_empty')
        	if self._size == 1:			# special case as queue is_empty
        		self._tail = None		# remove head had been the tail
        	answer = self._head._element
        	self._head = self._head._next
        	self._size -= 1
        	return answer
	
    	def enqueue(self):
		"""Add an element to the back of queue."""
            	newest = self._Node(e, None)		# node will be new tail node
            	if self.is_empty():
            		self._head = newest		# special case: previously empty
            	else:
            		self._tail._next = newest
            	self._tail = newest			# update reference to tail node
            	self._size += 1

---

1) 클래스 선언

class Empty(Exception):
	"""Error attempting to access an element from an empty container."""
pass

class LinkedQueue:
	"""FIFO queue implementation using a singly linked list for storage."""

 

2) Node 클래스 선언: Node 클래스를 외부에 보이지 않도록 nonpublic class로 선언

    class _Node:
    	"""Lightweight, nonpublic class for storing a singly linked node."""
        __slots__ = '_element', '_next'			# streamline memory usage
        
        def __init__(self, element, next):
        	self._element = element
            	self._next = next

 

3) 초기화

• self._head: head node 관리
• self._tail: tail 노드 관리
• self._size: 큐에 저장된 데이터 개수

	def __init__(self):
    		"""Create an empty queue."""
        	self._head = None
        	self._tail = None
        	self._size = 0				# number of queue elements

 

4) 길이: self._size를 return

	def __len__(self):
    		"""Return the number of elements in the queue."""
        	return self._size

 

5) 큐가 비어 있는지 확인: self._size가 0이면 True, 아니면 False로

	def is_empty(self):
    		"""Return True if the queue is_empty."""
        	return self._size == 0

 

6) 큐의 첫 번째 요소를 반환

• 큐가 비어 있으면 Empty Exception 발생
• 큐가 비어 있지 않으면 head의 요소 반환

	def first(self):
    		"""Return (but do not remove) the element at the front of the queue.
        	Raise Empty exception if the queue is_empty."""
        	if self.is_empty():
        		raise Empty('Queue is_empty')
        	return self._head._element		# front aligned with head of list

 

7) dequeue

• 큐가 비어 있으면 Empty Exception 발생
• head의 다음 요소를 answer로 저장해 두었다가 반환
• head는 다음 노드로 이동시키고 크기는 1 줄임
• 큐가 비었으면 tail을 None으로 설정
• answer 반환

	def dequeue(self):
    		"""Remove and return the first element of the queue (i.e., FIFO).
        	Raise Empty exception if the queue is_empty."""
       		if self.is_empty():
        		raise Empty('Queue is_empty')
        	if self._size == 1:			# special case as queue is_empty
        		self._tail = None		# remove head had been the tail
        	answer = self._head._element
        	self._head = self._head._next
        	self._size -= 1
        	return answer

 

8) enqueue

• 새로운 노드를 생성
• 큐가 비어 있으면 head로 지정
• 큐가 비어 있지 않으면 새로운 노드를 tail에 연결
• tail을 새로운 노드로 이동, 크기도 1 증가

    	def enqueue(self):
		"""Add an element to the back of queue."""
            	newest = self._Node(e, None)		# node will be new tail node
            	if self.is_empty():
            		self._head = newest		# special case: previously empty
            	else:
            		self._tail._next = newest
            	self._tail = newest			# update reference to tail node
            	self._size += 1

 

4. 성능 분석

 연결 리스트로 큐를 구현하면 모든 연산이 O(1) 시간 복잡도를 갖는다.

Operation	Running Time
Q.enqueue(e)	O(1)
Q,dequeue(e)	O(1)
Q.first()	O(1)
Q.is_empty()	O(1)
len(Q)	O(1)

 

다음 게시글에서는 원형 연결 리스트를 짧게 다룬다.