Programming

Stacks And Queues

堆疊 (Stack)

實作 LIFO (last-in first-out) 順序，
如同一疊鬆餅，最後疊上去的鬆餅會最先被吃掉。

It uses the following operations:

  • pop(): Remove the top item from the stack.
  • push(item): Add an item to the top of the stack.
  • peek(): Return the top of the stack.
  • isEmpty(): Return true if and only if the stack is empty.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
<?php

class Stack
{
  protected ?StackNode $top;

  public function pop()
  {
      if (is_null($this->top)) {
          throw new Exception('Empty Stack');
      }

      $item = $this->top->data;
      $this->top = $this->top->next;

      return $item;
  }

  public function push($item)
  {
      $stackNode = new StackNode($item);
      $stackNode->next = $this->top;

      $this->top = $stackNode;
  }

  public function peek()
  {
      if (is_null($this->top)) {
          throw new Exception('Empty Stack');
      }

      return $this->top->data;
  }

  public function isEmpty()
  {
    return is_null($this->top);
  }

}

class StackNode
{
  public mixed $data;
  public ?StackNode $next;

  public function __construct($data)
  {
      $this->data = $data;
      $this->next = null;
  }
}

佇列 (Queue)

實作 FIFO (first-in first-out) 順序，
如同售票亭前排隊，最先排隊的人最早拿到票。

It uses the following operations:

  • add(item): Add an item to the end of the queue.
  • remove(): Remove the first item of the queue.
  • peek(): Return the first of the queue.
  • isEmpty(): Return true if and only if the queue is empty.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
<?php

class Queue
{
  protected ?QueueNode $first;
  protected ?QueueNode $last;

  public function add($item)
  {
      $queueNode = new QueueNode($item);

      if (!is_null($this->last)) {
          $this->last->next = $queueNode;
      }

      $this->last = $queueNode;

      if (is_null($this->first)) {
          $this->first = $queueNode;
      }
  }

  public function remove()
  {
      if (is_null($this->first)) {
          throw new Exception('No Such Element');
      }

      $item = $this->first->data;

      $this->first = $this->first->next;

      if (is_null($this->first)) {
          $this->last = null;
      }

      return $item;

  }

  public function peek()
  {
      if (is_null($this->first)) {
          throw new Exception('No Such Element');
      }

      return $this->first->data;
  }

  public function isEmpty()
  {
      return is_null($this->first);
  }
}

class QueueNode
{
  public mixed $data;
  public ?QueueNode $next;

  public function __construct($data)
  {
      $this->data = $data;
      $this->next = null;
  }
}

ʕ •ᴥ•ʔ：程式碼可參考：CtCI-6th-php。

Share