Stack in C

What is Stack?

A stack in C refers to a linear data structure that allows the insertion of a new element and deletion of an existing element at the same end which is depicted as the top of the stack.

For stack implementation, the pointer must be maintained at the top of the stack, i.e., the last element to be inserted in the stack. You can access the elements only at the top of the stack.

The concept of the stack is widely used in backtracking, expression evaluation, recursion, and execution of other data structures like queues.

Basic Operations on Stack

You can manipulate a stack using certain stack operations in C. The push and pop in stack in C are the two widely used stack operations. Let’s look at the briefs of all basic operations on the stack.

push()	It inserts an element into the stack. If the stack is full, it is called an Overflow condition.
pop()	It discards an element from the stack. The elements are popped in the reverse order in which they are being pushed. In case the stack is empty, it is called an Underflow condition.
top()	It returns the top element of the stack.
size()	It returns the size of the stack.
isEmpty()	It returns true if the stack is empty otherwise false.

Time Complexity of Stack Operations

Operations	Complexity
push()	O(1)
pop()	O(1)
size()	O(1)
isEmpty()	O(1)

Types of Stacks

Two major types of stacks are fixed size stacks and dynamic size stacks. They are discussed here:

Fixed size stacks: The size of this type of stack in C is fixed size. Its size can’t increase or reduce dynamically.

Dynamic size stacks: The size of a dynamic size stack in C can increase or reduce dynamically. It is implemented through a linked list.

Here’s the list of a few other types of stacks:

Infix to Postfix stack
Recursion stack
Memory Management stack
Balanced Parenthesis stack
Undo-Redo stack

Applications of the stack

A stack in C is used for evaluating expressions comprising operators and operands.
It is used for backtracking to check parenthesis coordination in an expression.
It helps to program languages to manage function calls.
Stacks can be employed to reverse the order of characters in a string.
Stacks are valuable for implementing undo and redo functionality in applications like text editors.
It can be used to convert expressions from one form to another, such as infix to postfix or infix to prefix.
The stack data structures efficiently evaluate arithmetic operations by transforming them into a particular notation (prefix or postfix) and subsequently calculating its values.

Implementation of Stack

You can implement a stack in C using a linked list or an array.

When implementing it using an array-based method, the push operation is used to increment the index of the top element and assign the new element at the particular index.

In a linked list-based implementation, the push operation is used to create a new node with the new element and initialise the next pointer of the existing top node to the new node. Subsequently, the value of the existing top node is returned.

Implementing Stack using Arrays

Here’s an example program to implement stack in C using an array:

#include <stdio.h>
#include <stdbool.h>

#define size_limit 100

typedef struct
{
int data[size_limit];
int top_element;
} Stack;

void initialize(Stack* stack)
{
stack->top_element = -1;
}

bool isFull(Stack* stack)
{
return stack-> top_element == size_limit - 1;
}

bool isEmpty(Stack* stack) {
return stack-> top_element == -1;
}

void push(Stack* stack, int value)
{
if (isFull(stack)) {
  printf("Stack is overflow! It cannot push element anymore %d.\n", value);
}
else
{
  stack->top_element++;
  stack->data[stack->top_element] = value;
  printf("The stack has pushed element %d into the stack.\n", value);
}
}

int pop(Stack* stack)
{
if (isEmpty(stack))
{
  printf("Stack is underflow! It cannot pop out element from an empty stack.\n");
  return -1; // returns a sentinel value or corrects error uniquely
}
else
{
  int value = stack->data[stack->top_element];
  stack->top_element--;
  printf("The stack has popped element %d from the stack.\n", value);
  return value;
}
}
int peek(Stack* stack) {
if (isEmpty(stack)) {
  printf("The stack is empty.\n");
  return -1;
}
else
{
  return stack->data[stack->top_element];
}
}

int main() {
Stack stack;
initialize(&stack);

push(&stack, 10);
push(&stack, 20);
push(&stack, 30);

printf("The top element of the stack is %d\n", peek(&stack));

pop(&stack);
pop(&stack);
pop(&stack);
pop(&stack); // these commands pop out the elements from an empty stack

return 0;
}

Output:

The stack has pushed element 10 into the stack.
The stack has pushed element 20 into the stack.
The stack has pushed element 30 into the stack.
The top element of the stack is 30
The stack has popped element 30 from the stack.
The stack has popped element 20 from the stack.
The stack has popped element 10 from the stack.
Stack is underflow! It cannot pop out element from an empty stack.

In the above program, a Stack struct stores an array of integers. It also stores the value of the top index to track the current top element. The program performs stack operations using initialise, isEmpty, isFull, push, pop, and peek in stack in C.

In the main function, the program creates an instance of the Stack struct. Different stack operations in C are performed, like pushing elements, popping elements, and analysing the top element. During stack underflow (popping out from an empty stack) and stack overflow (pushing into a full stack), the program displays relevant messages to the user.

Advantages of array implementation

Implementing a stack using an array is relatively straightforward compared to other data structures.
It does not require additional memory for storing pointers, resulting in memory savings.
Since stacks are destructive, you don’t need to copy them whenever you perform an operation on them.
It is more time-efficient than a linked list type stack implementation.
Usually, you need stacks in a limited number so that much memory is not wasted.

Disadvantages of array implementation

The array implementation of the stack is not dynamic; it’s fixed. It doesn’t increase or decrease based on the requirements at runtime.
Insertion and removal operations in an array are very difficult because they store the elements in sequential memory locations.

Implementing Stack using Linked List

Here’s an example code to implement stack in C using linked list:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node
{
int number;
struct Node* next;
} Node;

typedef struct
{
Node* top_element;
} Stack;

void initialize(Stack* stack)
{
stack-> top_element = NULL;
}

bool isEmpty(Stack* stack)
{
return stack-> top_element == NULL;
}

void push(Stack* stack, int value)
{
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->number = value;
newNode->next = NULL;

if (isEmpty(stack))
{
  stack-> top_element = newNode;
}
else
{
  newNode->next = stack->top_element;
  stack-> top_element = newNode;
}

printf("The stack has pushed element %d into the stack.\n", value);
}
int pop(Stack* stack)
{
if (isEmpty(stack))
{
  printf("The stack is underflow, it cannot pop element from an empty stack.\n");
  return -1; // returns a sentinel value or deals with an error uniquely
}
else
{
  Node* temp = stack->top_element;
  int value = temp->number;
  stack-> top_element = temp->next;
  free(temp);
  printf("The stack has popped element %d from the stack.\n", value);
  return value;
}
}
int peek(Stack* stack)
{
if (isEmpty(stack))
{
  printf("The stack is empty.\n");
  return -1;
}
else
{
  return stack->top_element->number;
}
}

int main()
{
Stack stack;
initialize(&stack);

push(&stack, 5);
push(&stack, 10);
push(&stack, 20);

printf("The top element of the stack is %d\n", peek(&stack));

pop(&stack);
pop(&stack);
pop(&stack);
pop(&stack); // these commands pop out from an empty stack

return 0;
}

Output:

The stack has pushed element 5 into the stack.
The stack has pushed element 10 into the stack.
The stack has pushed element 20 into the stack.
The top element of the stack is 20
The stack has popped element 20 from the stack.
The stack has popped element 10 from the stack.
The stack has popped element 5 from the stack.
The stack is underflow, it cannot pop an element from an empty stack.

The above program uses the Stack and Node structures. It performs stack operations using functions like initialise, push, pop, isEmpty, and peek. The program creates a new node and links it at the top of the stack after updating the next pointers. If the stack is already empty, the new node is the top node. Otherwise, the new node points to the former top node, and subsequently, it works as the new top node.

The program employs dynamic memory allocation with free and malloc functions to create and free up each node. Moreover, the program supports error handling in cases like stack underflow.

Advantages of Linked List implementation

A stack’s linked list implementation can increase and shrink as per the requirements at runtime.
It is used in virtual machines, including the Java Virtual Machine (JVM), due to its ability to efficiently manage memory and handle dynamic data structures.

Disadvantages of Linked List implementation

It requires additional memory to store the pointers that connect the elements.
It doesn’t allow direct random access to elements.

Conclusion

A stack in C provides a convenient way to add and remove elements from a data structure. The ease of accessing elements ensures you can use stack to evaluate an expression, check parenthesis matching, and other applications. One advantage of using stacks in C is that they require minimal memory usage.

In addition to learning the tutorials, pursuing upGrad’s Executive Post Graduate Programme in Software Development by IIIT-B can prove to be a step forward to your career development in the tech industry. The outstanding perks of this course include live lectures, an exclusive job opportunities portal, an AI-powered profile builder, interview preparation, and more. With industry expert guidance, upGrad can help accelerate your career growth in STEM.

Enroll now to initiate your journey!

FAQs

Q. Is stack a container of objects?

Yes, a stack works as a container of objects which are inserted and removed as per the last-in-first-out (LIFO) rule. The pushdown stacks support only two operations, i.e., push the item into the stack and pop out the item from the stack.

Q. How to check whether a stack is full or empty?

You can use the stack. empty() to check whether the stack is empty or not. This method doesn’t need any parameters. It returns true if the stack is empty and false if the stack isn’t empty.

Q. What is a peek in the stack in C?

Peek() is one of the significant operations in the stack that helps you to obtain the top element of the stack without deleting the particular element.

Q. What is a static stack in C?

A static stack in C contains a finite number of elements. It is also called a bounded stack.

67-A Header Files in C

69-A Stack Using Linked List in C

Your email address will not be published. Required fields are marked *

Comment*

Name*

E-mail*