Java程式插入元素到棧底

---

棧是一種遵循後進先出（LIFO）原則的資料結構。換句話說，我們新增到棧中的最後一個元素是第一個被移除的元素。當我們向棧中新增（或推送）元素時，它們會被放置在頂部；即所有先前新增的元素之上。

在某些情況下，我們可能需要在棧底新增元素。有多種方法可以在棧底新增元素。它們是：

• 使用輔助棧
• 使用遞迴
• 使用臨時變數
• 使用佇列

使用輔助棧

我們可以使用輔助棧（一個輔助棧，我們將使用它來執行操作）在 Java 中將元素插入到棧底。在這裡，我們將使用兩個棧（主棧和輔助棧）將元素插入到主棧的底部。

主棧將包含原始元素，而輔助棧將幫助我們重新排列元素。這種方法易於理解。

步驟

以下是使用輔助棧將元素插入到棧底的步驟

• 初始化兩個棧：建立一個主棧，向其中推送一些元素，然後建立一個輔助棧。
• 彈出所有元素：然後從主棧中移除所有元素並將其推入第二個輔助棧。這將有助於我們反轉元素的順序。
• 推送新元素：一旦主棧為空，我們需要將新元素推入主棧，或者如果需要，也可以將元素推入輔助棧的頂部。
• 恢復原始順序：從輔助棧中彈出所有元素並將其推回主棧。這將恢復元素的原始順序。

示例

以下是如何使用輔助棧將元素新增到底部的示例：

import java.util.Stack;
public class InsertAtBottomUsingTwoStacks {    
   public static void insertElementAtBottom(Stack<Integer> mainStack, int x) {
      // Create an extra auxiliary stack
      Stack<Integer> St2 = new Stack<>();
      
      /* Step 1: Pop all elements from the main stack 
      and push them into the auxiliary stack */
      while (!mainStack.isEmpty()) {
         St2.push(mainStack.pop());
      }

      // Step 2: Push the new element into the main stack
      mainStack.push(x);

      /* Step 3: Restore the original order by popping each 
      element from the auxiliary stack and push back to main stack */
      while (!St2.isEmpty()) {
         mainStack.push(St2.pop());
      }
   }
   public static void main(String[] args) {
      Stack<Integer> stack1 = new Stack<>();
      stack1.push(1);
      stack1.push(2);
      stack1.push(3);
      stack1.push(4);

      System.out.println("Original Stack: " + stack1);
      insertElementAtBottom(stack1, 0);
      System.out.println("Stack after inserting 0 at the bottom: " + stack1);
   }
}

在上面的程式中，我們首先將元素 1、2、3 和 4 推入棧中。然後，我們將這些元素轉移到另一個棧中。之後，我們將目標元素插入到主棧中。最後，我們從輔助棧中檢索所有元素。

使用遞迴

遞迴是另一種將元素插入到棧底的方法。在這種方法中，我們將使用遞迴函式從我們的棧中彈出所有元素，直到它變為空，一旦它變為空，我們將把新元素插入到棧中，然後將元素推回棧中。

步驟

以下是使用遞迴將元素插入到棧底的步驟

• 基本情況：檢查棧是否為空。如果為空，我們將把新元素推入棧中。
• 遞迴情況：如果棧不為空，我們將彈出頂部元素並遞迴呼叫函式。
• 恢復元素：在我們完成插入新元素後，我們需要將之前彈出的元素推回棧中。

示例

import java.util.Stack;
public class InsertAtBottomUsingRecursion {
   public static void insertAtElementBottom(Stack<Integer> st, int x) {
      // Base case: If the stack is empty, push the new element
      if (st.isEmpty()) {
         st.push(x);
         return;
      }
      // Recursive case: Pop the top element
      int top = st.pop();
      
      // Call the function recursively
      insertAtElementBottom(st, x);
      
      // Restore the top element into the stack
      st.push(top);
   }
   
   public static void main(String[] args) {
      Stack<Integer> st = new Stack<>();
      st.push(1);
      st.push(2);
      st.push(3);
      st.push(4);
   
      System.out.println("Original Stack: " + st);
      insertAtElementBottom(st, 0);
      System.out.println("Stack after inserting 0 at the bottom: " + st);
   }
}

在上面的程式中，我們定義了一個遞迴函式，該函式將一個新元素插入到棧的底部，然後我們繼續從棧中彈出元素，直到棧變為空，然後我們插入新元素，之後我們將之前的元素恢復到棧中。

使用臨時變數

我們還可以使用臨時變數來完成給定的任務。我們使用此變數來儲存元素，同時我們操作棧。此方法很簡單，我們可以使用簡單的迴圈來實現。

步驟

以下是使用臨時變數將元素插入到棧底的步驟

• 初始化一個臨時變數：建立一個變數來臨時儲存元素，因為您遍歷棧。
• 轉移元素：然後使用迴圈從棧中彈出元素並將這些元素儲存在臨時變數中。
• 插入新元素：一旦我們的棧為空，那麼我們需要將新元素推入棧中。
• 恢復元素：插入元素後，將臨時變數中的元素推回棧中。

示例

import java.util.Stack;
public class InsertAtBottomUsingTempVar {
public static void insertAtElementBottom(Stack<Integer> st, int x) {
   // Temporary variable to hold elements
   int[] temp = new int[st.size()];
   int index = 0;

   // Transfer elements to temporary variable
   while (!st.isEmpty()) {
      temp[index++] = st.pop();
   }

   // Push the new element into the stack
   st.push(x);

   // Restore elements from temporary variable
   for (int i = 0; i < index; i++) {
      st.push(temp[i]);
   }
}
public static void main(String[] args) {
   Stack<Integer> st = new Stack<>();
   st.push(1);
   st.push(2);
   st.push(3);
   st.push(4);

   System.out.println("Original Stack: " + st);
   insertAtElementBottom(st, 0);
   System.out.println("Stack after inserting 0 at the bottom: " + st);
}
}

在此程式中，我們使用了一個臨時陣列來儲存元素，同時操作棧。然後我們將新元素插入到棧中並將原始元素恢復到棧中。

使用佇列

在這種方法中，我們將使用佇列來臨時儲存元素，同時將新元素插入到棧底。此方法是管理元素順序的更好方法。使用佇列，我們可以將新元素新增到棧中，而不會篡改現有元素。

步驟

以下是使用佇列將元素插入到棧底的步驟：

• 初始化一個佇列：建立一個佇列來儲存棧中的元素。
• 轉移元素：從棧中彈出元素並將它們入隊到佇列中。
• 插入新元素：將新元素推入棧中。
• 恢復元素：將佇列中的元素出隊並將其推回棧中。

示例

import java.util.Stack;
import java.util.LinkedList;
import java.util.Queue;
public class InsertAtBottomUsingQueue {
   public static void insertAtElementBottom(Stack<Integer> st, int x) {
      // Create a queue to hold elements
      Queue<Integer> queue = new LinkedList<>();

      // Step 1: add elements from the stack to the queue
      while (!st.isEmpty()) {
         queue.add(st.pop());
      }

      // Step 2: Push the new element into the stack
      st.push(x);

      // Step 3: get back elements from the queue to the stack
      while (!queue.isEmpty()) {
         st.push(queue.remove());
      }
   }

   public static void main(String[] args) {
      Stack<Integer> st = new Stack<>();
      st.push(1);
      st.push(2);
      st.push(3);
      st.push(4);

      System.out.println("Original Stack: " + st);
      insertAtElementBottom(st, 0);
      System.out.println("Stack after inserting 0 at the bottom: " + st);
   }
}

輸出

以下是上述程式碼的輸出：

Original Stack: [1, 2, 3, 4]
Stack after inserting 0 at the bottom: [0, 4, 3, 2, 1]

在此實現中，我們使用了一個佇列來臨時儲存元素。我們首先將現有元素從棧轉移到佇列。然後，我們將新元素推入棧中並將原始元素從佇列恢復到棧中

注意：我們可以使用其他資料結構，例如陣列、連結串列、ArrayList 等，而不是佇列。