C++ Stack Exercises: Sort a stack using another stack
C++ Stack: Exercise-3 with Solution
Write a C++ program to sort a given stack (using an array) using another stack.
Test Data:
Input some elements onto the stack:
Stack elements: 0 1 5 2 4 7
Sort the elements in the stack:
Display the sorted elements of the stack:
Stack elements: 0 1 2 4 5 7
Sample Solution:
C++ Code:
#include <iostream>
using namespace std;
#define MAX_SIZE 15 // Maximum size of stack
class Stack {
private:
int top; // Index of top element
int arr[MAX_SIZE]; // Array to store elements
public:
Stack() {
top = -1; // Initialize top index to -1 (empty stack)
}
bool push(int x) {
if (isFull()) {
cout << "Stack overflow" << endl; // Display message if stack is full
return false; // Return false to indicate failure in pushing element
}
// Increment top index and add element to array
arr[++top] = x;
return true; // Return true to indicate successful element addition
}
int pop() {
if (isEmpty()) {
cout << "Stack underflow" << endl; // Display message if stack is empty
return 0; // Return 0 to indicate failure in popping element
}
// Return top element and decrement top index
return arr[top--];
}
int peek() {
if (isEmpty()) {
cout << "Stack is empty" << endl; // Display message if stack is empty
return 0; // Return 0 to indicate failure in peeking element
}
// Return top element without modifying top index
return arr[top];
}
bool isEmpty() {
// Stack is empty if top index is -1
return (top < 0);
}
bool isFull() {
// Stack is full if top index is equal to MAX_SIZE - 1
return (top >= MAX_SIZE - 1);
}
void display() {
if (top < 0) {
cout << "Stack is empty" << endl; // Display message if stack is empty
return;
}
cout << "\nStack elements: ";
for (int i = top; i >= 0; i--)
cout << arr[i] << " "; // Display elements of the stack
cout << endl;
}
void sort() {
Stack tmp; // Initialize a temporary stack
while (!isEmpty()) {
int x = pop(); // Pop an element from the original stack
while (!tmp.isEmpty() && tmp.peek() > x) {
// Pop elements from the temporary stack and push them back onto the original stack
push(tmp.pop());
}
// Push the popped element onto the temporary stack
tmp.push(x);
}
// Copy elements from the temporary stack back to the original stack
while (!tmp.isEmpty()) {
push(tmp.pop());
}
}
};
int main() {
Stack stk; // Initialize the stack stk
cout << "Input some elements onto the stack:\n";
stk.push(7);
stk.push(4);
stk.push(2);
stk.push(5);
stk.push(1);
stk.push(0);
stk.display(); // Display the elements of the stack
cout << "\nSort the elements in the stack:\n";
stk.sort();
cout << "Display the sorted elements of the stack:";
stk.display(); // Display the sorted elements of the stack
cout << "\nRemove two elements:";
stk.pop();
stk.pop();
stk.display(); // Display elements of the stack after popping
cout << "\nInput two more elements";
stk.push(-1);
stk.push(10);
stk.display(); // Display elements of the stack after pushing
cout << "\nSort the elements in the stack:\n";
stk.sort();
cout << "Display the sorted elements of the stack:";
stk.display(); // Display the sorted elements of the stack after sorting
cout << endl;
return 0;
}
Sample Output:
Input some elements onto the stack: Stack elements: 0 1 5 2 4 7 Sort the elements in the stack: Display the sorted elements of the stack: Stack elements: 0 1 2 4 5 7 Remove two elements: Stack elements: 2 4 5 7 Input two more elements Stack elements: 10 -1 2 4 5 7 Sort the elements in the stack: Display the sorted elements of the stack: Stack elements: -1 2 4 5 7 10
Flowchart:
CPP Code Editor:
Contribute your code and comments through Disqus.
Previous C++ Exercise: Implement a stack using an array with push, pop operations.
Next C++ Exercise: Reverse a stack (using an array) elements.
What is the difficulty level of this exercise?
It will be nice if you may share this link in any developer community or anywhere else, from where other developers may find this content. Thanks.
https://www.w3resource.com/cpp-exercises/stack/cpp-stack-exercise-3.php
- Weekly Trends and Language Statistics
- Weekly Trends and Language Statistics