Back to: Data Structures and Algorithms Tutorials
Implementation of Stack using Array in C:
In this article, I will discuss the Implementation of Stack using Array in C Language with Examples. Please read our previous article where we give you an introduction to the Stack Data Structure.
How do you implement stack using array in C?
We have already seen Stack ADT in the previous article, where we saw that for the definition of the stack, we require data representation and the operations on the data. So, first of all, we need the representation of data. What are the things required when we are using an array to implement a stack? Let us understand this with an example.
Here, we have taken an array of size 5. Also, we have a variable, size, where we store the size of the array. Next, we need a top pointer that will point to the topmost element of the array. So, here, we have taken a variable called Top that will store the topmost element of the array.
What should be the data type of the Top pointer?
Integer because it points to the index. So, Top will point to the recently inserted element in the array.
What should be the data type of the array?
This depends on what type of values you are storing in the array. Here, we have taken an integer array.
So, we need three things: an array of some size, the size of the array, and the topmost element of the array. That means we need three things to implement a stack by using an array in C Language.
Inside the stack, we insert and delete the element from the same end. Insertion and deletion will be done from the top. An array has two ends. We can insert or delete from any end of the array (right or left end).
Here, we have a few elements in the array, i.e., 10 and 5, which are stored at index positions 0 and 1, respectively. Now, we want to insert one more element, which is 2. So where should we insert it? At index 0 or at index 2? If we are inserting at index 0, then we have to shift all the elements to the right-hand side. So, inserting at index 2 will be a better way. So, we are inserting and deleting from the right-hand side of the array, as shown in the below image.
Insertion and deletion from the right side will take constant time (O(1)). We have updated the Top pointer to index 2, which points to element 2. When we work with a stack, we usually imagine it is vertical, as shown in the image below. In recursion, we have seen that the stack was vertical.
This is the representation of the array as a stack. We will represent the array as a vertical lane or stack. We require three things (array, size, and top). For this, we will combine them and define a structure. We can define a structure by grouping the related things under one name. So, let us define a structure for the stack as follows.
struct Stack { int size; int top; int *A; };
Here, we have the size and top variables of the type integer. And we have not declared any size for the array. Because the size of the array will be declared at the program’s runtime. So, at runtime, an array will be created with a user-defined size. We have taken a pointer in our structure. So, with the pointer, we will create an array at runtime so that we can dynamically create a stack. We are working with integer data, so we have used an integer-type pointer in our structure.
We will be using this structure wherever we will be using a stack. Now, let us see how to create and initialize this stack using the main method.
int main(){ struct Stack st; printf("Enter size of Stack: "); scanf("%d", &st.size); st.A = (int *)malloc(sizeof(int) * st.size); st.top = -1; }
Inside the main function, we have created an object st of the structure Stack.
Once the stack st is created, we will get an object that is st and has three things inside it: size, top, and A (pointer). Now, for creating a stack dynamically, we should know the size of the stack. So, let us take the size as input from the user. Suppose we got a size of 5 from the user. Now that we know the size, we will create an array of size 5, as shown in the image below.
Now, one more thing we have to do. We know that the top will point to the topmost element. For now, the stack is empty. So, there is no topmost element. Then where should the top point be? It should point outside the stack. It means if there is no element, the top should point outside the stack, and if there is an element, then point to the recently inserted element. The first element will be stored at index 0 in the array. So, the top should point to -1 if there is no element. So, we can create a stack with the above set of statements in C language. We are using the entire thing (stack) as a structure.
We will be looking at this diagram when we are working with the stack. Now, two important things here.
When will you say that the stack is empty?
Now, the stack is empty. So, what is the condition? When the top is at -1, then the stack is empty.
Condition for Empty Stack: if (top == -1)
When can we say that the stack is full?
If the top is pointing to a size-1 location, the stack will be full.
Condition For Full Stack: if (top == (size-1))
In the next article, we will look at how to perform the operations on the stack. In this article, I try to explain how to Implement a Stack using an Array in C Language with Examples. I hope you enjoy this Stack Implementation using an Array in the C Language article.