← 筆記
LeetCode

《圖說演算法-使用C#》要點摘錄 – 「棧與隊列」

書名：《圖說演算法-使用C#》

作者：吳燦銘、胡昭民

所讀版本：博碩文化

數組實作Stack

  •   public class ArrayStack
  {
  int[] stack;
  int top; //頂端索引
      public ArrayStack(int size)
      {
          stack = new int[size];
          top = -1; //實例化後默認頂端索引為-1（無元素）
      }
  
      public bool Push(int data)
      {
          if (top >= stack.Length) { return false; } //判斷Stack是否已經滿了
          stack[++top] = data;//索引+1，把數據入堆
          return true;
      }
  
      public bool IsEmpty()
      {
      	return top == -1;
      }
  
      public int Pop()
      {
          if (IsEmpty()) { return -1; } //判斷Stack是否為空
          return stack[top--]; //把數據出堆，索引-1
      }
  }

鏈表實作Stack

  •   public class LinkedListStack
  {
      public Node front; //指向堆的底端
      public Node rear; //指向堆的頂端
  
      public bool IsEmpty()
      {
          return front == null;
      }
  
      public void OutputStack()
      {
          Node curr = front;
          while(curr != null)
          {
              Console.Write(curr.val + " ");
              curr = curr.next;
          }
          Console.WriteLine();
      }
  
      public void Push(int data)
      {
          Node newNode = new Node(data);
          if (IsEmpty())
          {
              front = newNode;
              rear = newNode;
          }
          else
          {
              rear.next = newNode;
              rear = newNode;
          }
      }
  
      public void Pop()
      {
          Node target;
          if (IsEmpty()) { return; }
          target = front;
          if(target == rear) //只有一個元素
          {
              front = null;
              rear = null;
          }
          else
          {
              while(target.next != rear)
              {
                  target = target.next;
              }
              target.next = rear.next;
              rear = target;
          }
      }
  }

河內塔算法

  • 假設有A, B, C三個木樁和n個大小不一的套環，由小到大的編號為1~n，編號越大，直徑越大。開始的時候，n個套環套在A木樁上。
    • 直徑較小的套環永遠置於直徑較大的套環上。
    • 套環可任意地由任何一個木樁移到其他的木樁上。
    • 每一次僅能移動一個套環，而且只能從最上面的套環開始移動。
  • 當有n個盤子時，河內塔的移動步驟
    • 將n - 1個盤子從木樁1移動到木樁2
    • 將n個最大盤子，從木樁1移動到木樁3
    • 將n-1 個盤子，從木樁2移動到木樁3
public static void Hanoi(int n, int p1, int p2, int p3)
{
    if(n == 1)
    {
    	Console.WriteLine($"Plate Moved From {p1} To {p3}");
    }
    else
    {
        Hanoi(n - 1, p1, p3, p2);
        Console.WriteLine($"Plate Moved From {p1} To {p3}");
        Hanoi(n - 1, p2, p1, p3);
    }
}

八皇后算法

  • 在一個8*8棋盤內，置入一個皇后，確保這個位置不會被先前放置的皇后吃掉（直、橫、斜沒有其他皇后），就將這個皇后存入Stack。
  • 當放置新皇后的該行的8個位置都沒有辦法放置新皇后，就從Stack取出上一個皇后的位置，並在那行找一個新的位置放置皇后，然後再將該位置存入Stack中（BackTracking）。
  •   static int solutionCnt = 0;
  
  public static int TotalQueens()
  {
      int[,] chessBoard = new int[8, 8];
      BackTrack(chessBoard, 0);
      return solutionCnt;
  }
  
  static void BackTrack(int[,] chessBoard, int currRow)
  {
      //Loop Column of chessBoard
      for (int col = 0; col < 8; col++)
      {
          if (chessBoard[currRow, col] == 0) //Placable
          {
              chessBoard[currRow, col] = 1; //Place Queen
              SetAttackRange(chessBoard, currRow, col, 1); //Set Attack Range
  
              if(currRow + 1 == 8)
              {
                  //Current Combination Confirmed
                  solutionCnt++;
              }
              else
              {
                  //Move To Next Row
                  BackTrack(chessBoard, currRow + 1);
              }
  
              //Remove Queen
              chessBoard[currRow, col] = 0;
              SetAttackRange(chessBoard, currRow, col, -1);
  
          }
      }
  }
  
  //標記攻撃範圍
  static void SetAttackRange(int[,] chessBoard, int row, int col, int change)
  {
      //縱橫
      for (int i = 0; i < 8; i++)
      {
          if (i != col) { chessBoard[row, i] += change; }
          if (i != row) { chessBoard[i, col] += change; }
      }
  
      //斜
      //Top Left
      int y = row - 1;
      int x = col - 1;
      while (y >= 0 && x >= 0) { chessBoard[y--, x--] += change; }
      //Top Right
      y = row - 1;
      x = col + 1;
      while (y >= 0 && x < 8) { chessBoard[y--, x++] += change; }
      //Bottom Left
      y = row + 1;
      x = col - 1;
      while(y < 8 && x >= 0) { chessBoard[y++, x--] += change;}
      //Bottom Right
      y = row + 1;
      x = col + 1;
      while(y < 8 && x < 8) { chessBoard[y++, x++] += change; }
  
  }

數組實作Queue

  •   public class ArrayQueue
  {
  int[] queue;
  int front;
  int rear;
      public ArrayQueue(int size)
      {
          queue = new int[size];
          front = -1;
          rear = -1;
      }
  
      public bool Enqueue(int data)
      {
          if(rear + 1 == queue.Length) { return false; }
  
          queue[++rear] = data;
          return true;
  	}
      
      public int Dequeue()
      {            
          if(rear > front)
          {
              front++;
              int output = queue[front];
              queue[front] = 0;
              return output;
          }
          return -1;
      }        
  }

鏈表實作Queue

  •   public class LinkedListQueue
  {
      public Node front;
      public Node rear;
  
      public LinkedListQueue()
      {
          front = null;
          rear = null;
      }
  
      public bool Enqueue(int data)
      {
          Node newNode = new Node(data);
  
          if(front == null)
          {
              front = newNode;
          }
          else
          {
              rear.next = newNode;
          }
          rear = newNode;
          return true;
      }
  
      public int Dequeue()
      {
          if (front == null) { return -1; }
          int value = front.val;
          if (front == rear) { rear = null; }
          front = front.next;
          return value;
      }
  }

雙向Queue

  • 前後兩端都可以輸入/取出

  • 加入及取出時，指標往Queue的中央移動

  •   public class DoublyLinkedListQueue
  {
  public Node front;
  public Node rear;
      public DoublyLinkedListQueue()
      {
          front = null;
          rear = null;
      }
      
      //Only Insert Front Head
      public bool Enqueue(int data)
      {
          Node newNode = new Node(data);
  
          if(rear == null)
          {
          	front = newNode;
          }
          else
          {
          	rear.next = newNode;
          }
          rear = newNode;
          return true;
      }
  
      //Dequeue From Both Sides
      public int Dequeue(bool isFront)
      {
          int value;
          Node tmp;
          Node start;
  
          if(front != null && isFront)
          {
              value = front.val;
              front = front.next;
          	return value;
          }
          else if(rear != null && !isFront)
          {
              start = front; //save ref of front;
              value = rear.val;
  
              tmp = front;
              //track to the node before rear node
              while(front.next != rear && front.next != null)
              {
                  front = front.next;
                  tmp = front;
              }                
              front = start;
              //set new rear
              rear = tmp;
  
              //Dequeue Last Node
              if(front.next == null || rear.next == null)
              {
                  front = null;
                  rear = null;                    
              }
              return value;
          }
          else
          {
              return -1;
          }
      }
  }

優先Queue

  • HPOF（Highest Priority Out First）rather than FIFO
  • 為每一個元素賦予優先權，加入元素時任意加入，最高優先權者最先輸出