Implement Stack Using Array

Table of Contents
1. Stack Using Array
2. Stack Operations using Array
3. Implementation of Stack using Array (C)
4. Example trace
5. Time and Space Complexity
6. Advantages and Disadvantages (Array-based stack)
7. Applications of Stack
8. Output
View more

Stack Using Array

A stack is an abstract data type that stores elements in a Last-In, First-Out (LIFO) order. An array can be used to implement a stack when the maximum number of elements is known in advance. In the array implementation a single one-dimensional array holds the stack elements and an integer variable top keeps track of the index of the current top element. Conventionally, top is initialised to -1 to indicate an empty stack. When an element is pushed, top is incremented and the element is stored at array index top. When an element is popped, the element at index top is removed and top is decremented.

Stack Operations using Array

Before implementing the operations, follow these steps to define and create an empty stack in C:

1. Include required header files and define a constant SIZE for the maximum capacity of the stack.
2. Declare function prototypes for stack operations (for example: push, pop, peek, isEmpty, isFull, display).
3. Create a one-dimensional array of fixed size: int stack[SIZE];
4. Define an integer variable top and initialise it with -1: int top = -1;
5. In main, present a menu or test routine that calls the stack functions to perform operations chosen by the user or to run sample tests.

push(value) - Insert element on the stack

push() inserts an element at the top of the stack. The new element is always stored at index top after incrementing top.

1. Check whether the stack is FULL by testing (top == SIZE - 1).
2. If it is FULL, report overflow: "Stack is FULL - insertion not possible" and terminate the function.
3. If it is NOT FULL, increment top by one and assign the value to stack[top].

pop() - Remove element from the stack

pop() removes and returns the element at the top of the stack. The element is always removed from the current top position.

1. Check whether the stack is EMPTY by testing (top == -1).
2. If it is EMPTY, report underflow: "Stack is EMPTY - deletion not possible" and terminate the function or return an error code.
3. If it is NOT EMPTY, retrieve the value at stack[top] and decrement top by one.

display() - Display elements of the stack

The stack elements are displayed starting from the top down to the bottom (index 0).

1. Check whether the stack is EMPTY by testing (top == -1).
2. If it is EMPTY, display "Stack is EMPTY" and terminate the function.
3. If it is NOT EMPTY, iterate with a variable i initialised to top and print stack[i], decrementing i each time.
4. Repeat until i >= 0.

peek(), isEmpty(), isFull()

It is often useful to have helper functions:

• peek() returns the element at top without removing it. If stack is empty, report or return an error value.
• isEmpty() returns true when top == -1.
• isFull() returns true when top == SIZE - 1.

Implementation of Stack using Array (C)

Note: The example in some older tutorials uses <conio.h> and clrscr(). <conio.h> is non-standard and compiler-specific; the code below uses standard headers <stdio.h> and <stdlib.h> for portability.

#include <stdio.h> #include <stdlib.h> #define SIZE 10 int stack[SIZE]; int top = -1; /* Function prototypes */ void push(int value); int pop(void); int peek(void); int isEmpty(void); int isFull(void); void display(void); int main(void) { int choice, value, deleted; while (1) { printf("

* MENU *
"); printf("1. Push
2. Pop
3. Peek (Top element)
4. Display
5. Exit
"); printf("Enter your choice: "); if (scanf("%d", &choice) != 1) { /* invalid input: clear input and continue */ int ch; while ((ch = getchar()) != EOF && ch != '
'); printf("Invalid input. Try again.
"); continue; } switch (choice) { case 1: printf("Enter the value to insert: "); if (scanf("%d", &value) == 1) { push(value); } else { int ch; while ((ch = getchar()) != EOF && ch != '
'); printf("Invalid value.
"); } break; case 2: deleted = pop(); if (deleted != INT_MIN) { printf("Deleted: %d
", deleted); } break; case 3: if (!isEmpty()) { printf("Top element: %d
", peek()); } else { printf("Stack is EMPTY
"); } break; case 4: display(); break; case 5: exit(0); default: printf("Wrong selection! Try again!
"); } } return 0; } void push(int value) { if (isFull()) { printf("Stack is FULL!!! Insertion is not possible!!!
"); return; } top++; stack[top] = value; printf("Insertion success: %d
", value); } int pop(void) { if (isEmpty()) { printf("Stack is EMPTY!!! Deletion is not possible!!!
"); return INT_MIN; /* sentinel for error */ } int value = stack[top]; top--; return value; } int peek(void) { if (isEmpty()) { return INT_MIN; } return stack[top]; } int isEmpty(void) { return (top == -1); } int isFull(void) { return (top == SIZE - 1); } void display(void) { if (isEmpty()) { printf("Stack is EMPTY!!!
"); return; } printf("Stack elements (top to bottom):
"); for (int i = top; i >= 0; i--) { printf("%d
", stack[i]); } }

Example trace

Suppose we perform the operations: push(10), push(20), push(30), pop(), display(). The stack evolves as follows:

• Initial: top = -1, stack = [ ]
• push(10): top = 0, stack[0] = 10
• push(20): top = 1, stack[1] = 20
• push(30): top = 2, stack[2] = 30
• pop(): returns 30, top becomes 1
• display(): shows 20 (top), then 10

Time and Space Complexity

• push(): O(1) time
• pop(): O(1) time
• peek(): O(1) time
• display(): O(n) time in the number of elements currently in the stack
• Space complexity: O(SIZE) for the array; array-based stack uses a fixed contiguous block of memory.

Advantages and Disadvantages (Array-based stack)

• Advantage: Simple and fast - push and pop are constant-time operations and use contiguous memory which offers good cache behaviour.
• Disadvantage: Fixed maximum size; once the array is full no more elements can be pushed unless the array is reallocated or a dynamic structure is used.
• Alternative: A linked-list implementation of stack supports dynamic growth limited only by available memory.

Applications of Stack

• Function-call management and recursion (call stack).
• Expression evaluation and syntax parsing (infix to postfix/prefix conversions, evaluating postfix expressions).
• Undo mechanisms in editors and backtracking algorithms.
• Balancing symbols (parentheses matching) and depth-first search implementations.

Output