Stack: Operations, Array and Linked Implementation, Infix to Postfix

Stack as an ADT

A stack is an ordered list in which all insertions and deletions happen at one end, called the top. The last element pushed is the first one popped: LIFO (Last In, First Out), like a pile of plates.

Operations

All of these take O(1) time.

Array implementation

#define MAX 100
int stack[MAX];
int top = -1;                    /* -1 means empty */

void push(int x) {
    if (top == MAX - 1) { printf("Stack overflow\n"); return; }
    stack[++top] = x;
}

int pop(void) {
    if (top == -1) { printf("Stack underflow\n"); return -1; }
    return stack[top--];
}

int peek(void) { return top == -1 ? -1 : stack[top]; }

Algorithm PUSH

1. If top = MAX − 1, print "overflow" and exit.
2. top = top + 1.
3. stack[top] = item.

Algorithm POP

1. If top = −1, print "underflow" and exit.
2. item = stack[top].
3. top = top − 1 and return item.

Linked list implementation

The head of the list is the top. Push inserts at the head and pop deletes the head. There is no overflow until memory runs out.

struct node { int data; struct node *next; };
struct node *top = NULL;

void push(int x) {
    struct node *n = malloc(sizeof *n);
    n->data = x;
    n->next = top;
    top = n;
}

int pop(void) {
    if (top == NULL) { printf("Underflow\n"); return -1; }
    struct node *t = top;
    int x = t->data;
    top = t->next;
    free(t);
    return x;
}

Infix, prefix and postfix

• Infix: operator between operands: A + B
• Prefix (Polish): operator before operands: + A B
• Postfix (Reverse Polish): operator after operands: A B +

Postfix and prefix need no parentheses and no precedence rules, so computers evaluate them easily with a stack.

Operator precedence (highest first): ^, then * /, then + −. ^ is right-associative; the others are left-associative.

Infix to postfix algorithm

Scan the infix expression from left to right:

1. Operand: add it to the output.
2. (: push it.
3. ): pop to the output until ( is found; discard both parentheses.
4. Operator o: while the top of the stack is an operator with higher precedence than o, or equal precedence and o is left-associative, pop it to the output. Then push o.
5. At the end, pop all remaining operators to the output.

Example: A + B * (C - D) / E

Postfix: A B C D - * E / +

Evaluating postfix

Push operands. For an operator, pop B (the top) then A, compute A op B, and push the result.

5 3 2 * + 9 - → push 5, 3, 2; * gives 3 × 2 = 6; + gives 5 + 6 = 11; push 9; − gives 11 − 9 = 2.

Applications of stack

• Function calls and recursion (the call stack)
• Expression conversion and evaluation
• Checking balanced parentheses: {[()]}
• Undo/redo, browser back button
• Backtracking (maze solving, depth-first search)
• Reversing a string

Exam tip

"Convert to postfix" and "evaluate the postfix expression" appear in almost every paper. Always show the table with the symbol, stack and output columns: most of the marks are for the steps.