W2D5-2 221125 Stack & Queue 스택과 큐

Jin Bae·2022년 11월 25일
0

스파르타코딩클럽

목록 보기
11/35

Stack 스택

Uses a data structure called Last In First Out (LIFO)

  • push(data): Operation that adds an element to the top index
    - append() for Python works the same way for Python lists
  • pop(): Operation that deletes the top element
  • peek(): Returns the top element
  • isEmpty(): Returns if the stack is empty or not

Using Linked Lists to create functions

Push

For Linked Lists, the top element is at self.head.

def push(self, value):
        # Create a new Node
        newHead = Node(value)

        # Point the new Node to the current head
        newHead.next = self.head
        
        # Change the head to the new Node
        self.head = newHead

Pop

A new head is assigned to the next Node and the head is deleted.

def pop(self):
        # Return none when the Stack is empty
        if self.is_empty():
            return None

        # Save the current head
        deleteNode = self.head

        # Change the head to the next Node
        self.head = deleteNode.next
        
        return deleteNode

Peek

Shows the top data, or the head in this case.

def peek(self):
        if self.is_empty():
            return None
        return self.head.data

is_empty

Returns if the list is empty. The head would be empty in this case.

def is_empty(self):
        return self.head is None

Queue 큐

Uses a data structure called First In First Out (FIFO)

  • enqueue(data): Adds data to the last index
  • dequeue(): Deletes data of the first index
  • peek(): Returns the first element
  • isEmpty(): Determines if the queue is empty or not

To create this with Linked Lists, a head and tail is needed.

Enqueue

Adds new Node to the end (tail).

def enqueue(self, value):
        newNode = Node(value)
        
        # If the Queue is empty:
        if self.is_empty():
            self.head = newNode
            self.tail = newNode
            return

        # Declare the new Node as the new tail
        self.tail.next = newNode
        self.tail = newNode

Dequeue

Deletes first Node (head).

def dequeue(self):
        if self.is_empty():
            return None
        # Deleted head to return
        deleteHead = self.head

        # Change head
        newHead = self.head.next
        self.head = newHead
        return deleteHead.data

Peek

Returns first Node (head).

def peek(self):
        if self.is_empty():
            return None
        return self.head.data

is_empty

Returns if the Queue is empty.

def is_empty(self):
        return self.head is None

0개의 댓글