Une pile est une structure de données qui suit le principe LIFO (dernier dans, premier sorti). En d'autres termes, le dernier élément que nous ajoutons à une pile est le premier à être supprimé. Lorsque nous ajoutons (ou poussons) des éléments à une pile, ils sont placés sur le dessus; c'est-à-dire surtout les éléments précédemment ajoutés.
Il peut y avoir certains scénarios où nous devons ajouter un élément au bas de la pile. Il existe plusieurs façons d'ajouter un élément au bas de la pile. Ils sont -
Nous pouvons insérer un élément au bas d'une pile à l'aide d'une pile auxiliaire (une pile secondaire à l'aide de laquelle nous effectuerons des opérations) en Java. Ici, nous utiliserons deux piles (une pile principale et une pile auxiliaire) pour insérer un élément au bas de la pile principale.
La pile principale aura les éléments d'origine, tandis que la pile auxiliaire nous aidera à réorganiser les éléments. Cette méthode est facile à comprendre.
Voici les étapes pour insérer un élément au bas d'une pile à l'aide d'une pile auxiliaire:
Voici un exemple de la façon dont nous pouvons utiliser une pile auxiliaire pour ajouter un élément en bas -
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);
}
}
Dans le programme ci-dessus, nous commençons par pousser les éléments 1, 2, 3 et 4 dans la pile. Ensuite, nous transférons ces éléments vers une autre pile. Après cela, nous insérons l'élément cible dans la pile principale. Enfin, nous récupérons tous les éléments de la pile auxiliaire.
La récursivité est une autre façon d'insérer un élément au bas d'une pile. Dans cette approche, nous utiliserons une fonction récursive pour faire éclater tous les éléments de notre pile jusqu'à ce qu'il devienne vide, et une fois qu'il deviendra vide, nous insérons le nouvel élément dans la pile, puis repousserons les éléments dans la pile.
Voici les étapes pour insérer un élément au bas d'une pile en utilisant la récursivité:
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);
}
}
Dans le programme ci-dessus, nous avons défini une fonction récursive qui insère un nouvel élément au bas de la pile, nous avons ensuite continué à faire éclater les éléments de la pile jusqu'à ce que la pile soit vide, puis nous avons inséré le nouvel élément et après cela , nous avons restauré les éléments précédents dans la pile.
Nous pouvons également atteindre la tâche donnée en utilisant une variable temporaire. Nous utilisons cette variable pour stocker les éléments pendant que nous manipulons la pile. Cette méthode est facile et nous pouvons implémenter en utilisant une boucle simple.
Voici les étapes pour insérer un élément au bas d'une pile en utilisant une variable temporaire & lt;
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);
}
}
Dans ce programme, nous avons utilisé un tableau temporaire pour maintenir les éléments tout en manipulant la pile. Nous insérons ensuite le nouvel élément dans la pile et restaurons les éléments d'origine dans la pile.
Dans cette approche, nous utiliserons une file d'attente pour maintenir temporairement les éléments tout en insérant un nouvel élément au bas de la pile. Cette méthode est la meilleure façon de gérer l'ordre des éléments. En utilisant une file d'attente, nous pouvons un nouvel élément à une pile sans falsification des éléments existants.
Voici les étapes pour insérer un élément au bas d'une pile à l'aide d'une file d'attente -
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);
}
}
Voici la sortie du code ci-dessus -
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);
}
}
Dans cette implémentation, nous avons utilisé une file d'attente pour maintenir les éléments pour une période temporaire. Nous transférons d'abord les éléments existants de la pile à la file d'attente. Ensuite, nous poussons le nouvel élément dans la pile et restaurons les éléments d'origine de la file d'attente vers la pile
Remarque: Nous pouvons utiliser d'autres structures de données telles que Array, LinkedList, ArrayList, etc. au lieu d'une file d'attente.
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
