Stack is a collection of data elements serving Last In First Out (LIFO) functionality – whichever element comes last will be removed first.
This data structure helps solve a number of real life problems. Like undo / redo functionalities, recursive function implementation, solving arithmetic equations etc.
Basic Stack Operations
Push: Inserting a new element into the stack. The new element is inserted in such a way that it will be removed first.
Pop: Removing an element from the stack. The most recently inserted element will be removed.
Peek: Returning the last inserting element without removing that from the stack.
Display: Printing all elements in the stack – most recently inserted on top.
Stack Implementation
Here we’ll see how to implement stack and its basic operations using array.
#include <stdio.h>
#define SIZE 64
struct stack {
int element[SIZE];
int size;
};
void initialize(struct stack *s) {
/* Sanity check */
if (s == NULL) return;
s->size = 0;
}
int push(struct stack *s, int data) {
/* Sanity check */
if (s == NULL) return -1;
if (s->size >= SIZE) {
printf("Stack is full.\n");
return -1;
}
s->element[s->size] = data;
s->size++;
/*Returning the current stack size...*/
return s->size;
}
int pop(struct stack *s) {
if (s == NULL || s->size == 0) {
printf("Stack is empty.\n");
return -1;
}
s->size--;
return s->element[s->size];
}
int peek(struct stack *s) {
if (s == NULL || s->size == 0) {
printf("Stack is empty.\n");
return -1;
}
return s->element[s->size - 1];
}
void display(struct stack *s) {
int data;
int i;
if (s == NULL || s->size == 0) {
printf("Stack is empty.\n");
return;
}
for (i = s->size - 1; i >= 0; i--) {
printf("%d\n", s->element[i]);
}
}
int main(){
struct stack s;
int data;
int repeat = 1;
int choice;
initialize(&s);
while(repeat) {
printf("\nOptions: \n");
printf(" 1. Push \n");
printf(" 2. Pop \n");
printf(" 3. Peek \n");
printf(" 4. Display \n");
printf(" 5. Exit \n");
printf("Enter choice: ");
scanf("%d", &choice);
switch(choice) {
case 1:
printf("Enter a number: ");
scanf("%d", &data);
push(&s, data);
printf("The entered number is pushed.\n");
break;
case 2:
data = pop(&s);
printf("The popped numner: %d.\n", data);
break;
case 3:
data = peek(&s);
printf("The peeked numner: %d.\n", data);
break;
case 4:
printf("The stack elements: \n");
display(&s);
break;
case 5:
repeat = 0;
break;
default:
printf("Wrong choice.\n");
break;
}
}
return 0;
}
This program is implemented in such a way that multiple stacks can be used in the program at the same time. That’s why the functions take a stack as input. They work on the input stack.
Let’s discuss on the various elements of this program.
The stack data structure is defined as a C structure consisting of an array and an integer. The array holds the stack elements and the integer is the number of stack elements.
The initialize() function: simply sets the stack size to 0.
The push() function: does the sanity checking whether the stack pointer is invalid or the stack is full. In that case it returns -1 to signify push operation is failed. Then it assign the new element at the index equal to the current stack size. Then it increases the size. So the next element will be inserted at the next index.
The pop() function: decrements the stack size. Then it returns the array element of the index equal to the changed size. It means that the next pushed element will placed at the same place.
The pop() function: same as the pop() function but the stack size is not decreased. So, this function will return the same element if it is called multiple times.
The main() function runs in a infinite loop asking for options. It then does the selected stack operation.
Here is a sample output.
$ cc test.c -o test
$ ./test
Options:
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter choice: 1
Enter a number: 11
The entered number is pushed.
Options:
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter choice: 1
Enter a number: 22
The entered number is pushed.
Options:
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter choice: 1
Enter a number: 33
The entered number is pushed.
Options:
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter choice: 1
Enter a number: 44
The entered number is pushed.
Options:
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter choice: 1
Enter a number: 55
The entered number is pushed.
Options:
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter choice: 4
The stack elements:
55
44
33
22
11
Options:
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter choice: 2
The popped numner: 55.
Options:
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter choice: 4
The stack elements:
44
33
22
11
Options:
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter choice: 3
The peeked numner: 44.
Options:
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter choice: 5
