Array implementation of Stack
In array implementation, the stack is formed by using the array. All the operations regarding the stack are performed using arrays. Lets see how each operation can be implemented on the stack using array data structure.
Adding an element onto the stack [push operation]
Adding an element into the top of the stack is referred to as push operation. Push operation involves following two steps.
- Increment the variable Top so that it can now refere to the next memory location.
- Add element at the position of incremented top. This is referred to as adding new element at the top of the stack.
Stack is overflown when we try to insert an element into a completely filled stack therefore, our main function must always avoid stack overflow condition.
Algorithm:
Time Complexity : o[1]
implementation of push algorithm in C language
Deletion of an element from a stack [Pop operation]
Deletion of an element from the top of the stack is called pop operation. The value of the variable top will be incremented by 1 whenever an item is deleted from the stack. The top most element of the stack is stored in an another variable and then the top is decremented by 1. the operation returns the deleted value that was stored in another variable as the result.
The underflow condition occurs when we try to delete an element from an already empty stack.
Algorithm :
Time Complexity : o[1]
Implementation of POP algorithm using C language
Visiting each element of the stack [Peek operation]
Peek operation involves returning the element which is present at the top of the stack without deleting it. Underflow condition can occur if we try to return the top element in an already empty stack.
Algorithm :
PEEK [STACK, TOP]
Time complexity: o[n]
Implementation of Peek algorithm in C language
C program
Java Program
C# Program
Growable array based stack
We all know about Stacks also known as Last-In-First-Out[LIFO] structures. Stack primarily has two main operation namely push and pop, where push inserts an element at top and pop removes an element from top of the stack.
Now, whenever an implementation of stack is considered its size is pre-determined or fixed. Even though it is dynamically allocated, still once it is made its size cannot be changed. And hence a condition called “stack full” arises.
But what if a stack can grow as more elements are inserted or more elements are going to be inserted in future. Remember, we are talking about array based Stack. Growable Stack is the concept of allocating more memory such that “stack full” condition does not arises easily.
A Growable array-based Stack can be implemented by allocating new memory larger than previous stack memory and copying elements from old stack to new stack. And then at last change the name of new stack to the name which was given to old stack
There are two strategy for growable stack:
1. Tight Strategy : Add a constant amount to the old stack [N+c]
2. Growth Strategy : Double the size of old stack [2N]
There are two operation on growable stack:
1. Regular Push Operation: Add one element at top of stack
2. Special Push Operation: Create a new stack of size greater than old stack [according to one of the strategy above] and copy all elements from old stack and then push the new element to the new stack.
|
// CPP Program to implement growable array based stack
// using tight strategy
#include
using namespace std;
// constant amount at which stack is increased
#define BOUND 4
// top of the stack
int top = -1;
// length of stack
int length = 0;
// function to create new stack
int* create_new[int* a]
{
// allocate memory for new stack
int* new_a = new int[length + BOUND];
// copying the content of old stack
for [int i = 0; i < length; i++]
new_a[i] = a[i];
// re-sizing the length
length += BOUND;
return new_a;
}
// function to push new element
int* push[int* a, int element]
{
// if stack is full, create new one
if [top == length - 1]
a = create_new[a];
// insert element at top of the stack
a[++top] = element;
return a;
}
// function to pop an element
void pop[int* a]
{
top--;
}
// function to display
void display[int* a]
{
// if top is -1, that means stack is empty
if [top == -1]
cout
Chủ Đề |