Prefer the Array for Stack implementation in order to operate with a limited amount of data. Firstly, define a static array for data and define a variable to point to the top position. Then, implement the push, pop, and peek operations.
1. Stack Representation using Array
Here is an example of a stack with a capacity of 4. The capacity can be larger in real-time implementation.
// Stack maximum capacity
#define CAPACITY 4
// Stack data
int stack[CAPACITY];
// Index of top element
int top = -1;
2. Implementation of Stack using Array in C++
Here is an example program to implement stack using array in c++. This is an object-oriented implementation that encapsulates the stack using class.
/**
* C++ example to demonstrate the Stack implementation using Array
*/
#include <iostream>
#include <string>
using namespace std;
// Stack maximum capacity
#define CAPACITY 5
/**
* Stack implementation using Array
*/
class Stack
{
private:
// Stack data
int stack[CAPACITY];
// Index of top element
int top;
public:
// Constructor
Stack() : top(-1) {}
// Return true if the Stack is empty, false otherwise.
bool isEmpty();
// Returns true if the Stack is full, false otherwise.
bool isFull();
// Returns the top element without deleting
int peek();
// Push the new element to Stack
// Throws runtime_error if the stack is full
void push(int element);
// Pop the element from Stack
// Throws runtime_error if the stack is empty
int pop();
// Print the Stack
void print(string msg);
};
bool Stack::isEmpty() {
if (top == -1) {
cout << "Stack is Empty" << endl;
return true;
}
return false;
}
bool Stack::isFull() {
if (top == (CAPACITY-1)) {
cout << "Stack is Full" << endl;
return true;
}
return false;
}
int Stack::peek() {
if (isEmpty()) {
throw std::runtime_error("stack underflow");
}
return stack[top];
}
void Stack::push(int element) {
// Step 1. Return if the Stack is full, proceed otherwise
if (isFull()) {
throw std::runtime_error("stack overflow");
}
// Step 2. Move the Top to next position
top++;
// Step 3. Insert the new element on Top
stack[top] = element;
}
int Stack::pop() {
// Step 1. Return if the Stack is empty, proceed otherwise
if (isEmpty()) {
throw std::runtime_error("stack underflow");
}
// Step 2. Retrieve the element on Top
int element = stack[top];
// Step 3. Move Top to one position down
top--;
return element;
}
void Stack::print(string msg) {
cout << msg << endl;
if (isEmpty()) {
return;
}
cout << stack[top] << " <-- top" << endl;
for (int i=top-1; i >= 0; i--) {
cout << stack[i] << endl;
}
}
// The main function to begin the execution
int main()
{
// Create a Stack
Stack stack;
// Push the elements (10, 20, 30, 40 and 50)
try {
stack.push(10);
stack.push(20);
stack.push(30);
stack.push(40);
stack.print("Stack after inserting 10 20 30 and 40");
stack.push(50);
stack.print("Stack after pushing 50");
stack.push(60); // Expecting exception "stack overflow"
} catch (const std::exception& e) {
cout << "Push: exception received: " << e.what() << endl;
}
// Get the peek element
try {
int element = stack.peek();
cout << "Peek element returned " << element << endl;
} catch (const std::exception& e) {
cout << "Peek: exception received: " << e.what() << endl;
}
// Pop the elements from Stack
try {
int element = stack.pop();
cout << "Pop element returned " << element << endl;
element = stack.pop();
cout << "Pop element returned " << element << endl;
stack.print("Stack after poping two elements");
} catch (const std::exception& e) {
cout << "Pop: exception received: " << e.what() << endl;
}
}
Output
Stack after inserting 10 20 30 and 40
40 <-- top
30
20
10
Stack after pushing 50
50 <-- top
40
30
20
10
Stack is Full
Push: exception received: stack overflow
Peek element returned 50
Pop element returned 50
Pop element returned 40
Stack after poping two elements
30 <-- top
20
10
Also, look at the Stack implementation using Linked List.
In addition, you can look at the C program to implement the Stack using Array.
3. Stack Operations
Push and pop in Stack are the key operations.
3.1. Stack push with Array
Push operation inserts a new element into the top of the Stack. Also, increment the Top to point to the new element.
Algorithm of stack push()
- Return if the Stack is full, proceed otherwise
- Move the Top to the next position
- Insert the new element on the Top
Code snippet
void Stack::push(int element) {
// Step 1. Return if the Stack is full, proceed otherwise
if (isFull()) {
throw std::runtime_error("stack overflow");
}
// Step 2. Move the Top to the next position
top++;
// Step 3. Insert the new element on the Top
stack[top] = element;
}
Example for Stack push operation
Firstly, make sure that the stack is not full. The initial stack is empty and the Top is set to -1. However, the push operation follows the common procedure irrespective of whether the stack is empty or not. Increment the Top so that it becomes a valid array index and then insert the new element.
3.2. Stack pop with Array
Pop operation removes an element from the top of the Stack. Also, decrement the Top to point to the next element.
Algorithm of Stack pop()
- Return if the Stack is empty, proceed otherwise
- Retrieve the element on the Top
- Move Top to one position down
Code snippet
int Stack::pop() {
// Step 1. Return if the Stack is empty, proceed otherwise
if (isEmpty()) {
throw std::runtime_error("stack underflow");
}
// Step 2. Retrieve the element on Top
int element = stack[top];
// Step 3. Move Top to one position down
top--;
return element;
}
Example for Stack pop operation
Firstly, ensure that the Stack is not empty to perform the Pop operation. Then, retrieve the element on the Top and decrement the Top by one position.
4. When stack is implemented using the array
Implementing stacks using arrays is the preferred choice when the data is limited in size. In addition, all the advantages of the Array apply to the Stack.
4.1. Advantages and Disadvantages
Pros
- Array-based implementation of the stack works faster for push and pop operations. Because the memory is preallocated for the array, especially in continuous memory locations. So, it is cache friendly for the CPU.
Cons
- However, the array implementation is not suitable for dynamic data that can grow larger. Stack overflow can occur when it reaches its capacity. See Stack Implementation using Linked List to work with dynamic data.
Furthermore, see the comparison of Stack implementation using Array vs Linked List
5. Frequently Asked Questions (FAQ)
5.1. Can array be used as stack?
Yes. An array can be a building block for the Stack. But, an array allows random access to the elements whereas a stack always performs the operations on Top. So, the insertion and deletion must be restricted to one end of the array. For example, look at the above program to implement the stack using the array.
5.2. Stack vs Array
The key difference between an array and a stack is the order of insertion and deletion. A stack follows the Last In First Out (LIFO) order whereas the array allows random access.
| Stack | Array |
| A stack is an abstract data type restricted to follow the LIFO order for insertion and deletion. | In contrast, An array is a collection of linear items and allows random access to the elements using the index. |
| Specifically used for processing nested structures such as recursive operations. | Broadly used for linear structures and helps to build other data structures. In fact, a stack can be built using the array. |
| Mimics real-life stacks such as a stack of physical disks. So, the topmost disk must be removed first. | An array is like a shelf where we can place or remove an item from any section. |
| So, a stack supports limited operations which include push, pop, and peek. | Whereas, an array supports many operations such as insert, access, update, delete, search, sort, traverse, etc., |
5.3. Stack vs Stack ADT (Abstract Data Type)
In general, an Abstract Data Type (ADT) represents the interface and not the concrete implementation. So, the term Stack ADT represents the stack interface such as input/output and possible operations. In contrast, the word stack represents the concrete implementation such as the memory used for storing data and how the operations are implemented.