스택과 큐 || 파이썬 || 데이터 구조 및 알고리즘

스택

Stack - 후입선출(LIFO) 순서로 검색을 지원하는 저장 컨테이너입니다. 스택은 일괄 작업을 처리할 때와 같이 검색 순서가 전혀 중요하지 않을 때 사용하기에 적합한 컨테이너일 것입니다.

예를 들어 구내식당에서 사용되는 접시 더미를 생각해 보세요. 접시 더미에서 접시를 제거하는 순서는 추가된 순서와 반대입니다. 상단 접시에만 접근할 수 있기 때문입니다. .

스택에 대한 INSERT 작업을 PUSH라고 하며, 요소 인수를 사용하지 않는 DELETE 작업을 POP라고 합니다.

푸시(x,s): 스택 s의 맨 위에 항목 x를 삽입합니다.

Pop(s) : 스택 s의 최상위 항목을 반환(및 제거)합니다.

내 냉장고에 넣은 음식은 유통기한에 대한 인센티브에도 불구하고 대개 같은 방식으로 빠져나갑니다. 알고리즘적으로 LIFO는 재귀적인 알고리즘을 실행하는 과정에서 발생하는 경향이 있습니다.

스택의 응용 -

1. 함수 호출: 함수 실행 및 재귀를 관리하는 데 사용됩니다.
2. 실행 취소 작업: "실행 취소/다시 실행"에 대한 편집기의 변경 사항을 추적합니다.
3. 브라우저 기록: 역추적을 위해 방문한 페이지를 저장합니다.
4. 표현식 분석: 수학 표현식을 평가하고 변환합니다.
5. 구문 유효성 검사: 코드에서 괄호나 태그를 일치시킵니다.
6. 메모리 관리: 프로그램 실행 중 호출 스택을 관리합니다.
7. DFS: 그래프 알고리즘에 깊이 우선 검색을 구현합니다.

배열을 이용한 스택 구현 -

• push() - 스택에 요소 삽입
• pop() - 스택에서 요소 제거
• top() - 스택의 최상위 요소를 반환합니다.
• isEmpty() - 스택이 비어 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다.

class Stack:
    def __init__(self):
        #Initializes an empty stack 
        self.stack = []

    def isEmpty(self) -> bool:
        #Returns True if the stack is empty, False otherwise.

        return len(self.stack) == 0

    def push(self, item) -> None:
        #Pushes an item onto the stack.
        self.stack.append(item)

    def pop(self):
        #Removes and returns the top item from the stack.
        if self.isEmpty():
            return None
        return self.stack.pop()

    def peek(self):
        #Returns the top item from the stack without removing it.
        if self.isEmpty():
            return None
        return self.stack[-1]

대기줄

Queue - FIFO(선입선출) 순서로 검색을 지원하는 저장 컨테이너입니다. 대기열 ENQUEUE에서 INSERT 작업을 호출하고 DELETE 작업 DEQUEUE를 호출합니다. 스택 작업 POP와 마찬가지로 DEQUEUE는 요소 인수를 사용하지 않습니다. 스택과 큐는 DELETE 작업에 의해 세트에서 제거된 요소가 미리 정의되어 있는 동적 세트입니다.

Enqueue(x,q): 큐 q 뒤에 항목 x를 삽입합니다.

Dequeue(q): 대기열 q에서 맨 앞 항목을 반환(및 제거)합니다.

대기열에는 머리와 꼬리가 있습니다.

• 새로 도착한 고객이 줄 끝에 자리를 잡는 것처럼 요소가 대기열에 추가되면 대기열의 끝 부분에 자리를 잡게 됩니다.

• 대기열에서 제외된 요소는 가장 오래 기다린 줄 맨 앞에 있는 고객과 마찬가지로 항상 대기열의 맨 위에 있는 요소입니다.

큐의 활용 -

1. 작업 스케줄링: CPU 프로세스와 작업을 순서대로 관리합니다.
2. BFS: 그래프에서 너비 우선 검색을 구현합니다.
3. 인쇄 대기열: 인쇄 작업을 순차적으로 처리합니다.
4. 네트워크 라우팅: 전송을 위해 데이터 패킷을 버퍼링합니다.
5. 콜센터: 대기순으로 고객의 전화를 관리합니다.
6. 스트리밍: 실시간으로 비디오 또는 오디오 스트림을 버퍼링합니다.
7. 입력 이벤트: GUI 시스템에서 키보드 및 마우스 입력을 처리합니다.

배열을 이용한 대기열 구현-

• enqueue() – 대기열에 요소를 삽입합니다.
• dequeue() – 대기열에서 요소를 제거합니다.
• peek() 또는 front()- 대기열의 프런트 노드에서 사용 가능한 데이터 요소를 삭제하지 않고 획득합니다.
• isEmpty() – 대기열이 비어 있는지 확인합니다.

class Stack:
    def __init__(self):
        #Initializes an empty stack 
        self.stack = []

    def isEmpty(self) -> bool:
        #Returns True if the stack is empty, False otherwise.

        return len(self.stack) == 0

    def push(self, item) -> None:
        #Pushes an item onto the stack.
        self.stack.append(item)

    def pop(self):
        #Removes and returns the top item from the stack.
        if self.isEmpty():
            return None
        return self.stack.pop()

    def peek(self):
        #Returns the top item from the stack without removing it.
        if self.isEmpty():
            return None
        return self.stack[-1]

스택을 활용한 대기열 구현 -

• push(x) - 스택1의 모든 요소를 ​​스택 2로 이동하여 순서를 바꾼 다음 다시 스택2의 모든 요소를 ​​스택 1로 다시 이동합니다.
• pop() - 대기열 맨 앞의 요소를 제거하고 반환합니다
• peek() - 대기열 맨 앞에 있는 요소를 반환합니다
• empty() - 대기열이 비어 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다.

class MyQueue:
    def __init__(self):
        # Store elements
        self.queue = []
        # A pointer to indicate the start position
        self.p_start = 0

    def enQueue(self, x):
        #Insert an element into the queue. 
        self.queue.append(x)
        return True # Return True if the operation is successful

    def deQueue(self):
        #Delete an element from the queue. 
        if self.isEmpty():
            return False
        self.p_start += 1
        return True #Return True if the operation is successful

    def Front(self):
        #Get the front item from the queue.
        if not self.isEmpty():
            return self.queue[self.p_start]
        return None  # Return None if the queue is empty

    def isEmpty(self):
        #Checks whether the queue is empty or not
        return self.p_start >= len(self.queue)

큐를 이용한 스택 구현 -

• push(x) - 두 번째 대기열에 새 요소를 추가한 다음 모든 요소를 ​​대기열 1에서 대기열 2로 이동하여 스택 순서(LIFO)를 유지하고 대기열을 교환합니다.
• pop() - 스택 맨 위에 있는 요소를 제거하고 반환합니다
• peek 또는 top() - 대기열 맨 앞에 있는 요소를 반환합니다
• empty() - 대기열이 비어 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다.

class MyQueue:

    def __init__(self):
        self.stack_1 = []  # Main stack for enqueue operations
        self.stack_2 = []  # Temporary stack for dequeue operations
        self.front = None

    # Pushes element x to the back of the queue.
    def push(self, x):

        # Move all elements from stack1 to stack 2 to reverse their order
        while self.stack_1:
            self.stack_2.append(self.stack_1.pop())
        self.stack_2.append(x)

        # Move all elements back from stack2 to stack 1 as a queue
        while self.stack_2:
            self.stack_1.append(self.stack_2.pop())

    # Removes the element from the front of the queue and returns it
    def pop(self):
        return self.stack_1.pop()

    # Returns the element at the front of the queue
    def peek(self):
        return self.stack_1[-1]

    # Returns true if the queue is empty, false otherwise
    def empty(self):
        return not self.stack_1

위 내용은 스택과 큐 || 파이썬 || 데이터 구조 및 알고리즘의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!