PadhaikoAll subjects

Definition of stack and its operations · Array implementation of…

Data Structure and Algorithms (ENCT 252)

Open in the Padhaiko app

2.1 Definition of stack and its operations

Definition

Stack and LIFO Principle

A stack is a linear data structure in which all insertions and deletions are restricted to a single end called the top. Because the most recently inserted element is always the first to be removed, a stack follows the Last In, First Out (LIFO) principle.

Think of a stack of plates: you place a new plate on top and lift the top plate off first.

Conceptual Stack Diagram (LIFO Access)Text
          +-------+
  top --> |   D   |  <-- Push / Pop happen only here
          +-------+
          |   C   |
          +-------+
          |   B   |
          +-------+
          |   A   |  <-- Bottom (inserted first, removed last)
          +-------+

Stack ADT Specification

As an Abstract Data Type (ADT), a stack is defined by a collection of homogeneous elements and five core operations:

Core Operations of the Stack ADT
OperationBehaviorCondition / Error StateTime Complexity
push(S, x)Inserts element x at the top of stack SStack Overflow if the stack is full
pop(S)Removes and returns the top element of SStack Underflow if the stack is empty
peek(S) / top(S)Returns the top element without removing itError if the stack is empty
isEmpty(S)Returns true (1) if S has no elements, else false (0)Always valid
isFull(S)Returns true (1) if S has reached fixed capacity, else falseRelevant for bounded/array stacks

2.2 Array implementation of stack ADT

In a static (array-based) implementation, stack elements are stored in a contiguous one-dimensional array items[MAX] alongside an integer index top that tracks the topmost filled slot.

Array Implementation of Stack ADT in CC
#include <stdio.h>
#define MAX 100

typedef struct {
    int items[MAX];
    int top;
} Stack;

void initStack(Stack *s) {
    s->top = -1;
}

int isEmpty(const Stack *s) {
    return s->top == -1;
}

int isFull(const Stack *s) {
    return s->top == MAX - 1;
}

void push(Stack *s, int element) {
    if (isFull(s)) {
        printf("Stack Overflow\n");
        return;
    }
    s->items[++(s->top)] = element;
}

int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack Underflow\n");
        return -1;
    }
    return s->items[(s->top)--];
}

int peek(const Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty\n");
        return -1;
    }
    return s->items[s->top];
}

void display(const Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty\n");
        return;
    }
    for (int i = s->top; i >= 0; i--) {
        printf("%d\n", s->items[i]);
    }
}

2.3 Stack applications

One of the classic applications of stacks in compilers and calculators is converting and evaluating arithmetic expressions without ambiguity over operator precedence or parentheses.

Comparison of Infix, Prefix, and Postfix Notations
NotationOperator PositionParentheses Needed?Example
InfixBetween operands (A + B)Yes(A + B) * (C - D)
Prefix (Polish)Before operands (+ A B)No* + A B - C D
Postfix (Reverse Polish / RPN)After operands (A B +)NoA B + C D - *
Standard Operator Precedence and Associativity
Precedence LevelOperator(s)MeaningAssociativity
Highest ()^ExponentiationRight-to-Left
Middle ()*, /Multiplication, DivisionLeft-to-Right
Lowest ()+, -Addition, SubtractionLeft-to-Right

2.3.1 Expression conversion: Infix to postfix and prefix expression

Infix to Postfix Conversion

To convert a valid infix expression to postfix using an operator stack:

  1. Initialize an empty operator stack and an empty output string postfix.
  2. Scan the infix expression from left to right:
    • Operand: Append directly to postfix.
    • Left parenthesis (: Push onto the operator stack.
    • Right parenthesis ): Pop operators from the stack and append to postfix until ( is reached; pop and discard (.
    • Operator op: While the stack is non-empty, the top is not (, and the top operator has higher precedence than op—or equal precedence when op is left-associative (+, -, *, /)—pop the top operator and append it to postfix. Then push op onto the stack.
  3. After scanning all symbols, pop all remaining operators from the stack and append them to postfix.
Infix to Postfix Conversion in CC
#include <stdio.h>
#include <ctype.h>

int precedence(char op) {
    if (op == '^' || op == '$') return 3;
    if (op == '*' || op == '/') return 2;
    if (op == '+' || op == '-') return 1;
    return 0;
}

int isRightAssociative(char op) {
    return (op == '^' || op == '$');
}

void infixToPostfix(const char *infix, char *postfix) {
    char opstack[100];
    int top = -1, k = 0;

    for (int i = 0; infix[i] != '\0'; i++) {
        char ch = infix[i];
        if (ch == ' ' || ch == '\t') continue;

        if (isalnum((unsigned char)ch)) {
            postfix[k++] = ch;
        } else if (ch == '(') {
            opstack[++top] = ch;
        } else if (ch == ')') {
            while (top >= 0 && opstack[top] != '(') {
                postfix[k++] = opstack[top--];
            }
            if (top >= 0 && opstack[top] == '(') top--;
        } else {
            while (top >= 0 && opstack[top] != '(' &&
                   (precedence(opstack[top]) > precedence(ch) ||
                    (precedence(opstack[top]) == precedence(ch) && !isRightAssociative(ch)))) {
                postfix[k++] = opstack[top--];
            }
            opstack[++top] = ch;
        }
    }
    while (top >= 0) {
        postfix[k++] = opstack[top--];
    }
    postfix[k] = '\0';
}

Infix to Prefix Conversion

To convert an infix expression to prefix using the stack-based reversal method:

  1. Reverse the infix expression string and swap every ( with ) (and ) with ().
  2. Convert this reversed infix expression to a postfix-like string using an operator stack (with the associativity rule noted below).
  3. Reverse the resulting string to obtain the final prefix expression.

2.3.2 Expression evaluation: Infix and postfix expression evaluation

Postfix Expression Evaluation

Postfix expressions are evaluated in a single left-to-right pass using an operand stack:

  1. Initialize an empty operand stack.
  2. Scan each token of the postfix expression from left to right:
    • Operand: Push its numeric value onto the stack.
    • Binary operator op: Pop the top element as op2 (right operand), then pop the next element as op1 (left operand). Compute result = op1 op op2 and push result onto the stack.
  3. At the end of the expression, the single value remaining on top of the stack is the final answer.
Postfix Expression Evaluation in C (Single-Digit Tokens)C
#include <stdio.h>
#include <ctype.h>
#include <math.h>

int evalPostfix(const char *postfix) {
    int stack[100], top = -1;

    for (int i = 0; postfix[i] != '\0'; i++) {
        char ch = postfix[i];
        if (ch == ' ') continue;

        if (isdigit((unsigned char)ch)) {
            stack[++top] = ch - '0';
        } else {
            int op2 = stack[top--];
            int op1 = stack[top--];
            switch (ch) {
                case '+': stack[++top] = op1 + op2; break;
                case '-': stack[++top] = op1 - op2; break;
                case '*': stack[++top] = op1 * op2; break;
                case '/': stack[++top] = op1 / op2; break;
                case '^':
                case '$': stack[++top] = (int)pow(op1, op2); break;
            }
        }
    }
    return stack[top];
}

Direct Infix Expression Evaluation (Two-Stack Method)

An infix expression can be evaluated directly without building an explicit postfix string by maintaining two stacks: a value (operand) stack and an operator stack.

Definition

Two-Stack Direct Infix Evaluation Algorithm

Scan tokens from left to right:

  1. Number (operand): Push onto the value stack.
  2. (: Push onto the operator stack.
  3. ): While the top of the operator stack is not (, pop one operator op, pop op2 then op1 from the value stack, and push op1 op op2 back onto the value stack. Pop and discard (.
  4. Operator curr: While the operator stack is non-empty, its top is not (, and the top operator has higher precedence (or equal precedence if curr is left-associative), pop and apply that top operator using the top two values on the value stack. Then push curr onto the operator stack.
  5. End of input: Apply all remaining operators on the operator stack; the single value left on the value stack is the result.

Worked Examples

Example 1

1

Trace the state of an array-based stack S with capacity MAX = 3 (initially top = -1) for the sequence of operations: push(10), push(20), pop(), push(30), push(40), push(50), peek(), pop().

Executing each operation sequentially: Track top, the active array slice items[0..top], and any return value or condition:

Array Stack Operation Trace (MAX = 3)
OperationCondition Checktop AfterStack Contents (bottom -> top)Output / Status
InitialisEmpty = true-1[]Empty stack
push(10)top < 2 (not full)0[10]Inserted 10
push(20)top < 2 (not full)1[10, 20]Inserted 20
pop()top >= 0 (not empty)0[10]Returns 20
push(30)top < 2 (not full)1[10, 30]Inserted 30
push(40)top < 2 (not full)2[10, 30, 40]Inserted 40 (now full)
push(50)top == MAX - 12[10, 30, 40]Stack Overflow (ignored)
peek()top >= 02[10, 30, 40]Returns 40 (top unchanged)
pop()top >= 01[10, 30]Returns 40
Answer:

After all operations complete, top = 1 and the stack contains [10, 30] (30 at the top). The push(50) call triggers Stack Overflow.

Example 2

2

Convert the infix expression A + (B * C - (D / E - F) * G) * H to postfix notation, showing the operator stack and postfix output after every symbol.

Scanning left-to-right with precedence (*,/) > (+,-): Apply the infix-to-postfix algorithm, popping equal-or-higher precedence left-associative operators when a new operator arrives and popping back to ( on each ):

Infix to Postfix Trace for A + (B * C - (D / E - F) * G) * H
Scanned SymbolAction TakenOperator StackPostfix Output
AAppend operand(empty)A
+Push ++A
(Push (+(A
BAppend operand+(AB
*Push *+(*AB
CAppend operand+(*ABC
-Pop * (higher prec), push -+(-ABC*
(Push (+(-(ABC*
DAppend operand+(-(ABC*D
/Push /+(-(/ABC*D
EAppend operand+(-(/ABC*DE
-Pop / (higher prec), push -+(-(-ABC*DE/
FAppend operand+(-(-ABC*DE/F
)Pop -, discard (+(-ABC*DE/F-
*Push * (higher than -)+(-*ABC*DE/F-
GAppend operand+(-*ABC*DE/F-G
)Pop *, pop -, discard (+ABC*DE/F-G*-
*Push * (higher than +)+*ABC*DE/F-G*-
HAppend operand+*ABC*DE/F-G*-H
EndPop remaining *, +(empty)ABC*DE/F-G*-H*+
Answer:

The equivalent postfix expression is ABC*DE/F-G*-H*+.

Example 3

3

Convert the infix expression (A + B) * C - (D - E) ^ (F + G) into prefix notation using the stack-based reversal method, where ^ denotes exponentiation.

Reversing the infix expression and swapping parentheses: Original: (A + B) * C - (D - E) ^ (F + G) Reversed with ( and ) swapped: (G + F) ^ (E - D) - C * (B + A)

Converting the reversed expression with the stack:

Stack Trace on Reversed Infix (G + F) ^ (E - D) - C * (B + A)
SymbolOperator StackOutput Buffer
((
G(G
+(+G
F(+GF
)(empty)GF+
^^GF+
(^(GF+
E^(GF+E
-^(-GF+E
D^(-GF+ED
)^GF+ED-
-- (popped ^)GF+ED-^
C-GF+ED-^C
*-*GF+ED-^C
(-*(GF+ED-^C
B-*(GF+ED-^CB
+-*(+GF+ED-^CB
A-*(+GF+ED-^CBA
)-*GF+ED-^CBA+
End(empty)GF+ED-^CBA+*-

Reversing the output buffer: Reversing GF+ED-^CBA+*- character by character produces -*+ABC^-DE+FG.

Answer:

The equivalent prefix expression is -*+ABC^-DE+FG.

Example 4

4

Evaluate the postfix expression 6 2 3 + - 3 8 2 / + * 2 ^ 3 + (where ^ is exponentiation) using an operand stack, showing the stack after every token.

Scanning tokens left-to-right and evaluating binary operators (op1 op op2): Remember that the first popped item is op2 (right operand) and the second popped item is op1 (left operand).

Postfix Evaluation Stack Trace
TokenActionOperand Stack (bottom -> top)
6Push 6[6]
2Push 2[6, 2]
3Push 3[6, 2, 3]
+Pop 3, 2; push 2 + 3 = 5[6, 5]
-Pop 5, 6; push 6 - 5 = 1[1]
3Push 3[1, 3]
8Push 8[1, 3, 8]
2Push 2[1, 3, 8, 2]
/Pop 2, 8; push 8 / 2 = 4[1, 3, 4]
+Pop 4, 3; push 3 + 4 = 7[1, 7]
*Pop 7, 1; push 1 * 7 = 7[7]
2Push 2[7, 2]
^Pop 2, 7; push 7^2 = 49[49]
3Push 3[49, 3]
+Pop 3, 49; push 49 + 3 = 52[52]
Answer:

The postfix expression evaluates to .


Exercises

Exercises

Question 1

Define Stack as an ADT. Explain Stack Overflow and Stack Underflow, and write C functions for push, pop, and isEmpty using an array representation.

Stack ADT definition: A Stack ADT is a LIFO linear collection supporting push(x), pop(), peek(), isEmpty(), and isFull(), where insertions and deletions occur exclusively at one end (top).

Overflow and underflow:

  • Stack Overflow: Attempting to push onto a fixed-capacity stack that is already full (top == MAX - 1).
  • Stack Underflow: Attempting to pop or peek from an empty stack (top == -1).

Array-based C functions:

Array Stack OperationsC
#define MAX 50
typedef struct {
    int data[MAX];
    int top;
} Stack;

int isEmpty(const Stack *s) { return s->top == -1; }

void push(Stack *s, int x) {
    if (s->top == MAX - 1) { printf("Overflow\n"); return; }
    s->data[++(s->top)] = x;
}

int pop(Stack *s) {
    if (isEmpty(s)) { printf("Underflow\n"); return -1; }
    return s->data[(s->top)--];
}
Answer:

A Stack is a LIFO ADT; Overflow occurs on push when top == MAX - 1, and Underflow occurs on pop when top == -1, implemented in per operation using an array and index top.

Question 2

Convert the infix expression A + B - (C * D / E + F) - G * H into postfix expression showing the operator stack status at each symbol.

Tracing the operator stack left-to-right:

Infix to Postfix Trace
SymbolStackPostfix Output
AA
++A
B+AB
-- (pop +)AB+
(-(AB+
C-(AB+C
*-(*AB+C
D-(*AB+CD
/-(/ (pop *)AB+CD*
E-(/AB+CD*E
+-(+ (pop /)AB+CD*E/
F-(+AB+CD*E/F
)- (pop +, discard ()AB+CD*E/F+
-- (pop -)AB+CD*E/F+-
G-AB+CD*E/F+-G
*-*AB+CD*E/F+-G
H-*AB+CD*E/F+-GH
End(empty)AB+CD*E/F+-GH*-
Answer:

The postfix expression is AB+CD*E/F+-GH*-.

Question 3

Convert the infix expression A * (B + C) - (D / E) + F into both postfix and prefix expressions, showing the stack trace for each conversion.

Infix to Postfix trace: Scanning A * (B + C) - (D / E) + F left-to-right:

Postfix Conversion Trace
SymbolStackPostfix Output
AA
**A
(*(A
B*(AB
+*(+AB
C*(+ABC
)*ABC+
-- (pop *)ABC+*
(-(ABC+*
D-(ABC+*D
/-(/ABC+*D
E-(/ABC+*DE
)- (pop /)ABC+*DE/
++ (pop -)ABC+*DE/-
F+ABC+*DE/-F
End(empty)ABC+*DE/-F+

Infix to Prefix trace (reverse, swap parentheses, convert with strict-higher popping for left-assoc ops, then reverse): Reversed with swapped parentheses: F + (E / D) - (C + B) * A.

Reversed Scan Trace for Prefix
SymbolStackBuffer
FF
++F
(+(F
E+(FE
/+( /FE
D+(/FED
)+FED/
-+- (do not pop equal-prec +)FED/
(+-(FED/
C+-(FED/C
++-(+FED/C
B+-(+FED/CB
)+-FED/CB+
*+-*FED/CB+
A+-*FED/CB+A
End(empty)FED/CB+A*-+

Reversing FED/CB+A*-+ gives +-*A+BC/DEF.

Answer:
  • Postfix: ABC+*DE/-F+
  • Prefix: +-*A+BC/DEF
Question 4

Evaluate the postfix expression A B + C * D E F G - * + / using an operand stack for .

Substituting values and tracing the operand stack: The numeric postfix expression is 2 3 + 10 * 5 2 4 6 - * + /.

Operand Stack Trace
TokenOperation (op1 op op2)Operand Stack
2Push 2[2]
3Push 3[2, 3]
+2 + 3 = 5[5]
10Push 10[5, 10]
*5 * 10 = 50[50]
5Push 5[50, 5]
2Push 2[50, 5, 2]
4Push 4[50, 5, 2, 4]
6Push 6[50, 5, 2, 4, 6]
-4 - 6 = -2[50, 5, 2, -2]
*2 * (-2) = -4[50, 5, -4]
+5 + (-4) = 1[50, 1]
/50 / 1 = 50[50]
Answer:

The postfix expression evaluates to .

Question 5

Evaluate the infix expression 10 + 5 - (4 * 6 / 3 + 8) - 2 * 1 directly using the two-stack infix evaluation algorithm (value stack and operator stack).

Tracing the Value Stack and Operator Stack token-by-token:

Two-Stack Direct Infix Evaluation Trace
TokenActionValue StackOperator Stack
10Push value 10[10]
+Push +[10]+
5Push value 5[10, 5]+
-Pop + (), push -[15]-
(Push ([15]-(
4Push 4[15, 4]-(
*Push *[15, 4]-(*
6Push 6[15, 4, 6]-(*
/Pop * (), push /[15, 24]-(/
3Push 3[15, 24, 3]-(/
+Pop / (), push +[15, 8]-(+
8Push 8[15, 8, 8]-(+
)Pop + (), discard ([15, 16]-
-Pop - (), push -[-1]-
2Push 2[-1, 2]-
*Push * (higher than -)[-1, 2]-*
1Push 1[-1, 2, 1]-*
EndPop * (), pop - ()[-3](empty)
Answer:

The infix expression evaluates directly to .

Question 6

Trace the evaluation of the postfix expression 4 6 4 + * 8 / using an operand stack.

Scanning tokens left-to-right:

Postfix Evaluation Trace for 4 6 4 + * 8 /
TokenActionOperand Stack
4Push 4[4]
6Push 6[4, 6]
4Push 4[4, 6, 4]
+Pop 4, 6; push 6 + 4 = 10[4, 10]
*Pop 10, 4; push 4 * 10 = 40[40]
8Push 8[40, 8]
/Pop 8, 40; push 40 / 8 = 5[5]
Answer:

The postfix expression 4 6 4 + * 8 / evaluates to .

Past exam questions for Data Structure and Algorithms

← IntroductionRecursion →