Invertir una array usando Stack

Dado un arreglo arr[] de tamaño N , la tarea de invertir el arreglo usando Stack .

Ejemplos:

Entrada: arr[] = { 10, 20, 30, 40, 50 }
Salida: 50 40 30 20 10
Explicación:
Invertir la array modifica arr[] a { 50, 40, 30, 20, 10 }
Por lo tanto, la salida requerida es 50 40 30 20 10.

Entrada: arr[] = { 1 }
Salida: 1

Enfoque iterativo y recursivo: consulte el artículo invierta una array para resolver este problema de forma iterativa o recursiva.
Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Enfoque basado en pila : siga los pasos a continuación para resolver el problema:

• Inicialice una pila para almacenar los elementos de la array.
• Atraviese la array y coloque todos los elementos de la array en la pila .
• >Extraiga los elementos de la pila e insértelos en la array.
• Finalmente, imprima la array.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std;    // Structure of stack class Stack { public:     // Stores index of top     // element of a stack     int top;        // Stores maximum count of     // elements stored in a stack     unsigned capacity;        // Stores address of     // array element     int* array; };    // Function to Initialize a stack // of given capacity. Stack* createStack(unsigned capacity) {     Stack* stack = new Stack();     stack->capacity = capacity;     stack->top = -1;     stack->array = new int[(stack->capacity                             * sizeof(int))];     return stack; }    // Function to check if // the stack is full or not int isFull(Stack* stack) {     return stack->top            == stack->capacity - 1; }    // Function to check if // the stack is empty or not int isEmpty(Stack* stack) {     return stack->top == -1; }    // Function to insert an element // into the stack. void push(Stack* stack, int item) {        // If stack is full     if (isFull(stack))         return;        // Insert element into stack     stack->array[++stack->top] = item; }    // Function to remove an element // from stack. int pop(Stack* stack) {        // If stack is empty     if (isEmpty(stack))         return -1;        // Pop element from stack     return stack->array[stack->top--]; }    // Function to reverse the array elements void reverseArray(int arr[], int n) {        // Initialize a stack of capacity n     Stack* stack = createStack(n);        for (int i = 0; i < n; i++) {            // Insert arr[i] into the stack         push(stack, arr[i]);     }        // Reverse the array elements     for (int i = 0; i < n; i++) {            // Update arr[i]         arr[i] = pop(stack);     }        // Print array elements     for (int i = 0; i < n; i++)         cout << arr[i] << " "; }    // Driver Code int main() {        int arr[] = { 100, 200, 300, 400 };        int N = sizeof(arr) / sizeof(arr[0]);     reverseArray(arr, N);     return 0; }

C

// C program to implement // the above approach #include <limits.h> #include <stdio.h> #include <stdlib.h> #include <string.h>    // Structure of stack struct Stack {        // Stores index of top     // element of a stack     int top;        // Stores maximum count of     // elements stored in a stack     unsigned capacity;        // Stores address of     // array element     int* array; };    // Function to Initialize a stack // of given capacity. struct Stack* createStack(unsigned capacity) {     struct Stack* stack         = (struct Stack*)malloc(             sizeof(struct Stack));     stack->capacity = capacity;     stack->top = -1;     stack->array         = (int*)malloc(             stack->capacity             * sizeof(int));     return stack; }    // Function to check if // the stack is full or not int isFull(struct Stack* stack) {     return stack->top            == stack->capacity - 1; }    // Function to check if // the stack is empty or not int isEmpty(struct Stack* stack) {     return stack->top == -1; }    // Function to insert an element // into the stack. void push(struct Stack* stack, int item) {        // If stack is full     if (isFull(stack))         return;        // Insert element into stack     stack->array[++stack->top] = item; }    // Function to remove an element // from stack. int pop(struct Stack* stack) {        // If stack is empty     if (isEmpty(stack))         return -1;        // Pop element from stack     return stack->array[stack->top--]; }    // Function to reverse the array elements void reverseArray(int arr[], int n) {        // Initialize a stack of capacity n     struct Stack* stack = createStack(n);        for (int i = 0; i < n; i++) {            // Insert arr[i] into the stack         push(stack, arr[i]);     }        // Reverse the array elements     for (int i = 0; i < n; i++) {            // Update arr[i]         arr[i] = pop(stack);     }        // Print array elements     for (int i = 0; i < n; i++)         printf("%d ", arr[i]); }    // Driver Code int main() {        int arr[] = { 100, 200, 300, 400 };        int N = sizeof(arr) / sizeof(arr[0]);     reverseArray(arr, N);     return 0; }

Java

// Java program to implement // the above approach import java.util.*;    // Structure of stack class Stack {        // Stores maximum count of     // elements stored in a stack     int size;        // Stores index of top     // element of a stack     int top;        // Stores address of     // array element     int[] a;        // Function to check if     // the stack is empty or not     boolean isEmpty()     {         return (top < 0);     }        // Function to Initialize     // a stack of given capacity.     Stack(int n)     {         top = -1;         size = n;         a = new int[size];     }        // Function to push     // an element into Stack     boolean push(int x)     {            // If Stack is full         if (top >= size) {             System.out.println(                 "Stack Overflow");             return false;         }         else {                // Insert element             // into stack             a[++top] = x;             return true;         }     }        // Function to remove an element     // from stack.     int pop()     {            // If stack is empty         if (top < 0) {             System.out.println(                 "Stack Underflow");             return 0;         }            // Pop element from stack         else {             int x = a[top--];             return x;         }     } }    // Driver Code class Main {        // Function to reverse the array elements     public static void reverse(int arr[], int n)     {            // Initialize a stack of capacity n         Stack obj = new Stack(n);            for (int i = 0; i < n; i++) {                // Insert arr[i] into the stack             obj.push(arr[i]);         }            // Reverse the array elements         for (int i = 0; i < n; i++) {                // Update arr[i]             arr[i] = obj.pop();         }            // Print array elements         for (int i = 0; i < n; i++) {             System.out.print(arr[i] + " ");         }     }        // Driver function     public static void main(String args[])     {         int n = 4;            // Create a new array         int[] a = new int[] { 100, 200, 300, 400 };            // Call reverse method         reverse(a, n);     } }

Producción:

400 300 200 100

Complejidad temporal: O(N)
Espacio auxiliar: O(N) .