C Notes
HubApplications of C Programming LanguageFeatures of C Programming LanguageHistory of C Programming LanguageWhat is C Language?Why Learn C Programming in 2024?First C Program - Hello World in C with ExplanationGCC Compiler - Complete Guide to GNU C CompilerInstall C Compiler on Linux - GCC Setup Guide for All DistrosInstall C Compiler on macOS - Xcode Command Line Tools and Homebrew GCCInstall C Compiler on Windows - MinGW, MSYS2, and WSL GuideSetup VS Code for C Programming - Complete Configuration GuideC Syntax Rules — Complete GuideComments in C ProgrammingConstants in C ProgrammingData Types in CIdentifiers in C ProgrammingKeywords in C ProgrammingStructure of a C ProgramVariables in C ProgrammingArithmetic Operators in C ProgrammingAssignment Operators in C ProgrammingBitwise Operators in C ProgrammingIncrement and Decrement Operators in CLogical Operators in C ProgrammingRelational Operators in C ProgrammingTernary Operator in C ProgrammingBreak Statement in C ProgrammingContinue Statement in C ProgrammingDo-While Loop in C ProgrammingFor Loop in C ProgrammingGoto Statement in C Programmingif-else Statement in C Programmingif Statement in C ProgrammingNested if Statements in C ProgrammingSwitch Statement in C ProgrammingWhile Loop in C ProgrammingFunction Arguments in C - Pass by Value vs Pass by ReferenceFunction Call in C ProgrammingFunction Declaration (Prototype) in CFunction Definition in C ProgrammingIntroduction to Functions in C ProgrammingRecursion in C ProgrammingReturn Statement in C ProgrammingStorage Classes in C ProgrammingArray Operations in C - Searching, Sorting, Insert and DeleteArray Programs in C - Reverse, Rotate, Duplicates, MergeIntroduction to Arrays in C ProgrammingMultidimensional Arrays in C ProgrammingOne Dimensional Arrays in C ProgrammingPassing Arrays to Functions in CTwo Dimensional Arrays in C ProgrammingString Comparison in C - strcmp, strncmp, Case-InsensitiveString Functions in C - strlen, strcpy, strcat, strcmpC String Handling Library - Complete string.h ReferenceString Manipulation in C - Reverse, Uppercase, PalindromeString Programs in C - Anagram, Word Count, Vowels, FrequencyStrings in C Programming - Complete IntroductionDouble Pointers in C - Pointer to PointerPointer Arithmetic in C ProgrammingPointer Declaration and Initialization in CPointer Programs in C - Swap, String Reversal, Dynamic AllocationPointers and Arrays in C - The Relationship ExplainedPointers and Functions in C - Pass by ReferenceIntroduction to Pointers in C ProgrammingVoid Pointers in C - Generic Pointers Guidecalloc() in C – Contiguous Memory AllocationDynamic Arrays in C – Runtime-Sized Arraysfree() in C – Releasing Dynamic Memorymalloc() in C – Dynamic Memory AllocationMemory Management Best Practices in Crealloc() in C – Resizing Dynamic MemoryBinary Files in C – fread and fwriteFile Handling in C – IntroductionFile Handling Projects in C – Student Records & Phone BookFile Modes in C – Complete Guidefopen() and fclose() in C – Opening and Closing FilesReading Files in C – fgetc, fgets, fscanf, freadWriting Files in C – fputc, fputs, fprintf, fwriteConditional Compilation in C – #ifdef, #ifndef, #if#define Macros in C – Constants and Macro FunctionsHeader Files in C – Creating Custom Headers#include Directive in C – File InclusionMacro Functions in C – Parameterized MacrosC Preprocessor – Overview and DirectivesGraphs in C – Adjacency Matrix, Adjacency List, BFS, and DFSHash Tables in C – Implementation, Collision Handling, and ChainingLinked List in C – Singly, Doubly, and Circular with ImplementationQueue in C – Linear, Circular, and Priority Queue ImplementationStack in C – Array and Linked List Implementation with ApplicationsTrees in C – Binary Search Tree Implementation with TraversalsC Programming Best Practices – Coding Standards, Safety, and PerformanceBit Fields in C – Definition, Use Cases, and Protocol HeadersC Standard Library Overview – All Headers and Common FunctionsCommand Line Arguments in C – argc and argv ExplainedDebugging Techniques in C – GDB, Valgrind, and SanitizersFunction Pointers in C – Complete Guide with ExamplesMemory Layout of a C Program – Text, Data, BSS, Heap, StackBank Management System in C – Complete Project with File StorageFile Encryption Tool in C – XOR Cipher ImplementationLibrary Management System in C – Complete Project with Source CodeMini Compiler in C – Lexer and Parser for Simple ExpressionsSnake Game in C – Console-Based Game with Source CodeStudent Management System in C – Complete Project with Source CodeC Programming Cheatsheet – Complete Quick Reference GuideTop 50 C Programming Interview Questions with Answers (2025)Memory Management Interview Questions in C with AnswersOutput Prediction Questions in C – What Will This Program Print?Pointer Interview Questions in C – Tricky Problems with AnswersCommon C Programming Errors and Solutions – Debugging GuideImportant C Programs – 50+ Frequently Asked Programs with SolutionsQuick Revision Notes for C Programming – Complete C in 10 MinutesRecommended C Programming Books – From Beginner to ExpertFormat Specifiers in C - Complete Referencegetchar() and putchar() in C Programminggets() and puts() in C ProgrammingC Input Output Programs and Examplesprintf() Function in C Programmingscanf() Function in C ProgrammingArrays of Structures in C – Managing CollectionsEnums in C – Enumerated Data TypesNested Structures in C – Struct Within StructPointers to Structures in C – Arrow OperatorStructures in C – User-Defined Data Typestypedef in C – Creating Type AliasesUnions in C – Shared Memory Data Types
Learn stack data structure in C with array-based and linked list implementations, push/pop operations, applications like expression evaluation, and interview questions.
A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. Think of it like a stack of plates – you can only add or remove from the top. Stacks are fundamental in computer science, used in function calls, expression evaluation, undo mechanisms, and backtracking algorithms.
Stack Operations
| Operation | Description | Time Complexity |
|---|---|---|
| Push | Add element to top | O(1) |
| Pop | Remove element from top | O(1) |
| Peek/Top | View top element without removing | O(1) |
| isEmpty | Check if stack is empty | O(1) |
| isFull | Check if stack is full (array only) | O(1) |
Stack Implementation Using Array
Example
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_SIZE 100
typedef struct {
int items[MAX_SIZE];
int top;
} Stack;
// Initialize stack
void initStack(Stack *s) {
s->top = -1;
}
// Check if stack is full
bool isFull(Stack *s) {
return s->top == MAX_SIZE - 1;
}
// Check if stack is empty
bool isEmpty(Stack *s) {
return s->top == -1;
}
// Push element onto stack
void push(Stack *s, int value) {
if (isFull(s)) {
printf("Stack Overflow! Cannot push %d\n", value);
return;
}
s->items[++(s->top)] = value;
}
// Pop element from stack
int pop(Stack *s) {
if (isEmpty(s)) {
printf("Stack Underflow! Cannot pop\n");
return -1;
}
return s->items[(s->top)--];
}
// Peek at top element
int peek(Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty\n");
return -1;
}
return s->items[s->top];
}
// Display stack
void display(Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty\n");
return;
}
printf("Stack (top to bottom): ");
for (int i = s->top; i >= 0; i--)
printf("%d ", s->items[i]);
printf("\n");
}
int main() {
Stack s;
initStack(&s);
push(&s, 10);
push(&s, 20);
push(&s, 30);
push(&s, 40);
display(&s);
printf("Peek: %d\n", peek(&s));
printf("Pop: %d\n", pop(&s));
printf("Pop: %d\n", pop(&s));
display(&s);
printf("Size: %d\n", s.top + 1);
return 0;
}
Output
Stack (top to bottom): 40 30 20 10 Peek: 40 Pop: 40 Pop: 30 Stack (top to bottom): 20 10 Size: 2
Stack Implementation Using Linked List
This implementation has no fixed size limit – it grows dynamically.
Example
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
typedef struct {
Node *top;
int size;
} Stack;
void initStack(Stack *s) {
s->top = NULL;
s->size = 0;
}
bool isEmpty(Stack *s) {
return s->top == NULL;
}
void push(Stack *s, int value) {
Node *newNode = (Node*)malloc(sizeof(Node));
if (!newNode) {
printf("Memory allocation failed\n");
return;
}
newNode->data = value;
newNode->next = s->top;
s->top = newNode;
s->size++;
}
int pop(Stack *s) {
if (isEmpty(s)) {
printf("Stack Underflow!\n");
return -1;
}
Node *temp = s->top;
int value = temp->data;
s->top = temp->next;
free(temp);
s->size--;
return value;
}
int peek(Stack *s) {
if (isEmpty(s)) return -1;
return s->top->data;
}
void display(Stack *s) {
Node *temp = s->top;
printf("Stack: ");
while (temp) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
void freeStack(Stack *s) {
while (!isEmpty(s)) pop(s);
}
int main() {
Stack s;
initStack(&s);
push(&s, 100);
push(&s, 200);
push(&s, 300);
display(&s);
printf("Size: %d\n", s.size);
printf("Pop: %d\n", pop(&s));
display(&s);
freeStack(&s);
return 0;
}
Output
Stack: 300 200 100 Size: 3 Pop: 300 Stack: 200 100
Application: Balanced Parentheses Checker
Example
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#define MAX 100
typedef struct {
char items[MAX];
int top;
} CharStack;
void init(CharStack *s) { s->top = -1; }
bool empty(CharStack *s) { return s->top == -1; }
void push(CharStack *s, char c) { s->items[++(s->top)] = c; }
char pop(CharStack *s) { return empty(s) ? '\0' : s->items[(s->top)--]; }
bool isMatchingPair(char open, char close) {
return (open == '(' && close == ')') ||
(open == '{' && close == '}') ||
(open == '[' && close == ']');
}
bool isBalanced(const char *expr) {
CharStack s;
init(&s);
for (int i = 0; expr[i]; i++) {
if (expr[i] == '(' || expr[i] == '{' || expr[i] == '[') {
push(&s, expr[i]);
} else if (expr[i] == ')' || expr[i] == '}' || expr[i] == ']') {
if (empty(&s)) return false;
char top = pop(&s);
if (!isMatchingPair(top, expr[i])) return false;
}
}
return empty(&s);
}
int main() {
const char *tests[] = {
"{[()]}",
"((()))",
"{[(])}",
"((())",
"hello(world)[test]{done}"
};
for (int i = 0; i < 5; i++) {
printf("\"%s\" -> %s\n", tests[i],
isBalanced(tests[i]) ? "Balanced" : "Not Balanced");
}
return 0;
}
Output
"{[()]}" -> Balanced
"((()))" -> Balanced
"{[(])}" -> Not Balanced
"((())" -> Not Balanced
"hello(world)[test]{done}" -> BalancedApplication: Infix to Postfix Conversion
Example
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define MAX 100
char stack[MAX];
int top = -1;
void push(char c) { stack[++top] = c; }
char pop() { return stack[top--]; }
char peek() { return stack[top]; }
int empty() { return top == -1; }
int precedence(char op) {
switch (op) {
case '+': case '-': return 1;
case '*': case '/': return 2;
case '^': return 3;
default: return 0;
}
}
void infixToPostfix(const char *infix, char *postfix) {
int j = 0;
top = -1;
for (int i = 0; infix[i]; i++) {
char c = infix[i];
if (isalnum(c)) {
postfix[j++] = c;
} else if (c == '(') {
push(c);
} else if (c == ')') {
while (!empty() && peek() != '(')
postfix[j++] = pop();
if (!empty()) pop(); // Remove '('
} else { // Operator
while (!empty() && precedence(peek()) >= precedence(c))
postfix[j++] = pop();
push(c);
}
}
while (!empty())
postfix[j++] = pop();
postfix[j] = '\0';
}
int main() {
char postfix[MAX];
infixToPostfix("A+B*C", postfix);
printf("A+B*C -> %s\n", postfix);
infixToPostfix("(A+B)*C", postfix);
printf("(A+B)*C -> %s\n", postfix);
infixToPostfix("A+B*C-D/E", postfix);
printf("A+B*C-D/E -> %s\n", postfix);
return 0;
}
Output
A+B*C -> ABC*+ (A+B)*C -> AB+C* A+B*C-D/E -> ABC*+DE/-
Application: Postfix Expression Evaluation
Example
#include <stdio.h>
#include <ctype.h>
int stack[100];
int top = -1;
void push(int val) { stack[++top] = val; }
int pop() { return stack[top--]; }
int evaluatePostfix(const char *expr) {
top = -1;
for (int i = 0; expr[i]; i++) {
if (isdigit(expr[i])) {
push(expr[i] - '0');
} else {
int b = pop();
int a = pop();
switch (expr[i]) {
case '+': push(a + b); break;
case '-': push(a - b); break;
case '*': push(a * b); break;
case '/': push(a / b); break;
}
}
}
return pop();
}
int main() {
printf("23*5+ = %d\n", evaluatePostfix("23*5+"));
printf("92-3*1+ = %d\n", evaluatePostfix("92-3*1+"));
printf("53+82-* = %d\n", evaluatePostfix("53+82-*"));
return 0;
}
Output
23*5+ = 11 92-3*1+ = 22 53+82-* = 48
Comparison: Array vs Linked List Implementation
| Aspect | Array Stack | Linked List Stack |
|---|---|---|
| Size | Fixed (MAX_SIZE) | Dynamic (unlimited) |
| Memory | Pre-allocated | On-demand |
| Overflow | Possible | Only when memory exhausted |
| Cache performance | Better (contiguous) | Worse (scattered) |
| Extra memory | None | Pointer per node |
| Implementation | Simpler | Slightly complex |
Interview Questions on Stacks
Q1: How do you implement two stacks in one array? Start one stack from the beginning (grows right) and another from the end (grows left). They overflow only when the tops meet.
Q2: How to find the minimum element in O(1) time? Maintain an auxiliary stack that tracks the minimum. Push the new minimum alongside every push. The top of the aux stack always has the current minimum.
Q3: How do you sort a stack using only another stack? Pop from original, compare with top of temp stack. Pop elements from temp back to original until you find the right position, then push. Repeat until original is empty.
Q4: What's the difference between stack and recursion? Recursion uses the system call stack implicitly. Every recursive algorithm can be converted to an iterative one using an explicit stack.
Q5: How are stacks used in function calls? Each function call pushes a stack frame containing local variables, parameters, and return address. When the function returns, its frame is popped, restoring the caller's context.
Summary
Stacks are one of the most versatile data structures in computer science. The LIFO principle makes them perfect for managing function calls, evaluating expressions, parsing syntax, implementing undo functionality, and solving backtracking problems. Array-based stacks are simpler and cache-friendly but size-limited; linked list stacks offer dynamic sizing at the cost of memory overhead. Master both implementations and their applications for coding interviews and real-world projects.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Stack in C – Array and Linked List Implementation with Applications.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this C Programming topic.
Search Terms
c-programming, c programming, programming, data, structures, stack, stack in c – array and linked list implementation with applications
Related C Programming Topics
Continue learning this concept
Data Structures In CGraphs in C – Adjacency Matrix, Adjacency List, BFS, and DFSLearn graph data structure in C with adjacency matrix and adjacency list representations, BFS and DFS traversal algorithms, and complete implementation examples.Data Structures In CHash Tables in C – Implementation, Collision Handling, and ChainingLearn hash table implementation in C with hash functions, collision resolution using chaining and open addressing, performance analysis, and practical examples.Data Structures In CLinked List in C – Singly, Doubly, and Circular with ImplementationComplete guide to implementing linked lists in C covering singly linked list, doubly linked list, circular linked list, all operations with code examples and output.Data Structures In CQueue in C – Linear, Circular, and Priority Queue ImplementationLearn queue data structure in C with linear queue, circular queue, and priority queue implementations using arrays and linked lists with complete code examples.Data Structures In CTrees in C – Binary Search Tree Implementation with TraversalsLearn tree data structure in C with BST implementation covering insertion, deletion, searching, inorder/preorder/postorder traversals, and tree operations.BasicsComments in C ProgrammingLearn about comments in C — single-line comments, multi-line comments, best practices, nested comments, and when to use comments effectively in your code.