스택

  • 한 쪽 끝에서만 item(항목)을 삭제하거나 새로운 item을 저장하는 자료구조
  • 새 item을 저장하는 연산: push
  • Top item을 삭제하는 연산: pop
  • 후입 선출(Last-In First-Out, LIFO) 원칙 하에 item의 삽입과 삭제 수행

파이썬 리스트로 구현한 스택

In [1]:
def push(item): # 삽입 연산
    stack.append(item)
    
def peek(): # top 항목 접근
    if len(stack) != 0:
        return stack[-1]

def pop(): # 삭제 연산
    if len(stack) != 0:
        item = stack.pop(-1)      
        return item

def print_list():
  for item in stack:
    print(item, " -> ", end='')
  print()

stack = []
push('apple'),  print_list()
push('orange'), print_list()
push('cherry'), print_list()
print('사과, 오렌지, 체리  push 후:\t', end='')
print(stack, '\t<- top')
print('top 항목: ', end='')
print(peek())
push('pear')
print('배 push 후:\t\t', end='')       
print(stack, '\t<- top')
pop()              
push('grape')
print('pop(), 포도 push 후:\t', end='')
print(stack, '\t<- top')

apple  -> 
apple  -> orange  -> 
apple  -> orange  -> cherry  -> 
사과, 오렌지, 체리  push 후:	['apple', 'orange', 'cherry'] 	<- top
top 항목: cherry
배 push 후:		['apple', 'orange', 'cherry', 'pear'] 	<- top
pop(), 포도 push 후:	['apple', 'orange', 'cherry', 'grape'] 	<- top

단순연결리스트로 구현한 스택

In [2]:
class Node: # Node 클래스  
    def __init__(self, item, link): # Node 생성자     
        self.item = item           
        self.next = link
                                
def push(item): # push 연산
    global top
    global size
    top = Node(item, top)  
    size += 1
    
def peek(): # peek 연산
    if size != 0:
        return top.item 
              
def pop(): # pop 연산
    global top
    global size
    if size != 0:
        top_item = top.item
        top = top.next
        size -= 1
        return top_item   
def print_stack(): # 스택 출력
    print('top ->\t', end='')
    p = top
    while p:
        if p.next != None:
            print(p.item, '-> ', end='')
        else:
            print(p.item, end='')
        p = p.next
    print()
top = None
size = 0
push('apple')
push('orange')       
push('cherry')       
print('사과, 오렌지, 체리  push 후:\t', end='')
print_stack()
print('top 항목: ', end='')
print(peek())              
push('pear') 
print('배 push 후:\t\t', end='')       
print_stack()
pop()               
push('grape')
print('pop(), 포도 push 후:\t', end='')           
print_stack()

사과, 오렌지, 체리  push 후:	top ->	cherry -> orange -> apple
top 항목: cherry
배 push 후:		top ->	pear -> cherry -> orange -> apple
pop(), 포도 push 후:	top ->	grape -> cherry -> orange -> apple

파이썬 리스트로 구현한 큐

In [3]:
def add(item): # 삽입 연산
    q.append(item)

def remove(): # 삭제 연산
    if len(q) != 0:
        item = q.pop(0)      
        return item

def print_q(): # 큐 출력
    print('front ->  ', end='')
    for i in range(len(q)):
        print('{!s:<8}'.format(q[i]), end='')
    print('  <- rear')
q = []
add('apple')       
add('orange')        
add('cherry')   
add('pear')
print('사과, 오렌지, 체리, 배 삽입 후: \t', end='')         
print_q()         
remove()
print('remove한 후:\t\t', end='')
print_q()           
remove()
print('remove한 후:\t\t', end='')
print_q()           
add('grape')
print('포도 삽입 후:\t\t', end='')
print_q()

사과, 오렌지, 체리, 배 삽입 후: 	front ->  apple   orange  cherry  pear      <- rear
remove한 후:		front ->  orange  cherry  pear      <- rear
remove한 후:		front ->  cherry  pear      <- rear
포도 삽입 후:		front ->  cherry  pear    grape     <- rear

단순연결리스트로 구현한 큐

In [4]:
class Node: 
    def __init__(self, item, n): # Node 생성자
        self.item = item
        self.next = n
def add(item): # 삽입 연산
    global size
    global front
    global rear
    new_node = Node(item, None) 
    if size == 0:
        front = new_node   
    else:
        rear.next = new_node
    rear = new_node
    size += 1      
def remove(): # 삭제 연산
    global size
    global front
    global rear
    if size != 0:
        fitem = front.item
        front = front.next
        size -= 1
        if size == 0: 
            rear = None 
        return fitem 
def print_q(): # 큐 출력
    p = front
    print('front: ', end='')
    while p:
        if p.next != None:
            print(p.item, '->   ', end='')
        else:
            print(p.item, end = '')
        p = p.next
    print('  : rear') 
front = None
rear = None
size = 0
add('apple')       
add('orange')        
add('cherry')   
add('pear')         
print('사과, 오렌지, 체리, 배 삽입 후: \t', end='')         
print_q()         
remove()
print('remove한 후:\t\t', end='')
print_q()           
remove()
print('remove한 후:\t\t', end='')
print_q()           
add('grape')
print('포도 삽입 후:\t\t', end='')
print_q()

사과, 오렌지, 체리, 배 삽입 후: 	front: apple ->   orange ->   cherry ->   pear  : rear
remove한 후:		front: orange ->   cherry ->   pear  : rear
remove한 후:		front: cherry ->   pear  : rear
포도 삽입 후:		front: cherry ->   pear ->   grape  : rear

데크 프로그램

In [5]:
from collections import deque
dq = deque('data')        
for elem in dq:     
    print(elem.upper(), end='')
print()
dq.append('r') 
dq.appendleft('k')
print(dq)
dq.pop()
dq.popleft() 
print(dq[-1])
print('x' in dq)
dq.extend('structure')
dq.extendleft(reversed('python'))
print(dq)

DATA
deque(['k', 'd', 'a', 't', 'a', 'r'])
a
False
deque(['p', 'y', 't', 'h', 'o', 'n', 'd', 'a', 't', 'a', 's', 't', 'r', 'u', 'c', 't', 'u', 'r', 'e'])
In [5]: