스택(Stack), 큐(Queue)

스택(Stack)

https://yoongrammer.tistory.com/45

스택은 프로그래밍에서 사용되는 기본적이면서도 중요한 자료구조 중 하나이며, 선형 자료구조이다.

데이터를 임시 저장하고 관리하는데 사용되며, 특히 데이터의 입력과 출력순서가 후입선출(LIFO, Last In First Out) 방식으로 이루어진다.

 

스택의 특징

• 스택은 한쪽 끝에서만 데이터를 넣거나 뺄 수 있는 선형 자료 구조이다.
• 데이터의 추가(push)와 삭제(pop)가 같은 쪽에서 이루어지며, 가장 마지막에 들어온 데이터가 가장 먼저 나가는 구조를 가진다.
• 스택은 웹 브라우저의 뒤로 가기 기능, 함수 호출 시의 콜 스택 관리, 괄호 검사 , DFS(깊이 우선 탐색)등 다양한 애플리케이션에서 활용된다.

 

스택의 기본 연산

• push() : 스택에 데이터를 추가하는 작업. 스택의 가장 위에 테이터를 넣는다.
• pop() : 스택에서 데이터를 제거하는 작업. 스택의 가장 위에 있는 데이터를 빼내며, 가장 최근에 추가된 데이터가 제거된다.
• peek() : 스택의 가장 위에 있는 데이터를 조회하는 작업. 데이터를 제거하지 않고, 현재 스택의 상태를 확인 가능하다.
• isEmpty() : 스택이 비어있는지 확인. 스택이 비어있으면 true, 아니면 false를 반환
• isFull() : 스택이 가득 차 있는지 확인. 스택의 최대 크기에 도달했으면 true, 아니면 false를 반환
• getSize() : 스택에 있는 요소의 수를 반환. 스택의 크기를 나타내는 정수값을 얻을 수 있다.

예시)

class Stack:
    def __init__(self, size):
        self.stack = []
        self.size = size

    def push(self, item):
        if not self.isFull():
            self.stack.append(item)
        else:
            print("스택이 가득 찼습니다!")

    def pop(self):
        if not self.isEmpty():
            return self.stack.pop()
        else:
            print("스택이 비어있습니다!")
            return None

    def peek(self):
        if not self.isEmpty():
            return self.stack[-1]
        else:
            print("스택이 비어있습니다!")
            return None

    def isEmpty(self):
        return len(self.stack) == 0

    def isFull(self):
        return len(self.stack) == self.size

    def getSize(self):
        return len(self.stack)

# 스택 사용 예시
stack = Stack(3)
stack.push(1)
stack.push(2)
stack.push(3)

print("현재 스택:", stack.stack)
print("스택 크기:", stack.getSize())
print("맨 위의 요소:", stack.peek())

stack.push(4)  # 스택이 가득 찼으므로 추가되지 않음
print("pop 연산 결과:", stack.pop())
print("현재 스택:", stack.stack)

 

스택은 프로그래밍에서 매우 유용하게 사용되는 자료구조이며, 특히 데이터의 처리 순서가 중요한 경우, 스택을 활용하여 효율적으로 문제를 해결할 수 있다.

스택의 구현 방법에는 배열 기반과 연결 리스트 기반 구현이 있으며, 선택은 사용 사례와 성능 요구사항에 따라 달라질 수 있다.

각 연산의 시간 복잡도는 일반적으로  O(1) 이다. 즉, 스택의 크기에 관계없이 일정한 시간 내에 연산을 수행할 수 있다.

 

---

큐(Queue)

https://yoongrammer.tistory.com/46

큐도 스택과 같이 프로그래밍에서 사용되는 기본적이면서도 중요한 자료구조 중 하나이며, 선형 자료구조이다.

큐는 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO, First in First Out) 원칙에 따라 작동하는 자료구조이다.

 

큐의 특징

• 먼저 들어온 데이터가 먼저 나가는 FIFO 형식이다.
• 데이터는 큐의 뒤에서 삽입되고, 앞에서 삭제된다. 이로 인해 데이터의 순서가 일정하게 유지된다.
• 기본적인 선형 큐 외에도 원형 큐, 우선순위 큐, 덱(Deque) 등 다양한 형태의 큐가 있어, 상황에 맞게 선택하여 사용할 수 있다.
• 큐의 예시로는 프린터의 인쇄 작업 대기열 관리, 운영체제의 태스크 스케줄링, BFS(너비 우선 탐색) 등이 있다.

 

큐의 기본 연산

• enqueue() : 큐의 끝(rear)에 항목을 추가해 새로운 데이터를 삽입하는 동작. 이는 큐에 데이터를 추가하는 기본적인 방법이며, 큐가 가득 차 있지 않으면, rear 위치에 데이터를 추가하고, rear를 한 칸 이동시킨다.
• dequeue() : 큐의 맨 앞(front)에 항목을 제거해 데이터를 없애고 반환하는 동작. 큐에서 데이터를 제거하는 기본적인 방법이며, front 위치의 데이터를 제거하고, front를 한 칸 이동시킨다.
• peek() : 큐의 맨 앞(front)에 있는 항목을 제거하지 않고 단순히 확인만 하는 동작. 큐의 front 위치에 있는 데이터를 반환한다.
• isFull() : 큐가 가득 찼는지 확인하는 동작. 큐의 저장 공간이 모두 차 있으면 true, 아니면 false를 반환한다.
• isEmpty() : 큐가 비어 있는지 확인하는 동작. 큐가 비어 있으면 true, 아니면 false를 반환한다.

예시)

class Queue:
    def __init__(self, size):
        self.queue = []
        self.size = size

    def enqueue(self, item):
        if not self.isFull():
            self.queue.append(item)
        else:
            print("큐가 가득 찼습니다!")

    def dequeue(self):
        if not self.isEmpty():
            return self.queue.pop(0)
        else:
            print("큐가 비어있습니다!")
            return None

    def peek(self):
        if not self.isEmpty():
            return self.queue[0]
        else:
            print("큐가 비어있습니다!")
            return None

    def isEmpty(self):
        return len(self.queue) == 0

    def isFull(self):
        return len(self.queue) == self.size

    def getSize(self):
        return len(self.queue)

# 큐 사용 예시
queue = Queue(3)
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)

print("현재 큐:", queue.queue)
print("큐 크기:", queue.getSize())
print("맨 앞의 요소:", queue.peek())

queue.enqueue(4)  # 큐가 가득 찼으므로 추가되지 않음
print("dequeue 연산 결과:", queue.dequeue())
print("현재 큐:", queue.queue)

큐는 배열을 사용하여 구현할 수 있으나, 데이터를 추가하거나 제거할 때 배열의 크기 조정이 필요할 수 있다.

연결 리스트를 사용하여 큐를 구현하면, 데이터의 추가와 제거가 앞쪽과 뒤쪽을 가리키는 포인터만 조정하면 되기 때문에 유연하게 처리될 수 있어 배열 기반 구현 보다 효율적일 수 있다.

각 연산의 시간 복잡도는 O(1)을 가지며 스택과 마찬가지로 크기에 관계없이 일정한 시간 내에 연산을 수행할 수 있다.