Computer >> Máy Tính >  >> Lập trình >> Python

Sử dụng Danh sách dưới dạng Ngăn xếp và Hàng đợi trong Python

Trong bài viết này, chúng ta sẽ tìm hiểu về cấu trúc Stack &Queue trong Python 3.x. Hoặc sớm hơn. Ở đây chúng ta sẽ thảo luận về cách làm việc và sửa đổi trong các cấu trúc dữ liệu này -

Điều này bao gồm -

  1. Thao tác chèn (Đẩy, Yêu cầu)
  2. Thao tác xóa (Pop, Dequeue)
  3. Hoạt động Hiển thị / Truyền ngang

Điều kiện tiên quyết :Danh sách &Hoạt động Danh sách

Cấu trúc dữ liệu có liên quan :Thao tác danh sách

Hình ảnh liên quan

Sử dụng Danh sách dưới dạng Ngăn xếp và Hàng đợi trong Python

Ngăn xếp

Trong ngăn xếp, các đối tượng được lưu trữ chồng lên nhau, và các đối tượng này được gỡ bỏ theo thứ tự ngược lại của lần đến, tức là tuân theo khái niệm LIFO. LIFO có nghĩa là Kiểu cuối cùng trong Đầu ra sắp xếp được tuân theo trong cấu trúc dữ liệu Ngăn xếp.

Các hoạt động trên một ngăn xếp -

  • Bổ sung / Thêm phần tử:Điều này làm tăng kích thước ngăn xếp bằng số lượng mục được thêm vào và Việc bổ sung diễn ra ở phần trên, tức là ở phần trên cùng của ngăn xếp.
  • Xóa / Loại bỏ Phần tử - Điều này liên quan đến hai điều kiện - Nếu Ngăn xếp trống, không có phần tử nào có sẵn để xóa, tức là Dòng dưới xảy ra trong Ngăn xếp hoặc Nếu Ngăn xếp có một số phần tử nhất định hiện diện trong đó thì phần tử hiện diện ở trên cùng sẽ bị xóa . Điều này làm giảm kích thước của ngăn xếp theo số lượng phần tử bị xóa.
  • Duyệt / Hiển thị - Điều này liên quan đến việc truy cập từng phần tử của ngăn xếp và hiển thị trên màn hình.

Chúng tôi cũng có thể chèn một chức năng bổ sung của peek, tức là truy xuất giá trị ở đầu Ngăn xếp.

Đặc điểm của ngăn xếp

  • Thứ tự chèn được giữ nguyên.
  • Cho phép trùng lặp trong Stack.
  • Bộ nhớ kiểu dữ liệu tương tự.
  • Rất hữu ích trong Hoạt động phân tích cú pháp.

Mã mẫu 

def isEmpty(stk): # checks whether the stack is empty or not
   if stk==[]:
      return True
   else:
      return False

def Push(stk,item): # Allow additions to the stack
   stk.append(item)
   top=len(stk)-1

def Pop(stk):
   if isEmpty(stk): # verifies whether the stack is empty or not
      print("Underflow")
   else: # Allow deletions from the stack
      item=stk.pop()
      if len(stk)==0:
         top=None
      else:
         top=len(stk)
         print("Popped item is "+str(item))

def Display(stk):
   if isEmpty(stk):
      print("Stack is empty")
   else:
      top=len(stk)-1
      print("Elements in the stack are: ")
      for i in range(top,-1,-1):
         print (str(stk[i]))

# executable code
if __name__ == "__main__":
   stk=[]
   top=None
   Push(stk,1)
   Push(stk,2)
   Push(stk,3)
   Push(stk,4)
   Pop(stk)
   Display(stk)

Đoạn mã trên thực hiện chức năng Ngăn xếp trong Python 3.x. hoặc sớm hơn. Chúng ta có thể tạo chương trình hướng menu bằng cách cung cấp các lựa chọn cho người dùng bằng cách sử dụng nhiều câu lệnh if-else. Khái niệm về việc đóng khung Stack vẫn giống nhau trong cả hai trường hợp.

Màn hình hiển thị bên dưới mô tả kết quả được tạo ra bởi chương trình trên. Chúng ta cũng có thể sử dụng hàm input () cho hệ thống đầu vào dựa trên người dùng (Ở đây tôi đã triển khai các đầu vào tĩnh)

Đầu ra 

Popped item is 4
Elements in the stack are:
3
2
1

Hàng đợi

Trong ngăn xếp, các đối tượng được lưu trữ lần lượt và các đối tượng này được loại bỏ theo thứ tự đến tức là tuân theo khái niệm FIFO. FIFO có nghĩa là Đầu tiên trong Đầu tiên, sắp xếp loại đầu tiên được tuân theo trong cấu trúc dữ liệu hàng đợi.

Hoạt động trên hàng đợi

  • Bổ sung / Thêm phần tử - Điều này làm tăng kích thước hàng đợi theo số lượng mục được thêm vào và Việc bổ sung diễn ra ở cuối phía sau, tức là ở phía sau hàng đợi.

  • Xóa / Xóa phần tử - Điều này liên quan đến hai điều kiện - Nếu Hàng đợi trống thì không có phần tử nào có sẵn để xóa, tức là Dòng dưới xảy ra trong Hàng đợi hoặc Nếu Hàng đợi có một số phần tử nhất định hiện diện trong đó thì phần tử hiện diện ở phía trước sẽ bị xóa. Điều này làm giảm kích thước của ngăn xếp theo số lượng phần tử bị loại bỏ.

  • Duyệt / Hiển thị - Điều này liên quan đến việc truy cập từng phần tử của ngăn xếp và hiển thị trên màn hình.

Chúng tôi cũng có thể chèn một chức năng bổ sung của peek, tức là lấy giá trị ở phía sau / cuối Hàng đợi.

Đặc điểm của Hàng đợi

  • Thứ tự chèn được giữ nguyên.
  • Cho phép trùng lặp trong Hàng đợi.
  • Bộ nhớ kiểu dữ liệu tương tự.
  • Rất hữu ích trong việc phân tích cú pháp các hoạt động tác vụ của CPU.

Mã mẫu 

#Adding elements to queue at the rear end
def enqueue(data):
   queue.insert(0,data)

#Removing the front element from the queue
def dequeue():
   if len(queue)>0:
      return queue.pop()
   return ("Queue Empty!")

#To display the elements of the queue
def display():
   print("Elements on queue are:");
   for i in range(len(queue)):
      print(queue[i])

# executable code
if __name__=="__main__":
   queue=[]
   enqueue(5)
   enqueue(6)
   enqueue(9)
   enqueue(5)
   enqueue(3)
   print("Popped Element is: "+str(dequeue()))
   display()

Đoạn mã trên thực hiện chức năng Hàng đợi trong Python 3.x. hoặc sớm hơn. Chúng ta có thể tạo chương trình hướng menu bằng cách cung cấp các lựa chọn cho người dùng bằng cách sử dụng nhiều câu lệnh if-else. Khái niệm về định khung Hàng đợi vẫn giống nhau trong cả hai trường hợp.

Màn hình hiển thị bên dưới mô tả kết quả được tạo ra bởi chương trình trên. Chúng ta cũng có thể sử dụng hàm input () cho hệ thống đầu vào dựa trên người dùng (Ở đây tôi đã triển khai các đầu vào tĩnh)

Đầu ra 

Popped item is: 5
Elements on queue are:
3
5
9
6

Kết luận

Trong bài viết này, chúng ta đã học cách triển khai cấu trúc dữ liệu Stack &Queue trong Python 3.x. Hoặc sớm hơn. Bạn có thể triển khai cùng một thuật toán để triển khai chương trình phát hiện ngăn xếp / hàng đợi bằng bất kỳ ngôn ngữ lập trình nào khác.