Bài 6: NGĂN XẾP VÀ HÀNG ĐỢI

 1. Ngăn xếp.

Định nghĩa

Ngăn xếp: Là một loại dữ liệu trừu tượng và các thao tác có thể dùng:

• Push(data): Thêm data vào ngăn xếp
• Top(): Tìm key mới nhất 
• Pop(): Trả về và xoá key mới nhất
• Empty(): Kiểm tra ngăn xếp có rỗng không

Ví dụ: Cân bằng ngoặc

Đầu vào: Một chuỗi các ký tự '(', ')', '[', ']'

Đầu ra: Trả về việc dấu ngoặc tròn và dấu ngoặc vuông của chuỗi có cân bằng không.

Pseudocode

$IsBalanced(str)$
Stack stack
for char in str:
    if char in [ '(', '[' ]:
        stack.push(char)
    else: 
        if stack.empty(): return False
        top = stack.pop()
        if top = '(' and char != ')' or top = '[' and char != ']':
            return False
return stack.empty()

Code

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
class Stack:
    def __init__(self):
        self.head = None
    def print_stack(self):
        temp = self.head
        while temp is not None:
            print(temp.data)
            temp = temp.next
    def push(self, data_new):
        node_new = Node(data_new)
        node_new.next = self.head
        self.head = node_new
    def pop(self):
        if self.head is None:
            return None
        temp = self.head.data
        self.head = self.head.next
        return temp
    def top(self):
        return self.head.data
    def empty(self):
        return self.head is None
class IsBalanced:
    def __init__(self, str):
        self.str = str
    def isbalanced(self):
        s = Stack()
        for char in self.str:
            if char in ['(', '[']:
                s.push(char)
            else:
                if s.empty(): return False
                top = s.pop()
                if top == '(' and char != ')' or top == '[' and char != ']':
                    return False
        return s.empty()
string = ['(', ')', '[', ']']
I = IsBalanced(string)
print(I.isbalanced())

2. Hàng đợi

Định nghĩa

Ngăn xếp: Là một loại dữ liệu trừu tượng và các thao tác có thể dùng:

• Enqueue(key) : Thêm key vào hàng đợi
• Dequeue : Xoá key và trả về giá trị của nó
• Empty() : Kiểm tra hàng đợi có rỗng không