Hàng đợi ngăn xếp python

Cấu trúc dữ liệu tổ chức lưu trữ trong máy tính để chúng ta có thể truy cập và thay đổi dữ liệu một cách hiệu quả. Ngăn xếp và Hàng đợi là một số cấu trúc dữ liệu sớm nhất được định nghĩa trong khoa học máy tính

Đơn giản để tìm hiểu và dễ thực hiện, việc sử dụng chúng rất phổ biến và rất có thể bạn sẽ thấy mình kết hợp chúng trong phần mềm của mình cho các tác vụ khác nhau

Thông thường, Ngăn xếp và Hàng đợi được triển khai bằng Mảng hoặc Danh sách được liên kết. Chúng tôi sẽ dựa vào cấu trúc dữ liệu List để chứa cả Ngăn xếp và Hàng đợi

Họ làm việc như thế nào?

Cây rơm

Ngăn xếp, giống như tên gợi ý, tuân theo nguyên tắc Nhập trước xuất trước (LIFO). Như thể xếp chồng các đồng xu này lên nhau, đồng xu cuối cùng chúng ta đặt lên trên cùng là đồng xu đầu tiên được lấy ra khỏi ngăn xếp sau

Do đó, để triển khai ngăn xếp, chúng ta cần hai thao tác đơn giản

• push - thêm một phần tử vào đầu ngăn xếp

• pop - xóa phần tử ở đầu ngăn xếp

Xếp hàng

Hàng đợi, giống như tên cho thấy, tuân theo nguyên tắc Nhập trước xuất trước (FIFO). Như xếp hàng chờ mua vé xem phim, người đầu tiên đứng xếp hàng là người đầu tiên mua vé và thưởng thức bộ phim

Do đó, để thực hiện một hàng đợi, chúng ta cần hai thao tác đơn giản

• enqueue - thêm phần tử vào cuối hàng đợi

• dequeue - xóa phần tử ở đầu hàng đợi

Ngăn xếp và Hàng đợi sử dụng Danh sách

Cấu trúc dữ liệu List tích hợp sẵn của Python đi kèm với các phương thức để mô phỏng cả hoạt động của ngăn xếp và hàng đợi

Hãy xem xét một chồng thư

Chúng ta có thể sử dụng các chức năng tương tự để triển khai Hàng đợi. Hàm pop tùy chọn lấy chỉ mục của mục mà chúng tôi muốn truy xuất làm đối số

Vì vậy, chúng tôi có thể sử dụng pop với chỉ mục đầu tiên của danh sách tôi. e. 0, để có hành vi giống như hàng đợi

Hãy xem hướng dẫn thực hành, thực tế của chúng tôi để học Git, với các phương pháp hay nhất, tiêu chuẩn được ngành chấp nhận và bao gồm bảng gian lận. Dừng các lệnh Git trên Google và thực sự tìm hiểu nó

Hãy xem xét một "hàng đợi" của trái cây

Một lần nữa, ở đây chúng tôi sử dụng các hoạt động append và pop của danh sách để mô phỏng các hoạt động cốt lõi của hàng đợi

Ngăn xếp và hàng đợi với Thư viện Deque

Python có một thư viện push1 (phát âm là 'deck') cung cấp một chuỗi với các phương thức hiệu quả để hoạt động như một ngăn xếp hoặc hàng đợi

push1 là viết tắt của Double Ended Queue - một hàng đợi tổng quát có thể lấy phần tử đầu tiên hoặc cuối cùng được lưu trữ

Nếu bạn muốn tìm hiểu thêm về thư viện push1 và các loại bộ sưu tập khác mà Python cung cấp, bạn có thể đọc bài viết Giới thiệu về Mô-đun bộ sưu tập của Python

Triển khai chặt chẽ hơn trong Python

Nếu mã của bạn cần một ngăn xếp và bạn cung cấp một List, thì không gì có thể ngăn người lập trình gọi push5, push6 hoặc các hàm danh sách khác sẽ ảnh hưởng đến thứ tự ngăn xếp của bạn. Về cơ bản, điều này làm hỏng điểm xác định ngăn xếp, vì nó không còn hoạt động như bình thường

Đôi khi chúng tôi muốn đảm bảo rằng chỉ những hoạt động hợp lệ mới có thể được thực hiện trên dữ liệu của chúng tôi

Chúng ta có thể tạo các lớp chỉ hiển thị các phương thức cần thiết cho từng cấu trúc dữ liệu

Để làm như vậy, hãy tạo một tệp mới có tên là push7 và xác định hai lớp

Các lập trình viên sử dụng push8 và push9 của chúng tôi hiện được khuyến khích sử dụng các phương pháp được cung cấp để thao tác dữ liệu thay thế

ví dụ

Hãy tưởng tượng bạn là một nhà phát triển đang làm việc trên một trình xử lý văn bản hoàn toàn mới. Bạn được giao nhiệm vụ tạo một tính năng hoàn tác - cho phép người dùng quay lại hành động của họ cho đến khi bắt đầu phiên

Một ngăn xếp là một sự phù hợp lý tưởng cho kịch bản này. Chúng tôi có thể ghi lại mọi hành động mà người dùng thực hiện bằng cách đẩy nó vào ngăn xếp. Khi người dùng muốn hoàn tác một hành động, họ sẽ bật nó ra khỏi ngăn xếp. Chúng ta có thể nhanh chóng mô phỏng tính năng như thế này

Hàng đợi cũng được sử dụng rộng rãi trong lập trình. Hãy nghĩ về các trò chơi như Street Fighter hoặc Super Smash Brothers. Người chơi trong các trò chơi đó có thể thực hiện các động tác đặc biệt bằng cách nhấn tổ hợp các nút. Các tổ hợp nút này có thể được lưu trữ trong hàng đợi

Bây giờ, hãy tưởng tượng rằng bạn là nhà phát triển đang làm việc trên một trò chơi chiến đấu mới. Trong trò chơi của bạn, mỗi lần nhấn một nút, một sự kiện đầu vào sẽ được kích hoạt. Một người thử nghiệm nhận thấy rằng nếu các nút được nhấn quá nhanh, trò chơi chỉ xử lý nút đầu tiên và các bước di chuyển đặc biệt sẽ không hoạt động

Bạn có thể khắc phục điều đó bằng một hàng đợi. Chúng ta có thể liệt kê tất cả các sự kiện đầu vào khi chúng đến. Bằng cách này, sẽ không có vấn đề gì nếu các sự kiện đầu vào diễn ra cách nhau ít thời gian, tất cả chúng sẽ được lưu trữ và sẵn sàng để xử lý. Khi chúng tôi đang xử lý các nước đi, chúng tôi có thể loại bỏ chúng. Một động thái đặc biệt có thể được thực hiện như thế này

Phần kết luận

Ngăn xếp và hàng đợi là những cấu trúc dữ liệu đơn giản cho phép chúng ta lưu trữ và truy xuất dữ liệu một cách tuần tự. Trong một ngăn xếp, mục cuối cùng chúng tôi nhập vào là mục đầu tiên xuất hiện. Trong một hàng đợi, mục đầu tiên chúng tôi nhập là mục đầu tiên xuất hiện

Chúng ta có thể thêm các mục vào ngăn xếp bằng cách sử dụng thao tác push và truy xuất các mục bằng cách sử dụng thao tác pop. Với hàng đợi, chúng tôi thêm các mục bằng thao tác enqueue và truy xuất các mục bằng thao tác dequeue

Trong Python, chúng ta có thể triển khai ngăn xếp và hàng đợi chỉ bằng cách sử dụng cấu trúc dữ liệu List tích hợp. Python cũng có thư viện push1 có thể cung cấp hiệu quả các thao tác ngăn xếp và xếp hàng trong một đối tượng. Cuối cùng, chúng tôi đã tạo các lớp ngăn xếp và hàng đợi để kiểm soát dữ liệu chặt chẽ hơn

Có nhiều trường hợp sử dụng ngăn xếp và hàng đợi trong thế giới thực, việc hiểu chúng cho phép chúng ta giải quyết nhiều vấn đề về lưu trữ dữ liệu một cách dễ dàng và hiệu quả