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 等，而不是队列。