Given a stack S and an integer K, the task is to reverse the first K elements of the given stack
Examples:
Input: S = [ 1, 2, 3, 4, 5, 8, 3, 0, 9 ], K = 4
Output: [ 4, 3, 2, 1, 5, 8, 3, 0, 9 ]
Explanation: First 4 elements of the given stack are reversedInput: S = [ 1, 2, 3, 4, 5, 8, 3, 0, 9 ], K = 7
Output: [ 3, 8, 5, 4, 3, 2, 1, 0, 9 ]
Approach: The task can be solved using two auxiliary stacks to reverse the first K elements of the given stack. Follow the below steps to solve the problem:
- Create two stacks s1 and s2
- One by one pop all elements of the given stack and simultaneously push it into stack s1
- Now, pop k number of elements from s1 and push it in s2 simultaneously
- Pop all elements from stack s2, and push them into the given stack
- Similarly pop all elements from s1, and push them into the given stack
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to print the resultant stackvoid print(stack<int>& s){ vector<int> v; while (!s.empty()) { int temp = s.top(); s.pop(); v.push_back(temp); } reverse(v.begin(), v.end()); for (int i = 0; i < v.size(); i++) cout << " " << v[i] << " ";}// Function to reverse and push operation// in the stackvoid stack_reverse(stack<int>& s, int k){ stack<int> s1, s2; while (!s.empty()) { int temp = s.top(); s1.push(temp); s.pop(); } for (int i = 0; i < k; i++) { int temp = s1.top(); s2.push(temp); s1.pop(); } while (!s2.empty()) { int temp = s2.top(); s.push(temp); s2.pop(); } while (!s1.empty()) { int temp = s1.top(); s.push(temp); s1.pop(); }}// Driver Codeint main(){ stack<int> s; // s = [ 1, 2, 3, 4, 5, 8, 3, 0, 9 ] s.push(1); s.push(2); s.push(3); s.push(4); s.push(5); s.push(8); s.push(3); s.push(0); s.push(9); int k = 4; stack_reverse(s, k); print(s);} |
Java
// Java program for the above approachimport java.util.*;class GFG{ static Stack<Integer> s = new Stack<>(); // Function to print the resultant stack static void print() { Vector<Integer> v = new Vector<>(); while (!s.isEmpty()) { int temp = s.peek(); s.pop(); v.add(temp); } Collections.reverse(v); for (int i = 0; i < v.size(); i++) System.out.print(" " + v.get(i)+ " "); } // Function to reverse and push operation // in the stack static void stack_reverse(int k) { Stack<Integer> s1 = new Stack<>(), s2 =new Stack<>(); while (!s.isEmpty()) { int temp = s.peek(); s1.add(temp); s.pop(); } for (int i = 0; i < k; i++) { int temp = s1.peek(); s2.add(temp); s1.pop(); } while (!s2.isEmpty()) { int temp = s2.peek(); s.add(temp); s2.pop(); } while (!s1.isEmpty()) { int temp = s1.peek(); s.add(temp); s1.pop(); } } // Driver Code public static void main(String[] args) { // s = [ 1, 2, 3, 4, 5, 8, 3, 0, 9 ] s.add(1); s.add(2); s.add(3); s.add(4); s.add(5); s.add(8); s.add(3); s.add(0); s.add(9); int k = 4; stack_reverse(k); print(); }}// This code is contributed by gauravrajput1 |
Python3
# python3 program for the above approach# Function to print the resultant stackdef print(s): v = [] while (len(s) != 0): temp = s.pop() v.append(temp) v.reverse() for i in range(0, len(v)): print(f" {v[i]} ", end="")# Function to reverse and push operation# in the stackdef stack_reverse(s, k): s1, s2 = [], [] while (len(s) != 0): temp = s.pop() s1.append(temp) for i in range(0, k): temp = s1.pop() s2.append(temp) while (len(s2) != 0): temp = s2.pop() s.append(temp) while (len(s1) != 0): temp = s1.pop() s.append(temp)# Driver Codeif __name__ == "__main__": s = [] # s = [ 1, 2, 3, 4, 5, 8, 3, 0, 9 ] s.append(1) s.append(2) s.append(3) s.append(4) s.append(5) s.append(8) s.append(3) s.append(0) s.append(9) k = 4 stack_reverse(s, k) print(s) # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{ //print all element of stack static void print(Stack<int> stack) { int[] arr = new int[stack.Count]; int k=0; while (stack.Count !=0) { int temp = stack.Peek(); stack.Pop(); arr[k++]=temp; } Array.Reverse(arr); for (int i = 0; i < arr.Length; i++) Console.Write(arr[i] + " " ); } //function to reverse k element static void stack_reverse(Stack<int> stack,int k){ Stack<int> s1 = new Stack<int>(); Stack<int> s2 =new Stack<int>(); while (stack.Count != 0) { int temp = stack.Peek(); s1.Push(temp); stack.Pop(); } for (int i = 0; i < k; i++) { int temp = s1.Peek(); s2.Push(temp); s1.Pop(); } while (s2.Count != 0) { int temp = s2.Peek(); stack.Push(temp); s2.Pop(); } while (s1.Count != 0){ int temp = s1.Peek(); stack.Push(temp); s1.Pop(); } } static public void Main (){ //creating stack Stack<int> stack = new Stack<int>(); // Inserting elements into the Stack stack.Push(1); stack.Push(2); stack.Push(3); stack.Push(4); stack.Push(5); stack.Push(8); stack.Push(3); stack.Push(0); stack.Push(9); int k = 4; // calling a function to reverse k element stack_reverse(stack, k); print(stack); }}// This code is contributed by sourabhdalal0001. |
Javascript
<script> // JavaScript code for the above approach // Function to print the resultant stack function print(s) { let v = []; while (s.length != 0) { let temp = s[s.length - 1]; s.pop(); v.push(temp); } v.reverse(); for (let i = 0; i < v.length; i++) document.write(" " + v[i] + " "); } // Function to reverse and push operation // in the stack function stack_reverse(s, k) { let s1 = [], s2 = []; while (s.length != 0) { let temp = s[s.length - 1]; s1.push(temp); s.pop(); } for (let i = 0; i < k; i++) { let temp = s1[s1.length - 1]; s2.push(temp); s1.pop(); } while (s2.length != 0) { let temp = s2[s2.length - 1]; s.push(temp); s2.pop(); } while (s1.length != 0) { let temp = s1[s1.length - 1]; s.push(temp); s1.pop(); } } // Driver Code let s = []; // s = [ 1, 2, 3, 4, 5, 8, 3, 0, 9 ] s.push(1); s.push(2); s.push(3); s.push(4); s.push(5); s.push(8); s.push(3); s.push(0); s.push(9); let k = 4; stack_reverse(s, k); print(s); // This code is contributed by Potta Lokesh </script> |
Output
4 3 2 1 5 8 3 0 9
Time Complexity: O(N), N is the number of elements in the stack
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
