대학생 쩡딱구리
4-2. 연결 리스트로 스택, 큐 구현하기 본문
한방향 연결 리스트 내용 참고!
4-1. 한방향 연결 리스트
그동안 동적 배열과 동적 배열을 기반으로 한 자료구조를 다루었다. 하지만 동적 배열엔 아래와 같은 단점이 있다. 동적 배열의 길이가 저장하는 요소의 수보다 길다. 즉 메모리 낭비가 있다. �
jjeongttakgoori.tistory.com
1. 스택 구현
스택이 뭔지 기억이 안 난다면 이 글을 참고하면 좋을 것 같다.
3-1. 스택
1. 스택이란? 스택(Stack)이란 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료 구조이다. 스택은 LIFO(Last In First Out) 형태의 자료구조로, 가장 최근에 저장된 값 다음에 자료가 저장되고(push),
jjeongttakgoori.tistory.com
가장 먼저 들어간 것이 가장 나중에 나오는(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 answer1) 클래스 선언
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. 큐
3-1. 스택 1. 스택이란? 스택(Stack)이란 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료 구조이다. 스택은 LIFO(Last In First Out) 형태의 자료구조로, 가장 최근에 저장된 값 다음에 자료가 저장되
jjeongttakgoori.tistory.com
가장 먼저 넣은 것이 가장 먼저 나가는(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 += 11) 클래스 선언
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) |
다음 게시글에서는 원형 연결 리스트를 짧게 다룬다.
'STUDIES > DATA STRUCTURE' 카테고리의 다른 글
| 4-4. 양방향 연결 리스트 (0) | 2020.10.22 |
|---|---|
| 4-3. 원형 연결 리스트 (0) | 2020.10.21 |
| 4-1. 한방향 연결 리스트 (0) | 2020.10.19 |
| 3-3 덱 (0) | 2020.10.17 |
| 3-2. 큐 (0) | 2020.10.17 |