[전공 서적 번역] Stacks, Queues, and Deques

carpediem·2022년 9월 15일

Structure&Algorithm

목록 보기

3/4

Lecture 6

1. Stacks

A stack is a collection of objects that are inserted and removed according to the last-in, first-out (LIFO) principle.

→ 스택은 LIFO 정책을 갖고 있는 객체들의 집합이다.

→ 유저는 스택의 객체들을 아무때나 삽입이 가능하지만 삽입된 객체에 접근하거나 제거하기 위해서는 앞서 말한 정책을 따라야한다. 소위 말해 “top”에서만 접근이 가능한 것이다.

→ 인터넷 웹 브라우저에서 페이지 창의 뒤로가기 등의 기능은 스택의 정책을 사용한다고 볼 수 있다. 뒤로가기 버튼을 누르면 바로 이전 페이지가 pop되는것이다.

The Stack Abstract Data Type

스택의 추상화 데이터 타입인 예를들어 S (instance)는다음과 같은 methods들을 지원한다.

S.push(e) : element e를 stack S의 top에 더한다. 

S.pop() : top element를 반환하고 이를제거한다. (is empty 시 error)

S.top() : S의 top의 a reference element 를 반환한다.  (is empty 시 error)

S.is_empty() : S가 아무런 element를 가지고 있지 않다면 True 를 반환한다.

len(S) : ...

Simple Array-Based Stack Implementation
Implementing a Stack Using a Python List

class ArrayStack:
	def __init__(self):
		self._data = [] # empty python list for internal storage.
		
	def __len__(self):
		return len(self._data)
	
	def is_empty(self):
		return len(self._data) == 0

	def push(self, e):
		self._data.append(e)

	def top(self):
		if self.is_empty():
			raise Empty("Empty stack!")
		return self._data[-1]
	
	def pop(self):
		if self.is_empty():
			raise Empty("Empty stack!")
		return self._data.pop()

Analyzing the Array-Based Stack Implementation

→ Array-based stack에서는 각 메서드가 상수 시간의 시간복잡도를 가진다. 다만 push 그리고 pop의 기능은 amortized analysis상 list class랑 비슷한 bounds를 가지게 되고, push를 어디서 어떻게 하느냐에 따라 $O(n)$ 까지도 최악의 경우 가질 수 있다. 이는 pop도 마찬가지이다.

1.3 Reversing Data Using a Stack

Stack은순서 있는 데이터를 뒤집을 때 사용하는데 일반적으로 사용될 수 있다.

1.4 Matching Parentheses and HTML Tags

• Parentheses: “(” and “)”
• Braces: “{” and “}”
• Brackets: “[” and “]”

def is_matched(expr): # 모두 매칭에 성공하면 True를 반환한다. 그렇지 않은 경우 False.
	left_group = "({["
	right_group = ")}]"
	S = ArrayStack()
	for c in expr:
		if c in left_group:
			S.push(c)
		elif c in right_group:
			if S.is_empty():
				return False 
			item = S.pop() # item을 꺼내기 이전 S이 비어있는지 항상 확인부터 한다.
			if right_group.index(c) != left_group.index(item) : return False
	return S.is_empty() 
# stack이 비어있다면 모든 left_group이 꺼내져서 right_group과 검사한 셈이 되므로 
# Maching delimiters에 성공한다.

원리는 간단하다, left group과 right group을 나눠서 left 그룹을 순서대로 스택에 넣는다. 그런 다음 right 그룹이 등장하면 하나씩 꺼내서 짝이 맞는지 검사한다.

2. Queues

The queue abstract data type defines a collection that keeps objects in a
sequence, where element access and deletion are restricted to the first element in the queue, and element insertion is restricted to the back of the sequence.

→ 이에 대한 정의를 자세히 읽어보면 Queue라는 자료 구조는 역시 시퀀스 객체들에 대한 집합체에 대해 정의한 것이며, 각 원소들은 첫번째(first) 또는 마지막 (back)에서 접근이나 삭제가 허용되는 것을 알 수 있다. 이렇게 앞, 뒤로 자료의 삽입 삭제가 가능하며 먼저 들어온 원소가 먼저 나가는 정책을 가져 First-in, first-out FIFO 라고 불린다.

Q enqueue(e) : Q의 뒤에 원소 e를 더한다. dequeue() : Q에서 원소를 제거하고 첫번째 원소를 반환한다. Q가 비어있을 경우 에러를 일으킨다. first() : Q에 앞에 있는 원소를 바노한한다. (제거되진 않는다.) is_empty() : Q가 비어있는 경우 True를 반환한다. len() : Q안의 원소의 수를 반환한다. 파이썬의 경우 special method인 len으로 구현하였다.

2.2 Array-Based Queue Implementation

파이썬 list clas를 이용해서 손쉽게 simple한 adapter class를 만들어볼 수 있다. enqueue와 dequeue 는 append 그리고 pop으로 대치된다.
Chapter 5에서 다뤘던 것과 같이 list에서 pop(e) 의 경우, 특히 pop(0)를 하게 되는 경우 worst-case behavior가 $\Theta(n)$ 로 막을 수 없다.
따라서 본 책에서는 deque하는 경우 None을 참조하게 하고, explicit variable f가 Q의 front를 항상 가리키도록 하여 $O(1)$ 의 시간을 보장한다.
다만 이 접근법은 m번 만큼의 enque 크기를 갖게하여 사이즈가 $O(m)$ 가 되고, element 수만큼 이를 저장하는 스택과 다르게 공간을 많이 차지하게 된다.

Using an Array Circularly

이런 문제를 해결하고 좀 더 강건한 Q를 구현하기 위해서, Q의 앞이 다시 오른쪽으로 옮겨지도록 하는 방법을 쓰려고한다.

Cricularly한 형태의 queue를 만드는 것이다. 이렇게 되면 딱 필요한 공간만큼만 쓸 수 있다. f = 0으로 고정하는 것이 아니라 f = (f+1) % N 으로 두면 된다.
- 예를 들어, size 10인 f = 0으로 시작하는 queue가 있다고 생각해보자, 절대적인 공간도 10으로 제한하여 저장하는 queue이다. 여기서 3번을 dequeue를 하려고하면 size는 7이된다. 그리고 f는 (0+1) % 10 → (1+1) % 10 → (2+1) % 10 3이 된다.

Adding and Removing Elements

이런 형태는, 제한된 사이즈 10을 넘어갈 때 특징을 더욱 잘 살펴볼 수 있다.

예를 들어 front가 8이고 3개의 element가 존재 할 때, 삽입될 위치는 (8+3) % 10 11% 10 → 1.
- 1의 자리에 새로운 원소 e를 삽입한다.
Python Queue Implementation

from queue import Empty
class ArrayQueue:
    DEFAULT_CAPACITY = 10
    
    def __init__(self):
        self._data = [None] * ArrayQueue.DEFAULT_CAPACITY
        self._size = 0
        self._front = 0

    def __len__(self):
        return len(self._size)
    
    def __str__(self):
        return str(self._data)

    def is_empty(self):
        return self._size == 0

    def first(self):
        if self.is_empty():
            raise Empty("Queue is empty.")
        return self._data[self._front]

    def enqueue(self,e):
        if self._size == len(self._data):
            self._resize(2*len(self._data)) # insert index
        avail = (self._front + self._size) % len(self._data) 
        self._data[avail] = e
        self._size +=1
        return 

    def dequeue(self):
        if self.is_empty():
                raise Empty("Queue is empty.")	 # Empty class 
        item = self._data[self._front]
        self._data[self._front] = None
        self._front = (self._front + 1) % len(self._data)
        self._size -=1
        
        if 0 < self_size < len(self._data) //4 :
            self._resize(len(self._data) //2)
        return item

    def _resize(self, cap):
        old = self._data
        self._data = [None] * cap 
        walk = self._front
        for k in range(self._size):
            self._data[k] = old[walk]
            walk = (1+ walk) % len(old)
        self._front = 0

queue - A synchronized queue class - Python 3.10.5 documentation

_front 변수는 현재 큐의 첫번째 원소를 가리키고 있는 인덱스를 저장하고 있다.
_size는 현재 원소가 존재하는 개수(현재 들어 있는 원소의 인덱스의 +1)를 저장하고 있는 변수이다.

3 Double-Ended Queues

“Queue-like data structure that supports insertion and deletion at both the front and the back of the queue.”

→ 큐 자료구조는 First In First Out 이라는 정책에 맞게, 데이터가 나가는 방향이 앞으로 정해져있다. Double-ended Queue의 경우 이와 다르게 데이터의 삽입과 삭제를 앞, 뒤 모두 지원하며 이러한 구조의 특성 때문에 앞선 이름이 붙었다. 다른 말로 deque 데크라고도 부른다.

deque의 필요성과 관련해서 서적에는 레스토랑에서 손님을 관리하는 것에 그 비유를 들고 있는데, 첫 번 째 사람이 이용 가능한 테이블이 없어서 제거되었다가 다시 앞에 추가될 수 있고 마지막 손님이 기다리지 못하고 그냥 나가게 될 수도 있다. 이렇게 좀 더 general한 data structure에 대해서 이야기를 하고 있다.

3-1 The Deque Abstract Data Type

기본적인 기능, 시작과 끝에서 더하고(add) 제거하는(delete) 메서드를 지원하고 있다. 동시에 accessor 또한 지원하는데 처음과 마지막을 가리키고 있어 그 값을 반환할 수 있는 기능과 이를 통해 비어있는지 확인하는 is_empty와 그 길이를 반환하는 len 기능을 제공한다.

Resizing the Queue

enqueue 시, 사이즈가 데이터 저장공간과 같아지게 되는 경우 5.3.1의 DynamicArray에서 구현했던 것과 비슷하게 저장 공간을 두 배로 만들어주는 보편적인 테크닉을 진행하게 된다.
이 때, 공간을 늘리고 다시 컨텐츠들을 transfer하는 작업을 하게 되는데 재할당하는 과정에서 front가 0으로 다시 설정해주게 된다.

Shrinking the Underlying Array

마찬가지로 dequeue일 때, 메모리 공간을 효율적으로 활용하기 위해 capacity를 적절히 조절한다.
이를 위해서 요소가 전체 capacity의 1/4로 줄어들면 현재 capacity를 1/2 로 감소시킨다. 따라서 dequeue 메서드에 그와 같은 조건을 추가한다. ( ArrayQueue class 참고.)

3.2 Implementing a Deque with a Circular Array

ArrayQueue 와 구현방식이 거의 비슷하다. _data, _size, _front instance variables 가 존재하고 front 및 back 에 대해서 필요할때마다 modular arithmetic 연산을 한다.
마찬가지로 deque는 back의 index와 available한 slot이 있는지 알아야한다. last 메소드는 다음과 같이 back 인덱스를 사용한다.

💡 back = (self._front + self._size - 1 ) % len(self_data) 💡 self._front = (self._front - 1) % len(self._data)

ArrayDeque의 delete_first , add_last는 각각 Queue의 dequeue, enqueue 연산과 동일하다.

3.3 Deques in the Python Collections Module

Python에서 제공하는 collections.deque는 list class와 네이밍도 비슷하게 구현되었고, D[j]와 같이 인텍스 기반의 접근을 허용한다.
deque 라이브러리는 maxlen을 통해서 고정된 사이즈의 deque를 제공한다.
현재 collections에 있는 deque의 경우 circular arrays와 동시에 doubly linked list 로 구성된 block들로 구성이 되어있다.
아래는 deque의 ADT와 collections deque에서 제공하는 모듈들을 소개한다.