스택

• 스택은 기본 자료구조에 규칙을 포함한 확장형 자료구조
• 스택의 규칙은 새로운 데이터를 저장할 때 항상 가장 마지막에 저장하며 이러한 저장 동작을 push, 저장된 데이터를 불러올 때 pop 동작이라고 정의

실습 예제

간단한 스택 추가 및 삭제

stk = [10, 20, 30]
print(stk)
stk.append(40)
print(stk)
stk.pop()
print(stk)

빈 스택에 데이터 추가, 삭제하기

• 빈스택에 시작해 데이터를 하나씩 추가
• 1:삽입, 2:삭제, 3:종료
• 만약 더이상 삭제할 데이터가 없으면 매시지 표시

stack = []

while True:
    a = int(input("1 : 삽입, 2 : 삭제, 3 : 종료"))
    if a == 1:
        input_data = input()
        stack.append(input_data)
        print(stack)
    elif a == 2:
        if len(stack) == 0:
            print("데이터가 없습니다")
        else:
            del_data = stack.pop()
            print(del_data)
    else:
        break

후기 표기법을 사용한 우선순위 연산

• push(): 스택 가장 마지막에 데이터 삽입
• pop() : 스택의 가장 마지막 데이터 읽음, 스택의 가장 마지막 데이터 삭제

stack = []

a = list(input().split(","))

def push(input_data):
    stack.append(input_data)

def pop():
    del_data = stack[-1]
    stack.remove(stack[-1])
    return del_data

for i in a:
    if i == "+" or i == "-" or i == "*" or i == "/":
        pop_data = pop()
        pop_data2 = pop()

        if i == "+":
            push(pop_data2 + pop_data)
        elif i == "-":
            push(pop_data2 - pop_data)
        elif i == "*":
            push(pop_data2 * pop_data)
        else:
            push(pop_data2 / pop_data)
    else:
        push(i)

큐

• 큐는 기본 자료구조에 규칙을 포함한 확장형 자료구조
• 새로운 데이터를 저장할 때 항상 가장 마지막에 저장하는데, 이 저장 동작을 Enqueue라고 하며, 저장된 데이터를 불러올 때 가장 처음에 저장된 데이터를 불러오며 Dequeue라고 함

실습 예제

간단하게 큐 구성하기

queue = [1, 2, 3]
print(queue)

queue.append(4)
queue.append(5)
print(queue)

print(queue.pop())
print(queue)

은행 업무 프로그램

w_no = 100
queue = []

def enqueue(data):
    queue.append(data)

def dequeue(data):
    deq_ob = None
    if len(queue) ==0:
        print("queue is empty")
    else:
        deq_ob = queue[0]
        queue.remove(queue[0])

    return deq_ob

while True:

    a = int(input("1 : 뽑기, 2: 업무처리, 3:종료"))

    if a == 1:
        enqueue(w_no):
        w_no += 1
        print(w_no)
    elif a == 2:
        b == dequeue()
        print(b)
    else:
        break

queue 라이브러리 이용하기

import queue

data = [1,2,3,4,5]
que = queue.Queue()

# que에 data값 입력
for i in data:
    que.put(i)
    print(que.qsize())

# que에서 값 출력
for i in range(que.qsize()):
    print(que.get())
    print(que.qsize())

• 데크(deque)를 이용해서 표현
  - 데크(deque : double-ended queue)는 덱이라고도 읽는다.
  - 큐는 큐이지만 스택과 큐의 기능을 모두 가지고 있어 데이터를 양방향에서 추가하고 제거할 수 있는 자료구조

  deque.append() : deque의 오른쪽 끝에 삽입
  
  deque.appendleft() : 덱의 왼쪽 끝에 삽입
  
  deque.insert() : 특정 인덱스 값을 삽입
  
  deque.extent() : 주어진 값(배열 포함) 덱 오른쪽에 추가
  
  deque.pop() : deque의 오른쪽 끝값을 제거 및 반환
  
  deque.poplist() : deque의 왼쪽 끝값을 제거 및 반환
  
  deque.remove() : 삭제하고 싶은 값을 deque에서 찾으며, 삭제

deque 라이브러리 이용하기

from collections import deque

que = deque([1,2,3])
que.append(4)
que.append(5)
print(que)

que.appendleft(0)
print(que)

que.insert(2,7)
print(que)

arr = [8,9]
que.extend(arr)
print(que)

print(que.pop())
print(que)

print(que.popleft())
print(que)

que.remove(7)
print(que)

연습문제 1

• 스택과 큐를 이용한 문제 해결방법, 회문 찾기 문제를 풀어보자
• Palindrome이란 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 단어, 숫자, 문자열을 말한다
• 기러기 등등
• 큐와 스택에 문자열을 저장

def palindrome(data):

    stack = []
    q = []
    for word in data:
        stack.append(word)
        q.append(word)
    for word in data:
        if stack.pop() == q.pop(0):
            print("True")
        else:
            print("False")

data = input()

연습문제 2

• 출력문에서 괄호를 확인하는 스택문제

stack = []
cnt = 0

for i in a:
    if i == "(":
        stack.append(i)
        print(stack)
        cnt += 1
    elif i == ")":
        stack.pop()
        print(stack)
        cnt -= 1
    else:
        pass
if cnt == 0:
    print("OK")
else:
    print("error")