더디지만... 꾸준히...

1. 개요 & 알고리즘

"C로 배우는 알고리즘"^[각주:1]에서는 Stack을 배열과 Linked list로 구현하는 방법을 설명하는데, 이번글에서는 Linked list로 Stack을 구현해 봅니다. Stack은 입/출구가 하나이므로 단순 연결 리스트를 사용합니다.

2. 동작 코드

앞서 단순 연결 리스트와 관련해서 사용한 코드를 기초로 진행합니다.^[각주:2]

새로운 Node를 생성해서 linked list의 head쪽에 연결하는 push()를 아래와 같이 구현합니다. Python을 사용하므로 메모리 제한과 관련해서 특별히 고려하지 않았습니다.

def push(self, i):
    new_node = Node(i)
    new_node.key = i
    # Input to head side
    new_node.next = self.head.next
    self.head.next = new_node

    return i

Linked list의 head쪽에서 Node를 빼내오도록 pop()을 아래와 같이 구현합니다. empty case에 대해서도 고려했습니다.

def pop(self):
    # Output to head side
    t = self.head.next
    # Stack empty case
    if t == self.tail:
        return -1

    output = t.key
    self.head.next = t.next

    return output

Python이 자체적으로 메모리를 관리하므로, Stack을 지우는 경우는 단순히 head와 tail을 연결했습니다. 

def clear_stack(self):
    # Python manage memory automatically
    self.head.next = self.tail

3. 실행 코드

구현한 Stack을 사용한 예제 코드는 다음과 같습니다("C로 배우는 알고리즘" 리스트 3-10 : STACK2.C에 대응).

#main() function
if __name__ == "__main__":
    stack = Stack()

    print("Push 5, 4, 7, 8, 2, 1")
    stack.push(5)
    stack.push(4)
    stack.push(7)
    stack.push(8)
    stack.push(2)
    stack.push(1)
    stack.print_stack()

    print("Pop")
    i = stack.pop()
    stack.print_stack()
    print("Poped value is : ", i)

    # Don't test for memory full case

    print("Initialize stack")
    stack.clear_stack()
    stack.print_stack()

    print("Now stack is empty, pop")
    i = stack.pop()
    stack.print_stack()
    print("Poped value is : ", i)

4. 코드

1. 개요 & 알고리즘

Stack은 LIFO(Last In First Out)의 자료 구조로, 자료를 Stack에 넣는 push 동작과 자료를 가져오는 pop 동작으로 구성됩니다.^[각주:1] "C로 배우는 알고리즘"^[각주:2]에서는 배열과 Linked list로 구현하는 방법을 설명하는데, 이번글에서는 배열 관련 내용을 정리합니다.

2. 동작 코드

Python에서는 List 자체가 Stack의 기능을 제공합니다. 즉, push 동작은 append()를 사용하면 되며, pop은 pop()을 사용하면 됩니다.^[각주:3]

>>> stack = [3, 4, 5]
>>> stack.append(6) #6을 push
>>> stack.append(7) #7을 push
>>> stack
[3, 4, 5, 6, 7]
>>> stack.pop()
7
>>> stack
[3, 4, 5, 6]
>>> stack.pop()
6
>>> stack.pop()
5
>>> stack
[3, 4]
>>> stack.pop()
4
>>> stack.pop()
3
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: pop from empty list
>>>

3. 실행 코드

Python이 제공하는 기능을 그대로 사용해도 되겠지만, 조금 더 사용성을 고려해서 코드를 추가/구현할 수도 있겠습니다.^[각주:4]

1. 개요 & 알고리즘

간단한 텍스트뷰어를 이중 연결 리스트를 응용해서 작성해 봅니다. 이중 연결 리스트를 이용해서 텍스트 파일을 읽는 방법은 아래와 같습니다. ("C로 배우는 알고리즘"^[각주:1])

1. 파일을 연다.

2. 전체 라인 수를 0으로 초기화한다.

3. 파일의 끝에 도달할 때까지

3.1 파일에서 한 라인을 읽어서 buf에 저장한다.

3.2 buf에 저장된 문자의 길이가 80을 넘으면 자른다. (?)

3.3 새로운 노드를 생성하고 여기에 buf에 저장된 문자열을 복사한다.

3.4 새로 생성된 노드를 이중 연결 리스트의 제일 뒤에 삽입한다.

3.5 전체 라인 수를 증가시킨다.

3.6 3으로 돌아간다.

4. 파일을 닫고 끝낸다.

텍스트 파일을 보여 주는 동작은 PGUP, PGDN, ESC 키를 이용해서 동작합니다.

2. 동작 코드

텍스트 파일의 각 라인을 읽어서 double linked list를 구성하기 위한 기본적인 class는 다음과 같습니다.

class LineBufferNode:
    def __init__(self, line=""):
        self.line = line
        self.next = -1
        self.prev = -1

파일명을 인수로 받아서, 파일을 읽어서 double linked list를 구성하는 함수는 다음과 같습니다.

def load_file(self, file_name):
    fd = open(file_name, 'r')
    self.file_name = file_name
    self.total_line_num = 0

    print("File loading...")
    while (True):
        line_buffer = fd.readline()
        if not line_buffer:
            break

        new_line_buffer_node = LineBufferNode(line_buffer)
        new_line_buffer_node.prev = self.tail.prev
        new_line_buffer_node.next = self.tail
        self.tail.prev.next = new_line_buffer_node
        self.tail.prev = new_line_buffer_node

        self.total_line_num += 1

    fd.close()

파일에서 한 라인의 텍스트를 읽기 위해서 readline()함수를 사용했고, return 값이 없는 경우 EOF(End Of File)로 처리했습니다.^[각주:2], ^[각주:3]

Display하는 문자열을 반전하기 위해서 "curses.A_REVERSE"를 사용했습니다.

def show_header(self):
    string = " Text Viewer : " + self.file_name
    self.stdscr.addstr(0, 0, string, curses.A_REVERSE)
    self.stdscr.refresh()

하나의 페이지를 보이기 위해서 아래와 같은 함수를 작성했습니다. 윈도우의 command 창의 높이는 일정하지 않고 command 창을 변경하면 높이 값도 변경됩니다. 이에 command창의 라인수를 특정하지 않고 "try ... except"를 이용해서 error가 발생하기전까지는 계속 정상 출력하도록 했습니다.^[각주:4]

def show_page(self, line_node):
    # Clear screen
    self.stdscr.clear()
    # Show header
    self.show_header()

    line_num = 1
    # Can show total 29 lines (1 line for header and 28 lines for context
    while line_node != self.tail:
        try:
            self.stdscr.addstr(line_num, 0, line_node.line)
        except:
            break

        line_node = line_node.next
        line_num += 1

    self.stdscr.refresh()

    return line_num

키보드의 키 입력을 받아서 처리하도록 아래와 같이 작성했습니다. stdscr.getch()를 이용합니다. stdscr.getch()의 출력값은 integer입니다.print()를 이용해서 입력 받은 key 값을 출력하려면 chr(stdscr.getch()의 출력값)을 이용하면 됩니다.^[각주:5]

def key_proc(self):
    curses.noecho()
    self.stdscr.keypad(1)

    line_node = self.head.next
    line_num = self.show_page(line_node)

    while True:
        key = self.stdscr.getch()
        if key == curses.KEY_PPAGE: # Page Up
            line_node = self.move_line(-1*line_num, line_node)
            self.show_page(line_node)
        if key == curses.KEY_NPAGE: # Page Down
            line_node = self.move_line(line_num, line_node)
            self.show_page(line_node)
        if key == ord('q') or key == ord('Q'):
            break
        self.stdscr.refresh()

예를 들면 아래 코드를 사용해서 화면에 입력 받은 key를 출력할 수 있습니다.

self.stdscr.addstr(0, 0, chr(key))

3. 실행 코드

실행코드는 다음과 같습니다. ("C로 배우는 알고리즘" 리스트 3-8 : TVIEW.C에 대응)

# main() function
if __name__ == "__main__":
    # Get file name to read
    file_name = input("Please input file name to load -> ")

    # Initialize TextFileViewer class
    text_viewer = TextFileViewer()
    # Read file
    text_viewer.load_file(file_name)
    # Handle key input
    text_viewer.key_proc()

4. 코드