STACK이란?

이지우·2024년 12월 17일
Dequequeuestack개념정리덱스택자료구조큐
post-thumbnail

STACK

스택의 개념

모든 자료의 삽입과 삭제가 한쪽 끝에서만 수행되는 제한적 개념의 선형 구조

LIFO(Last In First Out)인 자료구조로 먼저 들어가 요소가 나중에 나오게 된다

재귀함수를 호출할 때 호출 당한 함수가 끝난 뒤 호출을 한 함수가 끝나는 것과 같이 스택에 들어간 요소가 나오기 위해서는 그 이후에 삽입한 요소들이 모두 나와야 한다

  • 실생활에서의 스택의 예
    • 식당에 쌓여있는 접시 더미
    • 책상에 쌓여있는 책
    • 창고에 쌓여있는 상자
  • 스택의 활용
    • 자료의 출력 순서가 입력의 역순으로 이루어져야 할 때
    • undo기능을 구현할 때
    • 함수 호출에서 복귀주소를 기억할 때
    • 문서나 소스코드에서 괄호 닫기가 정상적으로 되었는지를 검사하는 프로그램
  • 스택 용어
    • 스택 상단(stack top): 스택에서 입출력이 이루어지는 부분
    • 스택 하단(stack bottom): 스택의 바닥 부분
    • 요소(element): 스택에 저장되는 것
    • 공백 스택(empty stack): 요소가 하나도 없는 스택
  • 스택 연산
    • isFull(s) : 스택의 원소 수가 size와 동일할 경우 return TRUE, 다를 경우 return FALSE
    • isEmpty(s) : 스택의 원소 수가 0일 경우 return TRUE, 0보다 클 경우 return FALSE
    • push(s, e) : isFull(s)을 실행하여 스택이 꽉 차있으면 에러를 발생시키고 빈 공간이 있을 경우 스택의 맨 위에 e 추가
    • pop(s) : isEmpty(s)를 실행하여 스택이 비어있으면 에러를 발생시키고 스택에 요소가 있으면 스택의 맨 위에 있는 요소를 제거하여 반환
    • peek(s) : isEmpty(s)를 실행하여 스택이 비어있으면 에러를 발생시키고 스택에 요소가 있으면 스택의 맨 위에 있는 요소를 제거하지 않고 반환
  • 스택 코드
    # Plus: 각 리스트 값에 1씩 더해준다
# ex) 1 2 3 4 5 -> 2 3 4 5 6
# isReverse: 리스트를 거꾸로 바꿔준다
# ex) 1 2 3 None None -> None None 3 2 1
# Reset: 리스트 안을 다 None로 초기화 시켜주고 top을 -1로 함
# ex) 1 2 3 4 5 -> None None None None None

class Stack:
    def __init__(self, size):
        self.stack_size = size  # 리스트 용량
        self.stack_list = [None] * self.stack_size  # 리스트 이름
        self.top = -1  # 가장 최근에 삽입된 요소의 위치

    def isEmpty(self):  # top이 -1이면 비어있다고 판단
        if self.top == -1:
            return True
        else:
            return False

    def isFull(self):  # top이랑 stack_size가 같으면 가득 찼다고 판단
        if self.top == self.stack_size:
            return True
        else:
            return False

    def push(self, e):  # 요소 e를 스택의 맨 위에 추가
        if self.isFull() == True:
            print("배열이 가득 찼습니다")
            return 0
        self.top += 1
        self.stack_list[self.top] = e

    def pop(self):  # 스택의 맨 위에 있는 요소를 꺼내 반환
        if self.isEmpty() == True:
            print("배열이 텅 비었습니다")
            return 0
        tmp = self.stack_list[self.top]
        self.stack_list[self.top] = None
        self.top -= 1

        return tmp

    def peek(self):  # 스택의 맨 위에 있는 항목을 삭제하지 않고 반환
        return self.stack_list[self.top]

    def isReverse(self):  # 리스트를 거꾸로 바꿈
        self.stack_list.reverse()
        return 0

    def Reset(self):  # 리스트 안을 다 None로 초기화 시켜주고 top을 -1로 함
        if self.isEmpty() == True:
            print("배열이 텅 비었습니다")
            return 0
        for i in range(-1, self.stack_size):
            self.stack_list[i] = None
        self.top = -1

    def Plus(self):  # 각 리스트 값에 1씩 더함
        if self.isEmpty() == True:
            print("배열이 텅 비었습니다")
            return 0
        for i in range(self.top, -1, -1):
            self.stack_list[i] += 1

stack = Stack(5)

print("push 확인")
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.push(5)
print(stack.pop())
print(stack.stack_list)
print(stack.peek())
print(stack.stack_list)
stack.Plus()
print(stack.stack_list)
stack.isReverse()
print(stack.stack_list)

stack.Reset()

print(stack.stack_list)
  • 중위표기 수식의 후위표기 변환

    전위

    연산자를 먼저 표시하고 연산에 필요한 피연산자를 나중에 표기하는 방법 ex) +ab

    중위

    연산자를 두 피연산자 사이에 표기하는 방법으로 가장 일반적으로 사용되는 표현 방법 ex) a+b

    후위

    피연산자를 먼저 표시하고 연산자를 나중에 표시하는 방법 ex) ab+
    """
전위: +ab
중위: (a+b)/c
후위: ab+
"""
"""
중위를 후위로 바꿀 때 나올 수 있는 경우의 수 3가지
1. a+b*c -> abc*+
연산자를 담을 스택을 만들어 놓고 output이라는 결과를 순서대로 넣어놓는 리스트를 만든다
연산자는 stack에 넣고 피연산자는 output에 넣는다
stack에 든 게 있는 지 확인하고 
있다면
stack에서 한 개씩 pop해서 output에 넣어서 출력
2. a*b+c -> ab*c+ 
연산자를 담을 스택을 만들어 놓고 output이라는 결과를 순서대로 넣어놓는 리스트를 만든다
연산자는 stack에 넣고 피연산자는 output에 넣는다
stack에 넣을 연산자가 stack안에 들어있던 연산자랑 우선순위를 비교해서 stack에 있는 게 더 높은 우선순위가 있다면 
다 pop해서 output결과 리스트에 넣고 넣을 연산자를 stack에 집어 넣는다
다 분류했다면
stack에서 한 개씩 pop해서 output에 넣어서 출력
3. (a+b)*c ->
(를 stack에 집어넣는다
)괄호를 넣을 차례일 때 (를 만날 때까지 그 위에 들어있는 연산자를 모두 pop해서 output리스트에 넣어준다
다 분류했다면
stack에서 한 개씩 pop해서 output에 넣어서 출력
"""
# 피연산자인가 연산자인가 / 연산자에서 ()인가 +인가 *인가
"""
def 우선순위
if () return 0 
    + return 1
    * return 2
"""

# 스택 ADT

# push(e) : 요소 e를 스택의 맨 위에 추가
# pop() : 스택의 맨 위에 있는 요소를 꺼내 반환한다.
# isEmpty() : 스택이 비어있는 true를 아니면 false를 반환한다.
# isFull() : 스택이 가득 차 있으면 true를 아니면 false를 반환한다.
# peek() : 스택의 맨 위에 있는 항목을 삭제하지 않고 반환한다.

class Stack:
    stack_size = 100
    stack_list = [None] * stack_size
    top = -1

    def isEmpty(self):
        if self.top == -1:
            return True
        else:
            return False

    def isFull(self):
        if self.top == self.stack_size - 1:
            return True
        else:
            return False

    def push(self, e):
        if self.isFull() == True:
            print("배열이 가득 찼습니다")
            return 0

        self.top += 1
        self.stack_list[self.top] = e

    def pop(self):
        if self.isEmpty() == True:
            print("배열이 텅 비었습니다")
            return 0

        print(self.stack_list[self.top])
        r = self.stack_list[self.top]
        self.stack_list[self.top] = None
        self.top -= 1
        return r

    def peek(self):
        print(self.stack_list[self.top])

# 연산자 우선순위 계산 함수
def precedence(op):
    if op == "(" or op == ")":
        return 0
    elif op == "+" or op == "-":
        return 1
    elif op == "*" or op == "/":
        return 2
    else:
        return -1

# 중위 표기 -> 후위표기로 바꾸는 함수
def Infix2Postfix(expr):
    s = Stack()
    output = []

    for term in expr:
        if term in "(":
            s.push("(")
        elif term in ")":
            while not s.isEmpty():
                op = s.pop()
                if op == "(":
                    break
                else:
                    output.append(op)

        elif term in "+-*/":
            while not s.isEmpty():
                op = s.peek()
                if precedence(op) >= precedence(term):
                    output.append(op)
                    s.pop()
                else:
                    break
            s.push(term)
        else:
            output.append(term)

    while not s.isEmpty():
        output.append(s.pop())

    return output

"""
stack = Stack()

print("push 확인")
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.push(5)

print(stack.stack_list)
"""
infix1 = input()
infix1 = list(infix1)
postfix1 = Infix2Postfix(infix1)
print(postfix1)

QUEUE

큐의 개념

뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조

FIFO(First In First Out)인 자료구조로 먼저 들어가 요소가 먼저 나오게 된다

큐는 한쪽 끝에서 삽입 작업, 다른 쪽 끝에서 삭제 작업이 이루어진다

  • 실생활에서의 큐의 예
    • 줄을 서서 기다리는 것
  • 큐의 활용
    • 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
    • 은행 업무
    • 콜센터 고객 대기시간
    • 프로세스 관리
    • 너비 우선 탐색(BFS) 구현
    • 버퍼(buffer): 데이터를 주고 받을 때 각 주변장치들 사이에 존재하는 속도의 차이나 시간차이를 극복하기 위해 임시 기억장치로 사용
    • 실시간 비디오 스트리밍(버퍼링 buffering)
    • 현실 세계 시뮬레이션
  • 큐의 연산
    • init(q) : 큐를 초기화
    • isEmpty(q) : size가 0이면 TRUE 반환, 0이 아니면 FALSE 반환
    • isFull(q) : size와 max_size가 같으면 TRUE 반환, 다르면 FALSE 반환
    • enqueue(q, e) : isFull이 TRUE면 에러 발생, FALSE면 q의 끝에 e 추가
    • dequeue(q) : isEmpty가 TRUE면 에러 발생, FALSE면 q의 맨 앞에 있는 요소 제거하여 반환
    • peek(q) : isEmpty가 TRUE면 에러 발생, FALSE면 q의 맨 앞에 있는 요소 제거하지 않고 반환

선형 큐의 개념

데이터가 증가되면 rear를 하나 증가하고 그 위치에 데이터가 저장되며 삭제할 때도 front를 하나 증가하고 front가 가리키는 위치에 있는 데이터를 삭제한다

  • 단점
    • 요소들의 불필요한 이동이 발생한다
    • 큐의 앞 부분이 비더라도 자료를 추가할 수 없다(메모리 낭비)
  • 선형 큐 코드
    """
AllPrint(): None이 아닌 배열에 있는 수 모두 출력
ex) [1, 2, 3, 4, None] -> [1, 2, 3, 4]가 출력됨
AllPrintReverse(): None이 아닌 배열에 있는 수 거꾸로 하여 모두 출력
ex) [1, 2, 3, 4, None] -> [4, 3, 2, 1]가 출력됨
Reset(): 배열 초기화
ex) 1, 2, 3, 4, None -> None, None, None, None, None
"""

class Queue:
    def __init__(self, size):
        self.queue_size = size
        self.list = [None] * self.queue_size
        self.front = -1
        self.rear = -1

    def isFull(self):  # rear랑 크기-1이 같으면 가득 찼음
        return self.rear == self.queue_size - 1

    def isEmpty(self):  # front랑 rear가 같으면 비어있음
        return self.front == self.rear

    def enqueue(self, e):  # 요소 e를 큐의 맨 뒤에 추가
        if self.isFull():
            print("큐가 가득 찼습니다")
            return 0
        self.rear = self.rear + 1
        self.list[self.rear] = e

    def dequeue(self):  # 큐의 맨 앞에 있는 요소를 꺼내 반환
        if self.isEmpty():
            print("큐가 비어있습니다")
            return 0
        self.front = self.front + 1
        tmp = self.list[self.front]
        self.list[self.front] = None
        return tmp

    def peek(self):  # 큐의 맨앞에 있는 요소를 삭제하지 않고 반환
        if self.isEmpty():
            print("큐가 비어있습니다")
            return 0
        return self.list[self.front + 1]

    def AllPrint(self):  # 배열에 있는 수 모두 출력
        if self.isEmpty():
            print("큐가 비어있습니다")
            return 0
        tmp = [i for i in self.list if i is not None]
        print(tmp)

    def AllPrintReverse(self):  # 배열에 있는 수 거꾸로 하여 모두 출력
        if self.isEmpty():
            print("큐가 비어있습니다")
            return 0
        tmp = [i for i in self.list if i is not None]
        print(tmp[::-1])

    def Reset(self):  # 배열 초기화
        if self.isEmpty():
            print("큐가 비어있습니다")
            return 0
        for i in range(-1, self.queue_size):
            self.list[i] = None

        self.front = -1
        self.rear = -1

queue = Queue(5)

queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.enqueue(4)
queue.enqueue(5)

print(queue.list)
print(queue.peek())
queue.AllPrint()
queue.AllPrintReverse()
queue.Reset()
print(queue.list)

원형 큐의 개념

기본 큐의 처음과 끝을 논리적으로 연결하여 오버플로가 발생하는 것을 보완한다

(front와 rear의 값이 배열의 끝인(MAX_QUEUE_SIZE-1)에 도달하면 다음에 증가되는 값은 0이 되도록 한다)

  • 문제 full 상태와 empty 상태일 때 front와 rear 값이 같음 → 이를 해결하기 위해 front와 rear 사이에 하나의 공백을 둠
  • 상태 포화 상태: (rear+1)%n == front 공백 상태: front == rear
  • 원형 큐 코드
    """
AllPrint(): None이 아닌 배열에 있는 수 모두 출력
ex) [1, 2, 3, 4, None] -> [1, 2, 3, 4]가 출력됨
AllPrintReverse(): None이 아닌 배열에 있는 수 거꾸로 하여 모두 출력
ex) [1, 2, 3, 4, None] -> [4, 3, 2, 1]가 출력됨
Reset(): 배열 초기화
ex) 1, 2, 3, 4, None -> None, None, None, None, None
"""

class Queue:
    def __init__(self, size):
        self.queue_size = size
        self.list = [None] * self.queue_size
        self.rear = 0
        self.front = 0

    def isEmpty(self):  # front랑 rear가 같으면 비어있음
        return self.front == self.rear

    def isFull(self):  # (rear+1)%5랑 front가 같으면 가득 차 있음
        return (self.rear + 1) % 5 == self.front

    def equence(self, e):  # 요소 e를 큐의 맨 뒤에 추가
        if self.isFull():
            print("큐가 가득 찼습니다")
            return 0
        self.rear = (self.rear + 1) % 5
        self.list[self.rear] = e

    def dequence(self):  # 큐의 맨 앞에 있는 요소를 꺼내 반환
        if self.isEmpty():
            print("큐가 비어있습니다")
            return 0
        self.front = (self.front + 1) % 5
        self.list[self.front] = None
        return self.list[self.front]

    def peek(self):  # 큐의 맨앞에 있는 요소를 삭제하지 않고 반환
        if self.isEmpty():
            print("큐가 비어있습니다")
        return self.list[(self.front + 1) % 5]

    def AllPrint(self):  # 배열에 있는 수 모두 출력
        if self.isEmpty():
            print("큐가 비어있습니다")
            return 0
        tmp = [i for i in self.list if i is not None]
        print(tmp)

    def AllPrintReverse(self):  # 배열에 있는 수 거꾸로 하여 모두 출력
        if self.isEmpty():
            print("큐가 비어있습니다")
            return 0
        tmp = [i for i in self.list if i is not None]
        print(tmp[::-1])

    def Reset(self):  # 배열 초기화
        if self.isEmpty():
            print("큐가 비어있습니다")
            return 0
        for i in range(-1, self.queue_size):
            self.list[i] = None
        self.front = 0
        self.rear = 0

queue = Queue(5)

print("push 확인")
queue.equence(1)
queue.equence(2)
queue.equence(3)
queue.equence(4)
queue.dequence()
print(queue.peek())
queue.AllPrint()
queue.AllPrintReverse()

""" 오늘 수업에서 알게된 점
큐에는 
선형큐, 원형큐, 우선수위 큐 이렇게 세가지로 있다!
"""

DEQUE

덱의 개념

덱은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조

(여전히 중간에 삽입하거나 삭제하는 것은 허용하지 않는다)

큐와 스택을 합친 형태

  • 배열로도 구현이 가능하고, 연결 리스트로도 구현이 가능
  • 데이터의 앞과 뒤에서만 삽입, 삭제, 접근이 이루어질 때 굉장히 빠르게 동작
  • 회전 전단 반시계방향 회전: (front1+capacity)%capacity 후단 반시계방향 회전: (rear-1+capacity)%capacity
  • 덱 연산
    • create() : 덱 생성
    • init(dq) : 덱 초기화
    • isEmpty(dq) : 덱이 공백 상태인지 검사
    • isFull(dq) : 덱이 포화 상태인지 검사
    • AddFront(dq, e) : 덱의 앞에 요소 추가
    • AddRear(dq, e) : 덱의 뒤에 요소 추가
    • DeleteFront(dq) : 덱의 앞의 요소 반환 후 삭제
    • DeleteRear(dq) : 덱의 뒤의 요소 반환 후 삭제
    • GetFront(dq) : 덱의 앞의 요소 반환(삭제x)
    • GetRear(dq) : 덱의 뒤의 요소 반환(삭제x)
  • 선형 덱 코드
    class Deque:
    def __init__(self, Deque_size):
        self.Deque_size = Deque_size
        self.front = -1
        self.rear = self.Deque_size
        self.list = [None] * self.Deque_size

    def isEmpty(self): #rear랑 크기가 같고 front가 -1이면 비어있음
        return self.rear == self.Deque_size and self.front == -1

    def isFull(self): #front랑 크기-1이 같거나 rear가 0이면 가득 참
        return self.front == self.Deque_size - 1 or self.rear == 0

    def AddFront(self, e):  # 맨 앞(전단)에 새로운 요소 e를 추가
        if self.isFull():
            print("덱이 가득 차있습니다")
            return 0
        self.front += 1
        self.list[self.front] = e

    def DeleteFront(self):  # 맨 앞(전단)의 요소를 꺼내서 반환
        if self.isEmpty():
            print("덱이 비어있습니다")
            return 0
        tmp = self.list[self.front]
        self.list[self.front] = None
        self.front -= 1
        return tmp

    def GetFront(self):  # 맨 앞(전단)의 요소를 꺼내지 않고 반환
        return self.list[self.front]

    def AddRear(self, e):  # 맨 뒤(후단)에 새로운 요소e를 추가
        if self.isFull():
            print("덱이 가득 차있습니다")
            return 0
        self.rear -= 1
        self.list[self.rear] = e

    def DeleteRear(self):  # 맨 뒤(후단)의 요소를 꺼내서 반환
        if self.isEmpty():
            print("덱이 비어있습니다")
            return 0
        tmp = self.list[self.rear]
        self.list[self.rear] = None
        self.rear += 1
        return tmp

    def GetRear(self):  # 맨 뒤(후단)의 요소를 꺼내지 않고 반환
        return self.list[self.rear]

deque = Deque(5)

deque.AddFront(1)
deque.AddFront(2)
deque.AddRear(1)
deque.AddRear(2)
print(deque.list)
  • 원형 덱 코드
    class Deque:
    def __init__(self, Deque_size):
        self.Deque_size = Deque_size
        self.front = 0
        self.rear = 0
        self.list = [None] * Deque_size

    def isEmpty(self): #front랑 rear가 같으면 비어있음
        return self.front == self.rear

    def isFull(self): #front랑 (rear_1)%크기가 같으면 가득 참
        return self.front == (self.rear + 1) % self.Deque_size

    def Addfront(self, e):  # 맨 앞(전단)에 새로운 요소 e를 추가
        if self.isFull():
            print("덱이 가득 찼습니다")
            return 0
        self.list[self.front] = e
        self.front = (self.front - 1 + self.Deque_size) % self.Deque_size

    def Addrear(self, e):  # 맨 뒤(후단)에 새로운 요소e를 추가
        if self.isFull():
            print("덱이 가득 찼습니다")
            return 0
        self.rear = (self.rear + 1) % self.Deque_size
        self.list[self.rear] = e

    def Deletefront(self):  # 맨 앞(전단)의 요소를 꺼내서 반환
        if self.isEmpty():
            print("덱이 비어있습니다")
            return 0
        self.front = (self.front + 1) % self.Deque_size
        return self.list[self.front]

    def Deleterear(self):  # 맨 뒤(후단)의 요소를 꺼내서 반환
        if self.isEmpty():
            print("덱이 비어있습니다")
            return 0
        self.rear = (self.rear - 1 + self.Deque_size) % self.Deque_size
        return self.list[self.rear]

    def Getfront(self): # 맨 앞(전단)의 요소를 꺼내지 않고 반환
        if self.isEmpty():
            print("덱이 비어있습니다")
            return 0
        return self.list[(self.front + 1) % self.Deque_size]

    def Getrear(self): # 맨 뒤(후단)의 요소를 꺼내지 않고 반환
        if self.isEmpty():
            print("덱이 비어있습니다")
            return 0
        return self.list[self.rear]

deque = Deque(5)
deque.Addfront(1)
deque.Addfront(2)
deque.Addrear(2)
print(deque.list)
profile
이지우
이전 포스트

시스템 프로그래밍 내용 정리(Part 4_개요/IP 주소와 포트 번호)

다음 포스트

[물류 통합 관리 ERP 시스템 개발일지] Vue와의 만남

0개의 댓글