자료구조 5장 | Linear Data Structure | 숙명여대 학점교류

학점교류로 듣는 숙명여대 자료구조

day 3. 2021.12.24. 금

 

---

Linear DS

Stack

Queue

Circular Queue

Expression Evaluation

Maze Problem

 

---

Stack 스택

last in first out LIFO

Stack and Queue

special types of ordered list

elements are inserted, deleted thru one end of stack, called top

 

applications

procedure call management

expression evaluation

 

Balanced Parenthesis

(5+6)*(9+8)/(6+2)

open close가 같아야 한다. 

 

Decimal to Binary

123(10) -> 1111011(2)

ㅇㅇ 이진수는 뒤에서부터 연결한다.

 

Function call

- system stack

a stack that manages function calls

if B() is called while A() is running, A() is paused until B() ends

whenever a new function is called, the context of current function must be stored in system stack as stack frame

A의 로컬 환경(현재 함수의 환경)을 저장하고 간다.

이때 Stack Frame이나 activation record를 이용해서 한다. 

 

def a():
	B()
def B():
	C()
    D()

def C()
def D()

SystemStack = [A]
SystemStack = [A,B]
SystemStack = [A,B,C]
...

 

LIFO Last in first outS = [a0, a1, ... , an-1]a0 : bottom elementan-1 : top elementstack operations : push, pop

 

- Stack Frame (activation record)local variablesaddress of the next instruction to resumea pointer to previous stack frame

 

Stack ADT- Implementation : linear list- operations : isEmpty(), stack_size(), push(), pop(), view(), peek_top()* peek_top : 마지막 원소가 무엇인지 '확인'

 

class Stack:
    def __init__(self):
        self.stack = []
    def empty(self):
        return len(self.stack)==0
    def size(self):
        return len(self.stack)
    def push(self, item):
        self.stack.append(item)
        self.view()
    def pop(self):
        if not self.empty():
            return self.stack.pop()
        else:
            print("Stack empty")
    def view(self):
        print(self.stack)
    def peek(self):
        if not self.empty():
            return self.stack[self.size()-1]
        else:
            return None

s = Stack()
for item in [3,4,5,6,7,8]:
    s.push(item)
print("stack size", s.size())
print("top", s.peek())

for i in range(7):
    print(s.pop(), end=' ')

 

Queue 큐

First in First Out FIFO

FCFS First Come First Served

Q = [a0,a1,...,an-1]

a0 : front

an-1 : rear

ai+1 is behind ai (0<=i<n)

elements are inserted/deleted at rear/front of queue, respectively

 

class Queue:
    def __init__(self):
        self.queue = []
    def empty(self):
        return len(self.queue)==0
    def size(self):
        return len(self.queue)
    def push(self, item):
        self.queue.append(item)
        self.view()
    def pop(self):
        if not self.empty():
            return self.queue.pop(0)
        else:
            print("Queue Empty")
    def peek(self):
        if not self.empty():
            return self.queue[0]
    def view(self):
        print(self.queue)

q = Queue()

for item in [3,4,5,6,7,8]:
    q.push(item)

print("front", q.peek())
print("Q size", q.size())

for i in range(6):
    print(q.pop(), end=' ')
    q.view()

 

(static) array based ordinary queue

ordinary queue scheduling jobs

a job queue without prioriity

job are processed ( deleted ) in order as they are inserted

뒤로 가서 추가하게 된다.

배열이 비효율적으로 메모리가 활용되게 된다.

Ordinary Queue

일반적인 static 선형 Queue의 문제

- Problem

Items in queue gradually shift to the right as they are added/deleted

False queue full

: queue full signal (rear == N-1) does not always mean that queue has actual N items

Item shifting to the left is required for resuming queue

: worst case - n-1 items

: TC = O(n)

- Solution

circular queue

 

 

 

Circular Queue 

array base circular queue

list를 쓰되 다른 방법을 쓰는 것이 좋다.

공간을 만들어두고 정적 공간처럼 쓰는 편이 좋다.

 

empty if front == reara full circular queue can contain at most n-1 element: one space must remain empty to distinquish from empty conditionno false full queue

cqueue는 full이 배열 크기 -1이라고 하셨는데 왜 full 함수에서는 self.count == self.size일 때 full이라고 판단하는 것인가요??

아~ front rear 비교하거나

cnt 이용하여 하는 방법이 있다. 

 

하나 빈칸이 있는 상태를 full queue라고 한다. 

empty 조건이 front == rear인데, 빈칸 없이 queue가 모두 차면 마찬가지로 front == rear가 되기 때문이다.

 

(**static array)

 

class CQueue:
    def __init__(self, size):
        self.front = 0
        self.rear = 0
        self.size = size
        self.cqueue = [None] * self.size  
        # static array 형태로 만든다
        # 현재 위치를 잘 파악하기 위한 장치
        self.count = 0
    def empty(self):
        return self.count == 0
    def full(self):
        return self.count == self.size
    def view(self):
        print(self.cqueue,\
            'F=%d R=%d' %(self.front, self.rear))
    def push(self, item):
        if not self.full():
            print("Push %2d" % item, end=' ')
            self.rear = (self.rear + 1) % self.size
            self.cqueue[self.rear] = item
            self.view()
            self.count += 1
        else:
            print("Queue full")
    def pop(self):
        if not self.empty():
            print("Pop  ", end=' ')
            self.front=(self.front+1)%self.size
            item = self.cqueue[self.front]
            self.cqueue[self.front] = None
            self.count -= 1
            self.view()
            return item
        else:
            print("Queue empty")
q = CQueue(5)
for item in [3,4,5]:
    q.push(item)
    
print(q.pop())
q.push(7)
q.push(9)
print(q.pop())
q.push(13)
print(q.pop())
q.push(15)
q.push(8)
q.push(10)

for i in range(6):
    print(q.pop())

 

Expression Evaluation 수식 변환

 

Maze Problem 미로

 

 

---