[Bài đọc] Stack

Stack (ngăn xếp) là một cấu trúc dữ liệu danh sách, trong đó việc thêm và lấy các phần tử được thực hiện theo quy tắc FILO (Fist-In/Last-Out), có nghĩa là phần tử nào được đưa vào đầu tiên thì sẽ được lấy ra sau cùng. Nguyên tắc này cũng được gọi là LIFO (Last-IN/First-Out), có nghĩa là phần tử nào được đưa vào sau cùng thì sẽ được lấy ra trước tiên.

Hãy tưởng tượng cấu trúc stack như một ngăn bàn chật hẹp, trong đó các đồ vật được đưa vào lần lượt, đồ vật nào được đưa vào trước thì nằm ở trong cùng, đồ vật nào được đưa vào sau thì nằm ở bên ngoài. Như vậy, khi lấy các đồ vật ra thì chúng ta phải lấy các đồ vật ở bên ngoài trước, rồi lần lượt như vậy cho đến khi lấy được các đồ vật ở bên trong.

Các thao tác của Stack

Các thao tác thông dụng của Stack bao gồm:

• init – create the stack.
• push – add an item to the top of the stack.
• pop – remove the last item added to the top of the stack.
• top – look at the item on the top of the stack without removing it.
• isEmpty – return whether the stack contains no more items.

Chúng ta cũng có thể đặt ra một giới hạn số lượng phần tử cho Stack, khi có nhiều hơn số lượng phần tử được thêm vào trong Stack thì sẽ tung ra một thông báo rằng đã bị “tràn” so với dung lượng đang có. Đến đây, chúng ta nhớ đến tại sao lại có trang web tên là “Stack Overflow” để dành cho các Lập trình viên hỗ trợ nhau trong trường hợp bị “tràn” bộ nhớ.

Triển khai Stack

Sau đây là một triển khai đơn giản của cấu trúc Stack:

<?php
class ReadingList
{
    protected $stack;
    protected $limit;
    
    public function __construct($limit = 10) {
        // initialize the stack
        $this->stack = array();
        // stack can only contain this many items
        $this->limit = $limit;
    }

    public function push($item) {
        // trap for stack overflow
        if (count($this->stack) < $this->limit) {
            // prepend item to the start of the array
            array_unshift($this->stack, $item);
        } else {
            throw new RunTimeException('Stack is full!'); 
        }
    }

    public function pop() {
        if ($this->isEmpty()) {
            // trap for stack underflow
	      throw new RunTimeException('Stack is empty!');
	  } else {
            // pop item from the start of the array
            return array_shift($this->stack);
        }
    }

    public function top() {
        return current($this->stack);
    }

    public function isEmpty() {
        return empty($this->stack);
    }
}

Trong ví dụ này, chúng ta đã sử dụng array_unshift() và array_shift() chứ không phải là array_push() và array_pop(), nhờ đó mà phần tử đầu tiên của stack luôn luôn ở trên cùng.

Tất nhiên, chúng ta cũng có thể sử dụng array_push() và array_pop() để triển khai stack. Trong trường hợp này, phần tử Nth của stack sẽ trở thành phần tử trên cùng. Nhưng đối với người sử dụng, thì điều đó không quan trọng, vì kết quả thì stack vẫn hoạt động giống như nguyên tắc LIFO mà không quan trọng cách triển khai ở bên trong như thế nào.

Hãy thêm một số phần tử vào trong Stack:

<?php
$myBooks = new ReadingList();

$myBooks->push('A Dream of Spring');
$myBooks->push('The Winds of Winter');
$myBooks->push('A Dance with Dragons');
$myBooks->push('A Feast for Crows');
$myBooks->push('A Storm of Swords'); 
$myBooks->push('A Clash of Kings');
$myBooks->push('A Game of Thrones');

Hãy lấy một số phần tử ra khỏi Stack:

<?php
echo $myBooks->pop(); // outputs 'A Game of Thrones'
echo $myBooks->pop(); // outputs 'A Clash of Kings'
echo $myBooks->pop(); // outputs 'A Storm of Swords'

Hãy hiển thị phần tử trên cùng của Stack:

<?php
echo $myBooks->top(); // outputs 'A Feast for Crows'

Điều gì sẽ xảy ra nếu chúng ta lấy phần tử này ra:

<?php
echo $myBooks->pop(); // outputs 'A Feast for Crows'

Rồi sau đó lại thêm một phần tử mới vào:

<?php
$myBooks->push('The Armageddon Rag');
echo $myBooks->pop(); // outputs 'The Armageddon Rag'

Chúng ta có thể thấy rằng Stack luôn hoạt động theo nguyên tắc Last-In/First-Out. Cho dù chúng ta thêm, bỏ theo bất cứ hình thức nào thì phần tử được thêm vào sau cùng thì cũng sẽ được lấy ra trước tiên.

Nếu chúng ta tiếp tục thêm nhiều phần tử nữa vào trong Stack thì sẽ nhận được một exception thông báo rằng Stack đã bị “tràn”.