Stack

A stack is a restricted linear list in which insertion and deletion are allowed only at one end, and which obeys the last in, first out (LIFO) principle. The stack underlies recursion, function calls, expression evaluation and many other algorithms, and it is a high-frequency topic in all kinds of examinations. After reading this chapter you will be able to understand the definition, the characteristics and the basic operations of a stack, master the implementation and the complexity of pushing, popping and reading the top of a sequential stack, master the implementation and the characteristics of a linked stack, master the classic applications such as bracket matching and expression evaluation, and judge whether a given pop sequence is legal.

Questions This Chapter Answers

How can the last in, first out property be used to solve problems? This chapter revolves around the definition of the stack, the two storage implementations (the sequential stack and the linked stack) and the classic applications (bracket matching, expression evaluation and so on), so that you can understand why a stack is a structure whose operations are restricted yet whose uses are extremely broad.

Basic route: basic concepts → sequential stack → linked stack; master the definition of the stack and its two implementations first.

Advanced route: classic applications → summary; see the practical value of the stack through bracket matching and expression evaluation.

Basic Concepts

Characteristics

• Last in, first out (LIFO): the element that was pushed last is popped first
• Restricted operations: elements can be inserted and deleted only at the top, not at arbitrary positions as in a general linear list
• Fixed bottom: the bottom of the stack never moves, while the top changes dynamically with every operation

Basic Operations

Exercises

Exercise 1

The characteristic of a stack is ( )

A. First in, first out B. Last in, first out C. Random in, random out D. Operations allowed only at both ends

Exercise 2

Suppose the input sequence of a stack is 1, 2, 3. After a series of push and pop operations, which of the following pop sequences cannot be produced? ( )

A. 3, 2, 1 B. 2, 1, 3 C. 3, 1, 2 D. 1, 2, 3

Sequential Storage

A sequential stack is implemented with an array, and the top pointer top points at the top element, or at the position just after the top element.

#define MaxSize 100
typedef struct {
    int data[MaxSize];
    int top;  // top pointer, initially -1, pointing at the top element
} SqStack;

Push

bool Push(SqStack &S, int x) {
    if (S.top == MaxSize - 1) return false;  // the stack is full
    S.data[++S.top] = x;  // increment first, then push
    return true;
}

Pop

bool Pop(SqStack &S, int &x) {
    if (S.top == -1) return false;  // the stack is empty
    x = S.data[S.top--];  // pop first, then decrement
    return true;
}

Read the Top Element

bool GetTop(SqStack S, int &x) {
    if (S.top == -1) return false;
    x = S.data[S.top];
    return true;
}

Time complexity: push, pop and reading the top element are all $O(1)$.

Shared Stack

Two stacks share the same array space and grow from the two ends towards the middle, which makes full use of the space and reduces the chance of either stack becoming full.

typedef struct {
    int data[MaxSize];
    int top0;  // top of stack 0, initially -1, grows to the right
    int top1;  // top of stack 1, initially MaxSize, grows to the left
} ShareStack;
// the stacks are full when: top0 + 1 == top1

Linked Storage

A linked stack is implemented with a linked list whose top is the head of the list, that is, the node right after the dummy head node. Both push and pop work at the head, so there is no need to worry about the stack becoming full.

typedef struct SNode {
    int data;
    struct SNode *next;
} SNode, *LinkStack;

// push (insertion at the head)
bool Push(LinkStack &S, int x) {
    SNode *s = (SNode *)malloc(sizeof(SNode));
    s->data = x;
    s->next = S->next;  // S is the dummy head node
    S->next = s;
    return true;
}

// pop
bool Pop(LinkStack &S, int &x) {
    if (S->next == NULL) return false;  // the stack is empty
    SNode *p = S->next;
    x = p->data;
    S->next = p->next;
    free(p);
    return true;
}

Time complexity: both push and pop are $O(1)$, and a linked stack never becomes full.

Exercises

Exercise 1

What are the advantages and the disadvantages of the sequential storage and the linked storage of a stack?

Applications

Bracket Matching

Checking whether the left and right brackets in an expression match is a typical application of the stack: push a left bracket when it is met, and pop and match it when a right bracket is met.

bool Match(char str[], int n) {
    SqStack S;
    InitStack(S);
    for (int i = 0; i < n; i++) {
        if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
            Push(S, str[i]);  // push the left bracket
        } else {
            if (StackEmpty(S)) return false;  // no left bracket left to match
            char top;
            Pop(S, top);
            // check whether the two brackets match
            if (str[i] == ')' && top != '(') return false;
            if (str[i] == ']' && top != '[') return false;
            if (str[i] == '}' && top != '{') return false;
        }
    }
    return StackEmpty(S);  // everything matches only if the stack is empty at the end
}

Expression Evaluation

Expression evaluation usually takes two steps: converting infix to postfix, and then evaluating the postfix expression.

Infix to postfix: a stack holds the operators, and the precedence rules are followed:

1. An operand is output directly
2. A left parenthesis is pushed onto the stack
3. On meeting an operator, every operator in the stack whose precedence is not lower than it is popped, and then the new operator is pushed
4. On meeting a right parenthesis, pop until the matching left parenthesis is removed

Evaluating a postfix expression: scan from left to right, pushing an operand onto the stack; when an operator is met, pop two operands, compute the result and push it back onto the stack.

For example, the infix expression (a+b)*c becomes the postfix expression ab+c*.

Other Applications

• Function calls: managing the stack frames of recursive calls
• Recursive implementation: recursion is a stack in essence
• Browser forward and back buttons: two stacks record the history separately
• Editor undo and redo: two stacks store the operation records

Exercises

Exercise 1

Give examples of the typical applications of a stack.

Exercise 2

How can a stack be used to check whether the brackets in a string match? Briefly describe the algorithm.

Summary

A stack is a last in, first out linear list, a concept so simple that it hardly needs any explanation, but it is its three classic applications, bracket matching, expression evaluation and function calls, that give it its value in real systems. The terminology table aligns the notions of sequential stack, linked stack and shared stack with their English names, and the key takeaways list the complexity, the overflow conditions and the solution for the frequently asked question of whether a given pop sequence is legal.

Terminology Reference

Key Takeaways

• All basic stack operations, namely push, pop and reading the top element, have a time complexity of $O(1)$
• A sequential stack must guard against stack overflow, while a linked stack never becomes full
• Bracket matching, expression evaluation and function calls are the three classic applications of the stack
• Judging whether a pop sequence is legal is a frequently asked question type, and it can be verified by simulating the stack