Stack Data Structure using C Programming

If we keep some books on our table one on top of another, we call it a stack of books. This informal idea can be extended to the official understanding of stack data structure.

In this context, we do understand that the books are accessible from the top of the stack of books, not from any intermediate positions. If you want to put another book that is to be kept on top of the books and if we want to remove a book, that is to be removed from the top. The same concept is used in this stack data structure.

Basically, a stack is a collection of data elements that are kept in an order, where elements are added and removed on the same side of the elements. These operations are known as push (insertion) and pop (deletion).

A very common example of the use of a stack is a recursive function. In a recursive function, the state of the caller function is stored in the stack. And after completion of the called function, the control of the program moves to the caller.

Hence, in which order the elements are inserted, in the reverse order the elements are deleted. Thus, we can consider that one end of the stack is blocked and operations are performed at the other end. In the following figure dark end represents that the operations can not be performed at that end.

---

Applications

---

Some of the common applications of the stack are

• Function call / Recursive function call
• Infix to postfix / prefix conversion
• Postfix expression evaluation etc.

These applications will be discussed in the following tutorials.

---

Definition of stack

---

A Stack is a collection of data elements, where elements are inserted and deleted at the same end. These operations are known as push (insertion) and pop (deletion).

Hence, we can understand in which order the elements are inserted, in the reverse order the elements are deleted. The operations on a stack follow a well-known technique, called Last In First Out (LIFO).

---

Operations on Stack

---

Generally, two operations are performed in the Stack data structure. The operations are

• insertion of new elements to the stack, known as Push operation and
• removal of existing elements from the stack, known as Pop operation.

There is another operation, which is used to read the topmost element of the stack without performing any modification to the stack. The operation is known as Peek.

---

Stack using Array

---

How to define and create Stack?

#define CAPACITY 10

typedef struct Stack
{
	int data[CAPACITY];
	int topindex;
} stack;

void createStack(stack *s)
{
	s->topindex = -1;
}

Push Operation

void push(stack *s, int data)
{
	if(isFull(s))
	{
		printf("Stack is Full.");
	}
	else
	{
		s->topindex++;
		s->data[s->topindex] = data;
	}
}

Pop Operation

int pop(stack *s)
{
	int temp = -9999;
	if(isEmpty(s))
	{
		printf("Stack is Empty.");
	}
	else
	{
		temp = s->data[s->topindex];
		s->topindex--;
	}
	return temp;
}

Checking whether the Stack is full or not?

int isFull(stack *s)
{
	if(s->topindex == CAPACITY - 1)
		return 1;
	else
		return 0;
}

Checking whether the Stack is empty or not?

int isEmpty(stack *s)
{
	if(s->topindex == -1)
		return 1;
	else
		return 0;
}

Complete code 

#include <stdio.h> #include <stdlib.h> #define CAPACITY 5 typedef struct Stack { int data[CAPACITY]; int topindex; } stack; void createStack(stack *s); void push(stack *s, int data); int pop(stack *s); int isFull(stack *s); int isEmpty(stack *s); int main() { stack s; int choice, data; createStack(&s); while(1) { printf("\nChoices:\n 1-> Push\n 2-> Pop \n 0->exit"); printf("\n Enter your choice:"); scanf("%d", &choice); switch(choice) { case 1: printf("Enter data to push."); scanf("%d", &data); push(&s, data); break; case 2: data = pop(&s); if(data != -9999) printf("Poped item is : %d", data); break; case 0: exit(0); default: printf("\nInvalid choice"); } } } void push(stack *s, int data) { if(isFull(s)) { printf("Stack is Full."); } else { s->topindex++; s->data[s->topindex] = data; } } int pop(stack *s) { int temp = -9999; if(isEmpty(s)) { printf("Stack is Empty."); } else { temp = s->data[s->topindex]; s->topindex--; } return temp; } int isFull(stack *s) { if(s->topindex == CAPACITY - 1) return 1; else return 0; } int isEmpty(stack *s) { if(s->topindex == -1) return 1; else return 0; } void createStack(stack *s) { s->topindex = -1; }

---

Stack using Linked List

---

A Stack is a collection of data elements, where elements are inserted and deleted at the same end. These operations are known as push (insertion) and pop (deletion).

A very common example of use of stack is recursive function. In a recursive function, state of the caller function is stored in stack. And after completion of the called function the control of the program moves to the caller.

Hence, in which order the elements are inserted, in the reverse order the elements are deleted.

How to define Stack

typedef struct Node {
	int data;
	struct Node *next;
} node;

Push operation

void push(node **head, int item)
{
	node *newnode = (node *)malloc(sizeof(node));
	newnode->data = item;

	if(*head == NULL)
		newnode->next=NULL;
	else
		newnode->next = *head;

	*head = newnode;
}

Pop operation

int pop(node **head)
{
	node *temp;
	int data = -1;
	if(*head != NULL)
	{
		temp = *head;
		*head = (*head)->next;
		data = temp->data;
		free(temp);
	}
	return data;
}

Complete code

#include <stdio.h> typedef struct Node { int data; struct Node *next; } node; void printMenu(); void push(node **head, int item); int pop(node **head); int main(void) { int option, item, after, key; node *head = NULL, *nd, *preloc, *curloc; while(1) { printMenu(); scanf("%d", &option); switch(option) { case 1: printf("Enter item :"); scanf("%d", &item); push(&head, item); break; case 2: item = pop(&head); if(item == -1) printf("Stack is empty\n"); else printf("%d\n", item); break; case 0: exit(0); default: printf("Invalid option"); } } return 0; } void printMenu() { printf("Choose option\n"); printf(" 1: Push\n"); printf(" 2: Pop\n"); printf(" 0: Exit\n"); } void push(node **head, int item) { node *newnode = (node *)malloc(sizeof(node)); newnode->data = item; if(*head == NULL) newnode->next=NULL; else newnode->next = *head; *head = newnode; } int pop(node **head) { node *temp; int data = -1; if(*head != NULL) { temp = *head; *head = (*head)->next; data = temp->data; free(temp); } return data; }

Happy Exploring!