Data Structures and Algorithms with C · Lecture Notes
Chapter 6: Stacks
A stack is the simplest linear structure: items are inserted and deleted at one end only, and the item added last is the first to leave. At first glance this restriction looks like a weakness. Yet whenever a problem obeys the rule "the task opened last is closed first," the stack is exactly the right tool: function calls, bracket matching, the undo command, and backtracking all follow that rule. These notes first define the stack as an abstract data type. They then implement the same interface in three ways: with a fixed array and a top index, with an array that grows on demand, and with a linked list. For each implementation, diagrams show what happens in memory and trace tables follow every line of code. The last sections cover the computer's own stack, the call stack, then keeping several stacks in a single memory array, and finally which output orders a stack can produce.
Learning outcomes
- Define LIFO
- Define a stack as a list S = {a0, …, an−1}, identify its bottom and top items, and find the state of a stack after a sequence of operations.
- Implement it with an array
- Write push and pop routines around a
topindex; check for overflow and underflow; explain the difference between++*topand*top--. - Build a linked stack
- Allocate nodes with
mallocand link them, release popped nodes withfree, and empty the stack without leaking memory. - Understand the call stack
- Explain how function calls behave like a stack, how each call pushes a frame, and why the call stack overflows.
- Make a design decision
- Choose among a fixed array, a growable array, and a linked list by time, memory, and risk of bugs; justify the amortized cost.
- Manage multiple stacks
- Share one memory array among n stacks with the arrays
top[i]andboundary[i], and recognize the limits of this scheme.
6.1The stack: last in, first out
Arrays and linked lists allow access to items anywhere. In an array we can write to any index; in a list we can insert a node after any node. A stack deliberately restricts this freedom. Items enter at one end only and leave from the same end. This section defines the stack and shows how it grows and shrinks over a sequence of operations.
6.1.1Definition
Everyday life offers many stack-like arrangements. From a pile of plates in the kitchen we take the top plate first. A new document on a desk goes on top of the pile and is read first. Figure 6.1 gives a more instructive example: a dead-end street one car wide, closed by a wall at one end. Cars have entered the street in the order A, B, C, D. The first car that can leave is D, the one nearest the entrance. For A to leave, D must leave first, then C, then B. Because one end is closed, cars must leave in the reverse of the order in which they entered.
A stack is an ordered list in which insertion and deletion take place at one end only. In a stack S = {a0, a1, …, an−1}, the bottom item is a0 and the top item is an−1. Item ai sits on top of ai−1 (0 < i < n). A new item is always placed above an−1, and the item removed is always the current top. The first item out is therefore the last one in. This principle is called last in, first out (LIFO).
The key word in the definition is "only." The items inside a stack are ordered, but from outside that order can be touched at a single point. Adding an item is called push and removing the top item is called pop. These are the standard names, and the notes use them throughout. Some textbooks, including Horowitz and Sahni, call the same operations add and delete.
Be careful not to confuse the word "stack" with two other things that share its name or spelling. The call stack (Section 6.7) is the stack the system uses to run function calls. The heap is the region of memory from which malloc allocates blocks, and it is also the name of the priority-queue data structure studied in a later chapter. None of these is related to the others except by name. In this chapter, "stack" means the abstract LIFO structure unless the call stack is mentioned explicitly.
6.1.2How a stack grows and shrinks
Push A, B, C, D, and E, in that order, onto an empty stack. Keep the stack in an array and store the index of the top item in a variable named top. In an empty stack top is −1. Each push increments top by one and writes the new item at that index. Figure 6.2 shows three moments in this process, followed by the first deletion.
top = 0; after C, top = 2; after E, top = 4. Deletion happens only at the top: the first item out is E, the most recently added, and top drops back to 3; the top item is now D.After every push the top item changes: after A is pushed the top is A, after B is pushed it is B, and so on. When E has been pushed, the stack holds five items and top is 4. The number of items is always top + 1. The first deletion that follows returns E, because E is on top. Had all items been popped one by one, the output order would have been E, D, C, B, A, which is exactly the reverse of the input order.
An item in the middle of the stack, say B, cannot be reached directly. To get B, the items above it, C, D, and E, must be popped first. This restriction is not a defect but a contract. A program that uses a stack is dealing with a problem in which the rule "the task opened last is closed first" holds. Because the structure permits nothing but that rule, the program stays simple and mistakes become harder to make. Wherever a stack is used, this rule is at work.
The following operations are applied to an empty stack: push(3), push(8), pop, push(5), push(1), pop, pop, push(9). After each step, the stack (bottom to top) and the item popped are:
- push(3): [3]
- push(8): [3, 8]
- pop: 8 comes out; [3]
- push(5): [3, 5]
- push(1): [3, 5, 1]
- pop: 1 comes out; [3, 5]
- pop: 5 comes out; [3]
- push(9): [3, 9]
The items popped are 8, 1, 5, in that order. At the end the stack holds two items; the bottom item is 3, the top item is 9, and in an array implementation top = 1. The item 3 is never popped, because it stays at the very bottom throughout the sequence.
6.2The stack abstract data type
Asking first what a data structure does and only then how it does it makes a program easier to change. An abstract data type (ADT) defines a set of values and the operations on those values, independently of how they are implemented. The stack ADT says which operations a stack offers and under what conditions they fail. It does not say whether the stack is built from an array or a list.
6.2.1Operations and preconditions
Table 6.1 lists the six operations of the stack ADT. The words push, pop, and peek beside the operations are the common names for the same operations.
| Operation | Meaning | Precondition / error |
|---|---|---|
stack_create(max) | Creates an empty stack that holds at most max items | — |
stack_full(S) | Returns true if the stack holds max items | — |
push(S, x) | Puts x on top | Overflow if the stack is full |
stack_empty(S) | Returns true if the stack holds no items | — |
pop(S) | Removes and returns the top item | Underflow if the stack is empty |
stack_top(S) · peek | Reads the top item without removing it | Error if the stack is empty |
The two error conditions in the table have names. Trying to add an item to a full stack is called overflow; trying to take an item from an empty stack is called underflow. Overflow rests on the assumption that a stack has a capacity. The abstract stack on paper is unbounded, but every real memory is finite. That is why the ADT gives stack_create a max value and defines the query stack_full.
Underflow, by contrast, has nothing to do with capacity. An empty stack has no top item, so asking for one is meaningless. The precondition of pop and stack_top is "the stack is not empty." Who checks this precondition is a design decision. The caller can ask stack_empty before every pop. The operation itself can also check and return an error code. The second way is safer, because forgetting the check becomes impossible.
The real value of an ADT is that it separates the code that uses a structure from the code that implements it. The same six operations can be implemented with a fixed array, with an array that grows as needed, or with a linked list. A program that calls only the ADT operations does not change when the implementation changes. These notes build all three implementations in turn and compare the costs of the same operations.
Confusing pop with peek. pop removes the top item and the stack shrinks by one. peek (stack_top) only reads the value of the top item and the stack is unchanged. If a loop that merely inspects the top value calls pop instead of peek, an item disappears at every look.
6.2.2Where stacks are used
The stack is one of the most widely used structures in computer science. What its applications share is that tasks are opened and closed in a nested fashion: the inner task finishes before the outer one. In each of the following examples, the top of the stack holds "the innermost task that is open right now."
- Call stack
- Each function call pushes a frame, containing the return address and the local variables, onto the stack. When the function returns, the frame is popped. The function called last finishes first.
- Expression evaluation
- Compilers first convert an infix expression such as
a + b * cto postfix notation. The postfix form of this expression isa b c * +. The compiler then evaluates that notation with a stack. In a postfix expression, each number is pushed, and each operator takes the top two values and pushes the result. - Backtracking
- A program searching for a path through a maze puts each fork on a stack. On reaching a dead end, it returns to the fork on top of the stack, the most recently passed one, and tries another path from there.
- Bracket matching
- Every closing bracket in an expression must match the most recently opened bracket that is still unclosed. The phrase "most recently opened" points straight to a stack.
- Undo
- A text editor puts every action it performs on a stack. The undo command (Ctrl+Z) reverses the action on top of the stack, the most recent one. A second press reverses the action before it.
- Depth-first search
- Depth-first search (DFS) in a graph keeps the nodes to be visited on a stack. This way the search goes as deep as possible along the most recently discovered path.
The interactive stack tool in the slides demonstrates this rule with a single button. When it pushes four times and then pops four times, the output order is the reverse of the input order. The fifth pop acts on an empty stack and the tool reports it as underflow.
6.2.3Checking balanced brackets
One application shows in a few lines of code why the stack is the natural choice. Suppose we ask whether the brackets (, [, and { in a string are balanced. In a balanced string every closing bracket has a matching opener, the types agree, and no bracket is left open at the end. {a[i] = (b + c) * d;} is balanced. ([)] is not: the counts are fine, but when ) arrives, the most recently opened bracket is [.
The function below uses a Stack type that keeps an array and its top index in one structure. push and pop return success as a bool; pop writes the removed value to the location pointed to by its second argument.
/* balance check for (, [ and {: each closer must match the latest opener */
bool balanced(const char *s) {
Stack st; int opener;
stack_init(&st);
for (int i = 0; s[i] != '\0'; i++) {
char c = s[i];
if (c == '(' || c == '[' || c == '{') {
if (!push(&st, c)) return false; /* nested too deep */
} else if (c == ')' || c == ']' || c == '}') {
if (!pop(&st, &opener)) return false; /* closer with no opener */
if ((c == ')' && opener != '(') || (c == ']' && opener != '[') ||
(c == '}' && opener != '{'))
return false; /* types do not match */
}
}
return stack_empty(&st); /* anything left open? */
}The function scans the string once from left to right. On seeing an opening bracket, it pushes it. On seeing a closing bracket, it pops the opener from the top of the stack. If the stack is empty at that moment, the closing bracket has no opener and the result is false. If the type of the popped opener does not agree with that of the closer, the result is again false. Characters that are not brackets are skipped. If items remain on the stack when the scan ends, some brackets were never closed, so the function finally returns whether the stack is empty.
The function was tried on these inputs: it returned 1 (true) for {a[i] = (b + c) * d;} and x = f(a[2], {1, 2});, and 0 (false) for ([)], ((), ()), and ]. The empty string is balanced and returns 1. Each character causes at most one push and one pop. Since push and pop take constant time, a string of n characters takes Θ(n) time. In the worst case every character is an opening bracket and the stack holds n items, so the extra memory is O(n).
6.3Array-based stack
The shortest way to implement a stack is a one-dimensional array. Cell 0 of the array is the bottom of the stack. Items are laid out upward through cells 1, 2, 3, and so on. The index of the top item is kept in a separate integer variable, top. This section first explains what top means and its two boundary cases, then goes through the C code of Horowitz and Sahni line by line.
6.3.1The top index, overflow, and underflow
In an array stack, all the information lies in two things: the contents of the array and the value of top. The variable top is the index of the item on top of the stack. If the stack holds k items, they occupy cells stack[0] through stack[k−1] and top = k − 1. When the stack is empty there are no items; in that case we choose top = −1. The value −1 is not a valid index, but at the first push, incrementing top by one gives exactly 0. This choice simplifies the code.
top = −1, below even cell 0; pop causes underflow in this state. On the right, the full stack: five items A through E, and top = 4 = MAX_STACK_SIZE − 1; one more push would cause overflow.Figure 6.3 shows the two boundary states side by side. Whether the stack is empty is determined by the test top < 0. If the array has MAX_STACK_SIZE cells, the last valid index is MAX_STACK_SIZE − 1. When top reaches this value the stack is full, and the test top ≥ MAX_STACK_SIZE − 1 is true. The number of items is always top + 1. Confusing top with the item count is the best-known source of off-by-one errors. For example, a program that writes the full test as top ≥ MAX_STACK_SIZE writes one cell past the end of the array.
C does not check array bounds at run time. The expression stack[MAX_STACK_SIZE] compiles and runs, but it touches the memory cell right after the array. If another variable lives there, its value is corrupted. The program may not crash immediately, and the error shows up much later in an unrelated place. For this reason the overflow and underflow checks are not an optional decoration of stack code. A push without a check overwrites neighboring memory.
6.3.2C definitions
The first implementation in the textbook by Horowitz and Sahni defines the stack as a global array:
#include <stdio.h>
#include <stdlib.h>
#define MAX_STACK_SIZE 101
typedef struct {
int key;
/* other fields */
} element;
element stack[MAX_STACK_SIZE];
void stack_full(void) {
printf("Stack is full!!!\n"); exit(-1);
}
void stack_empty(void) {
printf("Stack is empty!!!\n"); exit(-2);
}The line #define MAX_STACK_SIZE 101 fixes the capacity of the stack. Before compilation, the preprocessor replaces every occurrence of MAX_STACK_SIZE in the code with 101. To change the capacity, it is enough to edit this one line.
The type element defines the record stored in the stack. For now it has a single field, key. The comment is a reminder that in a real application other fields would be added to this record. A maze program, for instance, would put the row, the column, and the direction on the stack together. Defining the item as a struct rather than an int makes the stack code independent of what an item contains. When fields are added to the record, the stack routines do not change, because they merely copy element values.
The line element stack[MAX_STACK_SIZE]; is the stack itself. Because this array is defined outside every function, it is a global variable. Every function in the program can access it directly. Global arrays are initialized to zero and live for the whole run of the program. The variable top, however, is not global: it is defined as a local variable in the calling function (usually main) and passed to the stack routines by address.
The last two functions are error routines. stack_full prints a message and ends the program with exit(-1), and stack_empty does so with exit(-2). exit is declared in <stdlib.h> and ends the whole program no matter which function it is called from. The number passed is the exit code of the program and is handed to the operating system. On Unix-like systems the shell sees −1 as 255; on Windows this code is reported as 4294967295. The names of these two functions are the same as those of the queries stack_full and stack_empty in the ADT, but their jobs differ: they do not query, they report an error. The name clash is one of the flaws of this first implementation; in a better design these names go to the real queries.
Textbooks give these definitions in a single file, with a global array and a global top. In the exams and assignments of this course, however, global variables are forbidden. The reason is simple. Any function of the program can change a global variable. When a bug appears, finding who corrupted the variable means reading the whole program. Moreover, a single global array is useless when the same program needs two stacks. In this chapter the global array is used only to get to know the textbook code; in assignments, whatever the structure is, a stack, a queue, or something else, it is defined locally and passed by parameter.
6.3.3push and pop
The insertion and deletion routines are three lines each:
void push(int *top, element item) {
if (*top >= MAX_STACK_SIZE - 1) /* any room? */
stack_full(); /* warn and exit */
stack[++*top] = item; /* bump the index first */
} /* then store the item */
element pop(int *top) {
if (*top < 0)
stack_empty(); /* warn and exit if empty */
return stack[(*top)--]; /* return, then decrement */
}push takes two parameters. int *top is the address of the caller's top variable. element item is a copy of the item to be added. The first line tests whether there is room. *top is the integer that the pointer top points to, that is, the caller's top index. If this value has reached MAX_STACK_SIZE − 1, the stack is full and stack_full() ends the program. If there is room, the last line runs: stack[++*top] = item;. This line does two things. First *top is incremented, then the item is written at the new index. In an empty stack *top goes from −1 to 0 and the item is written to stack[0].
pop takes only the address of top. If the stack is empty, that is, *top < 0, stack_empty() ends the program. Otherwise the line return stack[(*top)--]; runs. This line also does two things, but in the opposite order. First the item at the old index is read, then *top is decremented. The item read is the return value of the function. For example, when *top is 2, stack[2] is returned and *top becomes 1.
The popped item is not erased from the array. The old value stays in cell stack[2]. But it is no longer part of the stack, because top determines the contents of the stack: the valid items are the cells from 0 up to top. The next push overwrites this cell. That deletion means pulling the boundary down rather than clearing a cell is what makes the array stack fast.
Why is top passed by address? In C, all arguments are passed by call by value. A call such as push(top, item) would hand the function a copy of the value of top. The function would increment this copy, but the caller's top would not change. The next push would write to the same cell. A function that wants to change the caller's variable is given the address of that variable: push(&top, item). Through *top the function reaches the caller's actual variable.
A writing rule matters here. A parameter that appears as *top in the function's parameter list must be used as *top everywhere inside the function. If only top is written inside, the pointer itself, an address, is being used. A test such as if (top >= MAX_STACK_SIZE - 1) compares an address with an integer. At best the compiler gives a warning; the program makes a meaningless comparison. This mistake is graded severely in exams, because not knowing the difference between a pointer and the value it points to means building every structure in this course wrongly.
Both routines cost O(1). Each performs one comparison, one index change, and one array access. The number of these operations does not depend on the number of items in the stack. The extra memory is also constant: only the parameters are used.
6.3.4The precedence trap: * with ++ and --
The expressions stack[++*top] and stack[(*top)--] are short but demand attention. The first has no parentheses; the second does. The reason for this difference is operator precedence in C. Table 6.2 compares four spellings.
| Expression | How C parses it | Result |
|---|---|---|
++*top | ++(*top): increment the int it points to, use the new value | Correct (push) |
(*top)-- | use the value of the int it points to, then decrement it | Correct (pop) |
*top-- | *(top--): decrement the pointer, read the value at the old address | Wrong: *top is unchanged |
*top++ | *(top++): advance the pointer, read the value at the old address | Wrong |
The rule is this. The postfix operators ++ and -- have higher precedence than the unary *. So in the expression *top--, the -- binds to top first: what gets decremented is the pointer itself. The prefix ++ and the unary *, on the other hand, are at the same precedence level and associate from right to left. In the expression ++*top, the * on the right is applied first, and ++ binds to its result, the integer being pointed to. That is why push needs no parentheses and pop does.
What happens if we write *top-- instead of (*top)--? The expression reads as *(top--). top-- yields the old value of the pointer and moves the pointer back by one int. The * reads at this old address. The value read is the caller's top index, so the array is read from the right cell. But what gets decremented is the local top pointer. When the function ends, this local copy vanishes. The caller's top has not changed at all. A bug of this kind is very insidious for exactly this reason: the first pop returns the right value.
The stack contains only A (top = 0). The last line of pop has mistakenly been written as return stack[*top--];. Two calls are made in a row.
- First call:
*(top--)reads the caller's 0.stack[0]= A is returned. What is decremented is the local pointer; the caller'stopstays 0. - Second call:
*top < 0is false, so underflow is not caught. Againstack[0]= A is returned, andtopis again 0.
This behavior was verified by compiling and running the code: both lines printed "pop: A top=0," and the compiler gave no warning even with -Wall -Wextra. A program that empties the stack with a loop of the form while (!empty) pop goes into an infinite loop. The *top++ mistake is worse in push: stack[*top++] = item writes to stack[-1] in an empty stack, that is, outside the array.
The most robust way to avoid this trap is to put the increment or decrement through the pointer on a separate line: first (*top)++;, then stack[*top] = item;. The code gets one line longer, but everyone who reads it understands at once what happens. The short form in the textbook is correct too, as long as one knows why the parentheses are there.
6.3.5Code trace
The behavior of the routines is easier to see with a small capacity. In the trace MAX_STACK_SIZE = 4, so the full test is *top ≥ 3. In main, with top = −1, A, B, and C are pushed in turn, one item is popped, and then D, E, and F are pushed. Table 6.3 gives the state after each call.
| Call | Test | Action | top | stack[0..top] |
|---|---|---|---|---|
| start | — | — | −1 | (empty) |
push(&top, A) | −1 ≥ 3? No | ++*top, stack[0] = A | 0 | A |
push(&top, B) | 0 ≥ 3? No | stack[1] = B | 1 | A B |
push(&top, C) | 1 ≥ 3? No | stack[2] = C | 2 | A B C |
pop(&top) | 2 < 0? No | returns stack[2] = C, top decrements | 1 | A B |
push(&top, D) | 1 ≥ 3? No | stack[2] = D (over C) | 2 | A B D |
push(&top, E) | 2 ≥ 3? No | stack[3] = E | 3 | A B D E |
push(&top, F) | 3 ≥ 3? Yes | stack_full(): "Stack is full!!!", exit(-1) | 3 | A B D E |
top = 2. In the middle, C has been popped: top has dropped to 1; the value of C stays in the cell but is no longer part of the stack. At the bottom, D and E have been pushed: top = 3 and the array is full; when F is to be pushed, stack_full() is called.The fifth row of the table shows how the array performs deletion. pop returns C and lowers top to 1. C still sits in cell 2. In the sixth row, when D is pushed, D is written to the same cell and no trace of C remains. In the last row there is no room. stack_full prints its message and ends the whole program with exit(-1). This behavior was verified by compiling and running the code: the program printed "push F ... Stack is full!!!" and Windows reported the exit code as 4294967295, that is, −1.
Ending the whole program at the moment of overflow is a crude reaction. A stack is a small library component; it cannot know what the rest of the program will do. Perhaps the caller was going to build a larger stack when this one filled up. Perhaps it would show the user a message and cancel the operation. exit takes these decisions away. Cleanup work such as closing open files properly or releasing allocated memory is also left undone when the program ends. A better design reports the error to the caller and leaves the decision to it.
6.4Designing the stack as an object
The first implementation in the textbook has three weaknesses. The stack is a global array, so the program can have only one stack. The variable top lives apart from the array; the caller has to define it separately and pass it separately in every call. On an error, the program ends with exit. This section builds a design that solves all three problems together: the array and the top index live in one structure, the routines take the stack as a parameter, and errors are reported by a return value.
6.4.1A struct instead of a global array
#include <stdbool.h>
#define CAP 100
typedef struct {
int data[CAP];
int top; /* -1 when empty */
} Stack;
void stack_init(Stack *s) { s->top = -1; }
bool stack_empty(const Stack *s) { return s->top < 0; }
bool stack_full(const Stack *s) { return s->top == CAP - 1; }
int stack_size(const Stack *s) { return s->top + 1; }
bool stack_top(const Stack *s, int *x) {
if (stack_empty(s)) return false;
*x = s->data[s->top]; return true;
}The Stack structure carries two fields: the array data of CAP items and top, which holds the top index. A stack is now a single variable. The definition Stack a, b; gives two independent stacks, each with its own array and its own top index. While one fills up, the other is unaffected. There are no global variables.
Each routine receives the stack through the parameter Stack *s, that is, by address. There are two reasons for this. First, push and pop modify the stack; if a copy passed by value were modified, the caller's stack would not change. Second, Stack is a large structure: with CAP = 100 it takes about 404 bytes. Passed by value, these 404 bytes would be copied at every call. An address is 8 bytes. The fields of the structure are accessed through the address with the arrow operator (->): s->top is shorthand for (*s).top.
The queries that do not modify the stack take const Stack *s. The const qualifier is a promise that the function will not modify the structure it points to. If an assignment such as s->top = 0; is written inside the function, the compiler reports an error. This promise informs the reader and also catches accidental modifications at compile time.
Each routine is a single line. stack_init creates an empty stack by setting top to −1. The fields of a local Stack variable hold indeterminate values at first; so every stack must be initialized once before use. stack_empty and stack_full are now real queries and return bool. stack_size gives the item count, top + 1. stack_top is the peek operation of the ADT. If the stack is empty it returns false and leaves *x untouched. Otherwise it writes the top item to *x and returns true. The value is delivered through an output parameter because the return value is reserved for success information. The type bool and the names true and false come from the header <stdbool.h>.
Push and pop are written in the same style:
bool push(Stack *s, int x) {
if (s->top == CAP - 1) return false; /* overflow */
s->data[++s->top] = x;
return true;
}
bool pop(Stack *s, int *x) {
if (s->top < 0) return false; /* underflow */
*x = s->data[s->top--];
return true;
}push first tests for overflow. If top == CAP - 1 there is no room and the function returns false. The program goes on; the caller, having learned of the overflow, decides for itself what to do. If there is room, the line s->data[++s->top] = x; first increments top, then writes the value at the new index. There is no precedence trap here: the -> operator is applied before ++, so ++s->top means ++(s->top).
pop first tests for underflow. If the stack is empty it returns false and leaves *x untouched. Otherwise the line *x = s->data[s->top--]; copies the top item to *x and then decrements top by one. The expression s->top-- likewise reads as (s->top)--; what is decremented is a field of the structure.
Because this version reports errors through the return value, it is very convenient to use. For instance, a loop that empties the stack and prints each item popped is a single line: while (pop(&st, &x)) printf("%d ", x);. The loop stops when pop returns false for the first time, that is, when the stack has become empty. All operations are again O(1).
Ignoring the result of a routine that returns bool. A program that writes push(&st, x); and never looks at the return value silently loses the item when the stack fills up. A program that writes pop(&st, &x); without checking the result keeps using the old or indeterminate value of x when the stack is empty. An interface that reports errors is useful only if the report is read.
6.4.2Code trace: push and pop returning bool
In the trace CAP = 3, so the full test is top == 2. An empty stack is created with stack_init(&st). Then 5, 8, 2, and 9 are pushed in turn, and pop is called four times. Table 6.4 gives each call and its return value.
| Call | Test | Action | Returns | top | data[0..top] |
|---|---|---|---|---|---|
stack_init(&st) | — | top = -1 | — | −1 | (empty) |
push(&st, 5) | −1 == 2? No | data[0] = 5 | true | 0 | 5 |
push(&st, 8) | 0 == 2? No | data[1] = 8 | true | 1 | 5 8 |
push(&st, 2) | 1 == 2? No | data[2] = 2 | true | 2 | 5 8 2 |
push(&st, 9) | 2 == 2? Yes | overflow, nothing is written | false | 2 | 5 8 2 |
pop(&st, &x) | 2 < 0? No | x = data[2] | true, x = 2 | 1 | 5 8 |
pop(&st, &x) | 1 < 0? No | x = data[1] | true, x = 8 | 0 | 5 |
pop(&st, &x) | 0 < 0? No | x = data[0] | true, x = 5 | −1 | (empty) |
pop(&st, &x) | −1 < 0? Yes | underflow, x untouched | false | −1 | (empty) |
top = 2 = CAP − 1, the size is 3; the fourth push returns false. At the bottom, after four pops the stack is empty: top = −1 and the last pop has returned false.The trace was verified with a test program. The program, which printed the return value of each push, produced the output "push 5:1 8:1 2:1 9:0"; 9 could not be added. The pops returned 2, 8, 5 in that order, and the fourth pop was false. The intermediate queries also worked as expected: after three pushes, stack_size gave 3, stack_full was true, and stack_top gave 2.
The difference between the two implementations shows at the overflow line. The global-array version would end the program at this point. The bool version returns false and the program continues where it left off. In the example, the caller learns that 9 could not be added. It may print a warning to the user or place 9 somewhere else. This way a single routine does not decide the fate of the whole program.
6.4.3Interface and implementation
The struct version still has a problem. The fields of the Stack structure are open to all the code that uses it. A programmer can write st.top = 5; and corrupt the stack, or reach into st.data[0] directly and break the stack discipline. A bigger problem is this: when the implementation of the stack changes, say from an array to a linked list, all the code that touches the fields directly breaks.
In C, this problem is solved by splitting the code into a header file and a source file. The header file carries the interface, that is, the types and function declarations exposed to the outside. The source file carries the implementation, that is, the bodies of these functions and the inside of the structure.
/* stack.h: all the client sees */
#ifndef STACK_H
#define STACK_H
#include <stdbool.h>
typedef struct Stack Stack; /* opaque */
Stack *stack_create(int capacity);
void stack_destroy(Stack *s);
bool push(Stack *s, int x);
bool pop(Stack *s, int *x);
bool stack_empty(const Stack *s);
#endifThe first and last lines of the header file are an include guard. In a large program, the same header can be included in a source file twice through indirect paths. The test #ifndef STACK_H processes the contents of the file if the name STACK_H is not yet defined, and defines this name right after. On the second inclusion the name is already defined, so the contents are skipped. This prevents the error of defining the same type twice.
The really important line is typedef struct Stack Stack;. This line says that a structure named struct Stack exists but does not say what its fields are. A type whose name alone is declared in this way is called an incomplete type. A type whose fields are hidden from the client is also called an opaque type. Client code cannot define a variable of an incomplete type, because the compiler does not know how many bytes it takes. Nor can it access its fields. The only thing it can do is hold a pointer to this type and pass the pointer to the functions in the header. That is why a stack is created with stack_create and destroyed with stack_destroy.
/* stack.c: implementation */
struct Stack { int *data; int top, cap; };
Stack *stack_create(int cap) {
Stack *s = malloc(sizeof *s);
if (s == NULL) return NULL;
s->data = malloc(cap * sizeof *s->data);
if (s->data == NULL) {
free(s); return NULL;
}
s->top = -1; s->cap = cap;
return s;
}
void stack_destroy(Stack *s) {
if (s) { free(s->data); free(s); }
}The source file holds the full definition of the structure. In this version the array is not of fixed size inside the structure. data is a pointer, and the array itself is allocated from heap memory during stack_create, with the requested capacity. This way the capacity of each stack can be chosen separately.
stack_create performs two allocations. First malloc(sizeof *s) is called for the structure itself. sizeof *s is the size of the type that s points to, that is, struct Stack. This spelling stays correct even if the type name changes. If the allocation fails, NULL is returned. Then malloc(cap * sizeof *s->data) is called for the array of cap items. If this second allocation fails, there is an important detail: the structure block allocated first is returned with free(s), and only then is NULL returned. If this line were forgotten, the structure's block would remain as a piece of memory that no variable can point to; that is, a memory leak would occur. If both allocations succeed, top is set to −1, cap to the requested capacity, and the address of the structure is returned.
stack_destroy follows the reverse of the allocation order. First the array and then the structure is released. The order matters: if the structure were released first, the field s->data would be read from memory that is no longer valid. The test if (s) allows the function to be called safely with NULL as well. By the C standard, free(NULL) does nothing anyway; but to read s->data, s must be valid.
For brevity, the implementation file in the slides omits the opening #include lines and three routines. A complete stack.c starts with the lines #include <stdlib.h> (for malloc and free) and #include "stack.h" (so that the compiler checks that declarations and definitions agree). The missing routines are the same as push, pop, and stack_empty of the struct version; the only difference is that the full test uses the structure's cap field instead of the constant CAP: if (s->top == s->cap - 1) return false;. With these completed, a test program that creates two separate stacks (capacities 2 and 5) was compiled and run. The third push to the stack of capacity 2 returned false; after both stacks were destroyed, a counting malloc/free wrapper counted four allocations and four releases. There is no leak.
The value of this split shows when the implementation changes. Suppose stack.c is converted from an array to a linked list. The inside of struct Stack changes completely; the fields data and cap disappear and a node pointer takes their place. But stack.h stays the same. Therefore all the files that use the stack keep working without any change, merely being relinked. This is how the ADT's separation of "what" from "how" takes concrete form in C.
6.4.4Reversing a string with a stack
The simplest application of a stack is reversing a sequence. Items are pushed in order and then popped in order. Because a stack gives back the last item first, the output order is the reverse of the input. The function below reverses a string in place this way; it uses the push and pop routines of the struct version.
void reverse(char *s) {
Stack st; int c, i;
stack_init(&st);
for (i = 0; s[i] != '\0'; i++)
push(&st, s[i]); /* assume CAP suffices */
for (i = 0; pop(&st, &c); i++)
s[i] = (char)c;
}The function has a local variable Stack st. The stack lives in the function's frame and vanishes by itself when the function returns; neither malloc nor free is needed. The first loop pushes every character up to the '\0' at the end of the string. The return value of push is not checked here; the assumption in the comment is that the string is shorter than CAP = 100 characters. The second loop, as long as pop succeeds, writes the popped character to position i of the string and increments i. When the stack is empty, pop returns false and the loop ends.
The variable c is an int because pop expects an int * as its second argument. In the call push(&st, s[i]) the char value is widened to int automatically. When writing back into the string, the cast (char)c narrows the value to char again. No information is lost, since the characters came from the char range in the first place.
Let the input be "STACK". Table 6.5 gives every step of the two loops.
| Loop | i | Action | Stack (bottom to top) | s |
|---|---|---|---|---|
| start | — | stack_init | (empty) | STACK |
| 1 | 0 | push('S') | S | STACK |
| 1 | 1 | push('T') | S T | STACK |
| 1 | 2 | push('A') | S T A | STACK |
| 1 | 3 | push('C') | S T A C | STACK |
| 1 | 4 | push('K') | S T A C K | STACK |
| 2 | 0 | pop → 'K', s[0] = 'K' | S T A C | KTACK |
| 2 | 1 | pop → 'C', s[1] = 'C' | S T A | KCACK |
| 2 | 2 | pop → 'A', s[2] = 'A' | S T | KCACK |
| 2 | 3 | pop → 'T', s[3] = 'T' | S | KCATK |
| 2 | 4 | pop → 'S', s[4] = 'S' | (empty) | KCATS |
| 2 | 5 | pop → false, the loop ends | (empty) | KCATS |
top = 4). At the bottom, the second loop has finished: the stack is empty (top = −1) and the string has become KCATS.The intermediate strings in the table may be surprising at first sight. For two steps s reads "KCACK." The reason is that the middle letter of the word "STACK," the A, is written back to the very cell where it already is, so that step changes nothing. Only the other steps actually change the string. The program was run to verify this: it gave KCATS for "STACK" and ba for "ab"; the empty string stayed empty.
The cost is clear. For a string of n characters, the first loop makes n pushes and the second makes n pops and one failed pop. Since each operation is O(1), the total time is Θ(n). Because the stack holds all n characters at once, the extra memory is also Θ(n). The same job can be done with two indices, swapping characters from the two ends, using O(1) extra memory. The value of the stack version is that it shows plainly the stack's ability to reverse order. The same method works for any stream whose order is to be reversed but whose length is not known in advance.
Forgetting the capacity assumption. reverse assumes that the string is shorter than CAP characters. For a string of 150 characters, the first 100 characters enter the stack, push returns false for the remaining 50, and those characters are silently lost. The second loop writes back only 100 characters. The result is a meaningless string made of the reverse of the first 100 characters followed by the remaining 50 characters in their original form. A safe version either checks the result of push and returns an error, or chooses the capacity according to the length of the string.
6.5Linked stack
The capacity of an array stack is chosen in advance. If the capacity is too small, the stack overflows; if it is too large, unused cells take up space for nothing. A linked list removes this dilemma. A separate node is allocated for each item, and the stack holds exactly as many nodes as it has items. This section builds the stack on a singly linked list.
6.5.1Why the top is the head of the list
In a linked list each item is a node. A node carries two fields: data, which holds the value of the item, and link, which holds the address of the next node. Because the node type contains a pointer to its own type, it is a self-referential structure:
typedef struct node {
int data;
struct node *link;
} node;Which end of the stack should correspond to which end of the list? In a singly linked list the two ends are not equal. Inserting at the head and deleting from the head are O(1): only the head pointer and one link change. Insertion at the tail is also O(1) if the last node is tracked separately. But to delete from the tail, the link of the second-to-last node has to be set to NULL. In a singly linked list one cannot go back from a node to the one before it; the second-to-last node can be found only by walking from the head, in O(n) time.
In a stack, insertion and deletion happen at the same end, so that end must be the head of the list. The pointer top, which designates the top of the stack, therefore points to the first node of the list. The item added last is at the head of the list and the item added first is at its tail. An empty stack is one whose top is NULL. In short there are two options: either keep two pointers and track the last node as well, and deletion stays slow anyway, or keep the head with a single pointer and everything is fast. The right choice is the second.
top points to the head of the list, that is, to C, the item added last; C points to B, and B points to A. The link of A is NULL: A is the bottom of the stack.Figure 6.7 shows a linked stack to which A, B, C have been pushed in that order. Pay attention to the direction of the arrows. They run from top to bottom: each node points to the node that was added before it. A pop moves top one arrow forward and removes C from the list. Nothing is shifted, and there is no capacity limit. The stack overflows only when malloc cannot find room for a new node.
6.5.2Linked push
bool push(node **top, int x) {
node *new_node = malloc(sizeof *new_node);
if (new_node == NULL) return false; /* no memory */
new_node->data = x;
new_node->link = *top; /* point to old top */
*top = new_node; /* new top */
return true;
}The function takes the parameter node **top. This is a pointer to a pointer: the address of the caller's top variable. Push is going to make the caller's top point to the new node. If a copy passed by value were changed, the caller's top would keep pointing to the old node and the new node would be lost. That is why the call is made as push(&top, 10). Inside the function, *top is the caller's top variable itself.
The body has four steps:
node *new_node = malloc(sizeof *new_node);allocates room for one node from heap memory. If the allocation fails,mallocreturnsNULLand the function exits withfalse. In that case the stack has not changed at all.new_node->data = x;writes the value into the new node. The memory thatmallocreturns is not cleared; the fields hold indeterminate values until this assignment.new_node->link = *top;makes the link of the new node point to the old top. If the stack is empty, the old top isNULLand the link of the new node becomesNULLtoo.*top = new_node;makes the caller'stoppoint to the new node. The new node is now the top of the stack.
The order of the third and fourth steps is critical. First link, then change the top. Had the order been reversed, the line *top = new_node; would have lost the address of the old top. The following new_node->link = *top; would then have linked the new node to itself. All the nodes of the old list would have remained as leaked memory that no variable can point to.
Push 10, 20, 30 in turn onto an empty stack. Table 6.6 gives the state after each line. In the table, node(10) means the address of the node whose value is 10.
| Call | Line | new_node | new_node->link | *top | Stack |
|---|---|---|---|---|---|
| start | node *top = NULL; | — | — | NULL | (empty) |
push(&top, 10) | malloc | node(?) | ? | NULL | (empty) |
new_node->data = x | node(10) | ? | NULL | (empty) | |
new_node->link = *top | node(10) | NULL | NULL | (empty) | |
*top = new_node | node(10) | NULL | node(10) | 10 | |
push(&top, 20) | new_node->link = *top | node(20) | node(10) | node(10) | 10 |
*top = new_node | node(20) | node(10) | node(20) | 20 → 10 | |
push(&top, 30) | new_node->link = *top | node(30) | node(20) | node(20) | 20 → 10 |
*top = new_node | node(30) | node(20) | node(30) | 30 → 20 → 10 |
malloc has allocated the first node; its fields are indeterminate (?) and *top is still NULL. In the second, 10 is the only item of the stack. In the third, the new node holding 30 has been prepared and linked to the old top, 20, but *top still points to 20. In the fourth, after *top = new_node, the stack is 30 → 20 → 10.The intermediate state in the third drawing is instructive. The new node is ready and points to 20, but the stack is still 20 → 10. The structure of the stack changes with a single assignment, the line *top = new_node. This arrangement is also safe in the failure case: had malloc failed, the function would have returned at the first check and the stack would not have been touched at all. Each push does a constant amount of work: one allocation and three assignments. The length of the stack does not affect this amount; push is O(1). The running time of malloc itself is also taken to be constant in practice, but it is much more expensive than writing to an array cell.
6.5.3Linked pop
bool pop(node **top, int *x) {
node *old = *top; /* no malloc! */
if (old == NULL) return false; /* empty */
*x = old->data;
*top = old->link; /* advance top */
free(old); /* release memory */
return true;
}Pop also takes node **top, because it is going to advance the caller's top to the next node. The value removed is delivered through the output parameter int *x; the return value reports success. The body consists of these steps:
node *old = *top;saves the address of the top node in a local pointer. This line allocates no new memory; it only copies an address.if (old == NULL) return false;reports underflow if the stack is empty.*x = old->data;copies the value to the caller. This line must run before the node is released.*top = old->link;advances the caller'stopto the next node. This too must be done before the release, because the link field lives inside the node that is about to be released.free(old);returns the node's memory to the system.
Apply four pops to the stack 30 → 20 → 10 and print each successful result. Table 6.7 summarizes the calls.
| Call | old | *x | *top (after) | free | Returns | Stack |
|---|---|---|---|---|---|---|
| 1st pop | node(30) | 30 | node(20) | node(30) | true | 20 → 10 |
| 2nd pop | node(20) | 20 | node(10) | node(20) | true | 10 |
| 3rd pop | node(10) | 10 | NULL | node(10) | true | (empty) |
| 4th pop | NULL | (untouched) | NULL | — | false | (empty) |
old points to the top node (30); no new memory has been allocated. Then, with *top = old->link, the top advances to 20; the node holding 30 is no longer in the list, but old still points to it. At the end, the node has been released with free(old); main prints 30.The test program pushed 10, 20, 30, called pop four times, and printed "30 20 10 false." The output order is the reverse of the input order. Pop also does a constant amount of work: one comparison, two assignments, and one free. Its cost is O(1).
The order of the steps in pop matters even more than in push. After the call free(old), the memory that old points to no longer belongs to the program. If old->data or old->link is read after that moment, the behavior is undefined. The program often reads the right value, because released memory is not handed to another use immediately. That makes the bug more dangerous: it does not show up in tests, but the value is corrupted when another malloc intervenes. A pointer that points to memory released in this way is called a dangling pointer. The robust rule is this: first save the value and the link, and call free last.
6.5.4Memory ownership and emptying the stack
In a linked stack, malloc allocates every node and one free must give each node back. In C, this responsibility lies entirely with the programmer. Nodes that remain on the stack when the program ends must be released too. A cleanup routine is written for this job:
typedef struct node {
int data;
struct node *link;
} node;
void stack_clear(node **top) {
while (*top != NULL) {
node *old = *top;
*top = old->link;
free(old);
}
} /* afterwards *top == NULL */stack_clear removes the top node until the stack is empty. Three lines run in each turn of the loop: the address of the top node is taken into old, *top is advanced to the next node, and then old is released. The order is again the same: a node is never released before its link is saved. When the loop ends, *top is NULL; the caller's top thus designates an empty stack and does not remain as a dangling pointer. In a stack of n nodes the loop runs n times; the cost is Θ(n). The extra memory is just the pointer old, that is, O(1).
One point deserves notice in this code: old is a pointer variable, not a new node. A common mistake in student code is to allocate room with malloc for every pointer: node *old = malloc(sizeof *old); old = *top;. The first line allocates room for one node; the second line overwrites old with the address of the top node. The address of the allocated block is now nowhere. One node leaks at every pop. malloc is applied to a pointer only when the pointer is going to point to a new object. To point to an existing node, an assignment is enough.
That the linked stack runs without leaks was verified with a counting wrapper. The wrapper redirects calls to malloc and free to its own functions with the help of a macro and counts every successful call. The test program pushed 10, 20, 30 and popped four times, then pushed five more items, 1 through 5, and called stack_clear. The counter showed eight malloc calls and eight free calls; after the cleanup top was NULL. In the same program sizeof(node) came out as 16. The fields of the node are a 4-byte int and an 8-byte pointer; so that the pointer sits at an address that is a multiple of 8, the compiler inserts 4 bytes of padding. For this reason, on a 64-bit system a linked stack uses four times as much memory per int as an array does; the bookkeeping records that malloc keeps for each block come on top of that.
Changing the top first in push: *top = new_node; new_node->link = *top;. When the second line runs, *top is already new_node; the node points to itself and all the nodes of the old stack are lost. Any loop that walks the stack from the top then spins forever on the same node. The correct order: first new_node->link = *top;, then *top = new_node;.
6.6Array-based or linked?
So far two implementations have been built: the fixed-capacity array and the linked list. There is a third option in between: an array that grows itself when it fills up. This section first builds this third implementation, then justifies its cost with amortized analysis, and finally compares the three implementations.
6.6.1The growable array
The problem with a fixed array is that the capacity must be known in advance. The solution is to keep the array in heap memory and, when it fills up, move it to a larger block with realloc. An array that is enlarged with realloc when full is called a dynamic array. The real question is how much to enlarge it. If the capacity is doubled at every fill-up, the average cost of the pushes stays constant. The implementation below follows the layout of the struct version:
typedef struct {
int *data;
int top, cap; /* top = -1 when empty */
} DynStack;
bool dyn_init(DynStack *s, int cap) {
s->data = malloc(cap * sizeof *s->data);
if (s->data == NULL) return false;
s->top = -1; s->cap = cap;
return true;
}
bool dyn_push(DynStack *s, int x) {
if (s->top == s->cap - 1) { /* full: double the capacity */
int *bigger = realloc(s->data, 2 * s->cap * sizeof *bigger);
if (bigger == NULL) return false; /* old block still valid */
s->data = bigger;
s->cap *= 2;
}
s->data[++s->top] = x;
return true;
}
bool dyn_pop(DynStack *s, int *x) {
if (s->top < 0) return false;
*x = s->data[s->top--];
return true;
}
void dyn_destroy(DynStack *s) {
free(s->data);
s->data = NULL; s->top = -1; s->cap = 0;
}The DynStack structure carries three fields: the address of the array in heap memory, data; the top index, top; and the current capacity, cap. dyn_init allocates the array with the requested initial capacity. dyn_pop is identical to pop in the struct version.
The difference is in dyn_push. If the stack is full, the routine does not return an error; it tries to double the capacity. realloc(s->data, new_size) brings the old block to the new size. If there is room right behind the old block, the block can grow in place. If not, realloc allocates a new block, copies the old contents there, releases the old block, and returns the address of the new block. The number of items copied is the current capacity.
The result of realloc is not written directly to s->data; it is first taken into a temporary pointer named bigger. The reason is the failure case. If realloc fails, it returns NULL and leaves the old block alone. Had the result been written directly to s->data, the address of the old block would have been lost and all the items in it would have leaked. Thanks to the temporary pointer, on failure the stack remains valid as it was and the function returns false. On success, data and cap are updated, and then the item is written as usual.
When 10, 20, 30, 40, 50 are pushed onto a stack whose initial capacity is 2, the capacity changes as follows: 10 and 20 find room (cap = 2). When 30 is pushed the stack is full; the capacity rises to 4 and 2 items are copied. 40 finds room. When 50 is pushed the capacity rises to 8 and 4 items are copied. These values were verified by printing them in a test program: after each push, the pairs (top, cap) were (0, 2), (1, 2), (2, 4), (3, 4), (4, 8). The counting wrapper counted two malloc calls and two free calls.
6.6.2Amortized cost
In a growable array, the cost of a single push varies greatly with the situation. Most pushes write to one cell and are O(1). But the push made at the moment the capacity is full copies all the items and is O(n). Worst-case analysis therefore says "push is O(n)." This is true but misleading: the expensive pushes are very rare. Finding the average cost per operation by dividing the total cost of a sequence of operations by the number of operations is called amortized analysis. The average here does not rest on probability; it holds even for the worst possible sequence of operations.
Perform n pushes in a row onto an empty growable-array stack of capacity 1, doubling the capacity each time it fills. The total number of items copied over all the enlargements is less than 2n. Therefore the total cost of n pushes is O(n) and the amortized cost per push is O(1).
Proof. An enlargement happens when a push is made while the stack is full. Since the capacity goes 1, 2, 4, 8, …, enlargements occur at capacities 1, 2, 4, …, 2k. An enlargement at capacity c copies c items. If the last enlargement happened at capacity 2k, then at that moment the stack holds 2k items and one more is being pushed; hence 2k < n. The total number of copies is 1 + 2 + 4 + … + 2k = 2k+1 − 1. Since 2k ≤ n − 1, this total is at most 2n − 3, a constant multiple of n. Each push also does one write. The total work is bounded by n + (2n − 3) < 3n, which is under 3 units per push. ∎
The bound on the copies in the proof can be stated more tightly. The total of the copies is 2k+1 − 1 and the final capacity is 2k+1; that is, the total number of copies is one less than the final capacity. The final capacity is also less than 2n. These numbers were verified with a test program: when 1000 pushes were made onto a stack of capacity 1, there were 10 enlargements, 1023 items were copied in total (fewer than 2n = 2000), and the final capacity reached 1024.
The growth factor does not have to be two; what matters is that it is a constant factor greater than 1. If a factor of 1.5 is chosen, the copies increase somewhat and the idle capacity decreases; the amortized cost remains O(1). By contrast, if the capacity is raised by a fixed amount at each fill-up, say 10 cells, the amortized cost breaks. Over n pushes there are about n/10 enlargements, and each copies all the current items. The total number of copies is 10 + 20 + … + n ≈ n²/20; the cost per push rises to Θ(n).
Writing s->data = realloc(s->data, …);. If realloc fails, it returns NULL and this assignment erases the only address of the old block. All the contents of the stack are lost and the old block leaks. The result must first be taken into a temporary pointer and written to the real field only after it is seen not to be NULL.
6.6.3Comparison and measurements
Table 6.8 compares the three implementations on six criteria.
| Criterion | Fixed array | Growable array | Linked list |
|---|---|---|---|
| Capacity | Fixed at compile time | ×2 as needed | Until memory runs out |
| push / pop | O(1) | O(1) amortized | O(1), a malloc per push |
| Extra memory per item | None | None (except unused capacity) | One pointer (8 bytes) and padding |
| Cache behavior | Very good | Very good | Poor (nodes scattered) |
| Overflow | Possible | Only if realloc fails | Only if malloc fails |
| Bug risk | Bounds checks | The result of realloc | Forgotten free, dangling pointer |
The "cache behavior" row needs an explanation. On every memory access, the processor brings into the cache not a single number but the 64-byte block around it. In an array stack, consecutive items lie side by side, so many items fit in one block and later accesses are served from the cache. In a linked stack, each node is a separate malloc block and where it will sit in memory is not known. Reaching consecutive nodes often requires fetching a new block.
The asymptotic costs are the same, but the constant factors differ greatly. To see this, a program that performs 107 pushes followed by 107 pops on each of the three implementations was compiled with -O2 and run three times. The fixed array took 25–35 ms, the growable array (initial capacity 16) 30–63 ms, and the linked stack 680–806 ms. These values vary from machine to machine, but the ratio is consistent: the linked stack is roughly twenty times slower than the array stacks. Most of the difference comes from the malloc at every push and the free at every pop, and the rest from cache misses.
A practical rule for choosing is this. If the largest size the stack can reach is known, a fixed array is the simplest and fastest solution. If it is not known, a growable array is the fastest in practice. A linked stack suits cases where the nodes already live in other structures or where items are created and deleted one by one. For example, in a program whose items are large records that are shared with other lists, linking the nodes into the stack is cheaper than copying them into an array.
6.7The call stack
The computer's most heavily used stack is not one that a programmer writes. Every C program uses a stack set up by the compiler and the operating system to manage function calls. It is called the call stack. This section explains how the call stack works, how it overflows, and how a recursive function can be written with our own stack instead of this one.
6.7.1The frame
When a function is called, the information needed for the call to live is written to a block in memory. This block is called a stack frame (or activation record). The first part of the frame is the return address: it says from which instruction in the caller execution continues when the function ends. The frame also holds the function's parameters, its local variables, and the information needed to return to the caller's frame. A call pushes a new frame onto the call stack. return pops this frame and control passes to the return address. The function called last finishes first; this is why the call stack is a true stack.
A recursive function shows this arrangement clearly:
long fact(int n) {
if (n <= 1) return 1; /* base case */
return n * fact(n - 1); /* multiply when the call returns */
}Let main call fact(5). To compute its result, fact(5) waits for the result of fact(4); fact(4) calls fact(3), which calls fact(2), which calls fact(1). Each call has its own n, and these values do not get mixed up, because each lives in a separate frame. fact(1) reaches the base case and returns 1. At that moment the stack has the most frames: six frames, counting main. Then the frames are popped in reverse order: fact(2) returns 2·1 = 2, fact(3) returns 3·2 = 6, fact(4) returns 4·6 = 24, and fact(5) returns 5·24 = 120. Table 6.9 summarizes this process.
| Moment | Call stack | Number of frames |
|---|---|---|
main starts | main | 1 |
fact(5) is called | main | fact(5) | 2 |
fact(4) is called | main | fact(5) | fact(4) | 3 |
fact(1) is called | main | fact(5) | fact(4) | fact(3) | fact(2) | fact(1) | 6 (maximum) |
fact(1) returns 1 | main | fact(5) | fact(4) | fact(3) | fact(2) | 5 |
fact(2) returns 2 | main | fact(5) | fact(4) | fact(3) | 4 |
fact(5) returns 120 | main | 1 |
That frames really are stacked in memory can be seen with an experiment. At each call of fact, the address of the parameter n was printed (-O0, Windows x86-64). At every call the address was 96 bytes lower than at the previous one: from a local variable in main to the n of fact(5) was 80 bytes, and to the n of fact(1) it was 464 bytes. These numbers vary with the compiler, the optimization level, and the processor. The observation that does not change is this: on x86 processors the call stack grows from high addresses toward low addresses, and each call adds a frame of fixed size. fact(n) therefore uses Θ(n) frames, that is, Θ(n) stack memory.
6.7.2How the call stack overflows
The capacity of the call stack is limited and fixed when the program starts. Typical values are a few megabytes: 8 MB on Linux, 1 MB on Windows with the Microsoft compiler. The zig cc compiler used for this work allocated 16 MB to Windows programs. When the stack fills up, the program crashes with a stack overflow error. Below are two typical causes and one bug that comes from the same stack layout.
- Infinite recursion
- A recursion with no base case, or one that never reaches it, pushes a frame at every call and pops none. For example, had the condition in
factbeen written asn == 1, the callfact(0)would have descended forever through −1, −2, …. In an experiment, an infinite recursion that keeps a 64-byte local array in each call stopped at a depth of about 104,000 calls with the Windows errorSTATUS_STACK_OVERFLOW(0xC00000FD). - Large local arrays
- A local array such as
int a[1000000];lives inside the frame and by itself takes 4 MB. It would overflow a 1 MB stack all on its own. In an experiment this array fit in a 16 MB stack, while an array of 5 million items (20 MB) crashed the program with the same error. Large data is kept in heap memory withmallocor defined asstatic. - Returning a local address
- Writing
return &local;is not an overflow but a bug that comes from the same stack layout. When the function returns, its frame is popped. That region of memory is reused for the frame of the next call. The address returned now points to the local variables of another call; it is a dangling pointer.
Stack overflow must be kept in mind in every recursive routine in this course. For example, a function that frees a linked list recursively pushes one frame per node. For a list of a million nodes that means a million frames, and it can overflow the stack.
6.7.3Turning recursion into a loop
Since the call stack is a stack, any recursive algorithm can be turned into a loop by doing, with our own stack, the work the call stack does. A recursive call puts "the work left unfinished for now" into a frame. In the loop version this unfinished work is pushed onto an explicit stack. For the factorial, the unfinished work is the information "multiply by n on return":
long fact_loop(int n) {
Stack st; int k; long result = 1;
stack_init(&st);
while (n > 1) /* push the "calls" on our own stack */
push(&st, n--);
while (pop(&st, &k)) /* multiply on the "returns" */
result *= k;
return result;
}The first loop imitates the descending calls of the recursive version: it pushes n until it falls to 1. For 5, the stack from bottom to top becomes 5, 4, 3, 2. The second loop imitates the returns: it multiplies the result by each value popped from the stack. The products are made in the order 2, 3, 4, 5, the same as the order of returns in the recursive version. The result is 120. fact_loop(0) and fact_loop(1) gave 1, and fact_loop(10) gave 3628800, the same as the recursive fact.
For the factorial this conversion is unnecessary; a simple for loop suffices. But in algorithms such as tree traversal, depth-first search, or backtracking, the unfinished work is not a single number. The unfinished work is a state, and that state is what gets pushed on the stack. Using our own stack has two benefits. First, our own stack can grow in heap memory; it is not bound by the few-megabyte limit of the call stack. Second, only the information that is needed is pushed onto the stack; there is none of the overhead of a frame, such as the return address and the saved registers.
6.8Multiple stacks
A program can use more than one stack at a time. Giving each stack its own array is easy, but memory is wasted: when one stack fills up, the others may have free room that cannot be reached. This section deals with sharing several stacks in a single memory array.
6.8.1Two stacks in one array
For two stacks there is a very neat solution. In an array of m cells, the first stack grows upward from cell 0 and the second grows downward from cell m − 1. The tops of the two stacks move toward each other.
top1 = 2). Stack 2 grows to the left from cell 7 and holds two items (2, 6; top2 = 6). The three cells in between are the free space shared by the two stacks.When both are empty, top1 = −1 and top2 = m; each points to an imaginary cell outside the array. Pushing onto stack 1 increments top1, and pushing onto stack 2 decrements top2. The array is full when the two tops become adjacent, that is, when top1 + 1 == top2. The advantage of this arrangement is that no cell is wasted. Even if one stack holds few items and the other many, the array fills only when the total reaches m items. For three or more stacks this trick does not work, because an array has only two ends.
6.8.2n stacks in one memory
For n stacks, the solution of Horowitz and Sahni is to divide the memory array of m cells into n segments. Each stack grows within its own segment. Two helper arrays are used. top[i] is the index of the top item of stack i. boundary[i] is the index of the cell just below the segment of stack i. Stack i uses the cells from memory[boundary[i]+1] to memory[boundary[i+1]]. To be able to write the upper bound of the last stack in the same way, boundary[n] = m − 1 is added.
Initially memory is divided into equal parts and all stacks are empty: for i = 0, …, n − 1, top[i] = boundary[i] = (m/n)·i − 1. A stack is empty when its top equals its own lower boundary: top[i] == boundary[i]. It is full when its top reaches the lower boundary of the next stack: top[i] == boundary[i+1]. Push and pop are written with these two tests:
/* stack i: boundary[i]+1 .. boundary[i+1] */
bool push(int i, int x) {
if (top[i] == boundary[i+1]) return false; /* full */
memory[++top[i]] = x;
return true;
}
bool pop(int i, int *x) {
if (top[i] == boundary[i]) return false; /* empty */
*x = memory[top[i]--];
return true;
}This code assumes that the arrays memory, top, and boundary are defined globally; it is kept short, as in the textbook. In a real program these three arrays are gathered in a struct and passed to the routines by address. The structure of the routines is the same as for a single stack; only the array boundary takes the place of the fixed limits. push returns false if the stack is full; otherwise it increments top[i] and writes the value. pop returns false if the stack is empty; otherwise it writes the top value to *x and decrements top[i]. Both are O(1).
6.8.3Code trace
Let m = 12 and n = 3. Each stack gets four cells. Initially top = [−1, 3, 7] and boundary = [−1, 3, 7, 11]. Stack 0 uses cells 0–3, stack 1 uses cells 4–7, and stack 2 uses cells 8–11. The calls push(0, 5), push(1, 7), push(0, 9), push(2, 4), push(0, 2), push(0, 8), push(0, 6), and pop(1, &x) are made in turn. Table 6.10 gives each call.
| Call | Test | Action | top |
|---|---|---|---|
| start | — | — | [−1, 3, 7] |
push(0, 5) | −1 == 3? No | memory[0] = 5 | [0, 3, 7] |
push(1, 7) | 3 == 7? No | memory[4] = 7 | [0, 4, 7] |
push(0, 9) | 0 == 3? No | memory[1] = 9 | [1, 4, 7] |
push(2, 4) | 7 == 11? No | memory[8] = 4 | [1, 4, 8] |
push(0, 2) | 1 == 3? No | memory[2] = 2 | [2, 4, 8] |
push(0, 8) | 2 == 3? No | memory[3] = 8 | [3, 4, 8] |
push(0, 6) | 3 == 3? Yes | false: stack 0 is full | [3, 4, 8] |
pop(1, &x) | 4 == 3? No | x = memory[4] = 7 | [3, 3, 8] |
push(0, 6) is rejected, although six cells of memory are free. At the bottom, pop(1, &x) has removed 7; stack 1 is empty again.The trace was verified with a test program; the top array after each call printed the same as in the table. The seventh call shows the weakness of the scheme. Stack 0 is full, because its top has reached the boundary of the next stack (boundary[1] = 3). Yet of the 12 cells in memory only six are occupied: stack 0 holds four items, stack 1 one, and stack 2 one. The remaining six cells are free. Even so, push says "full."
6.8.4Making room and evaluation
Horowitz and Sahni solve this problem with a routine stack_full(i). The routine is called when stack i fills up. First it looks among the stacks to the right for the first one with free room. If it finds one, it shifts the stacks in between one cell to the right and so opens one cell for stack i. If there is no room on the right, it makes the same search among the stacks on the left and shifts the ones in between, stack i itself included, one cell to the left. If there is no free cell anywhere, memory is truly full. Below, only the half that shifts to the right is given, simplified:
/* when stack i is full, look for room on the right; if found, shift
the stacks in between one cell right (Horowitz's idea, simplified) */
bool make_room_right(int i) {
int j = i + 1, k;
while (j < N && top[j] == boundary[j + 1]) /* first stack with room */
j++;
if (j == N) return false; /* no room on the right */
for (k = top[j]; k > boundary[i + 1]; k--) /* memory[boundary[i+1]+1 .. top[j]] */
memory[k + 1] = memory[k]; /* shift one right */
for (k = i + 1; k <= j; k++) { /* boundaries and tops shift too */
boundary[k]++;
top[k]++;
}
return true;
}The function tries the stacks to the right of i in turn. It skips those with top[j] == boundary[j+1], that is, those that are themselves full, and stops at the first stack with free room. If none is found, it returns false. If one is found, the cells from boundary[i+1]+1 to top[j] are copied one cell to the right. These cells hold the items of all the stacks from i + 1 to j. The copying must start from the right; had it started from the left, each cell would have overwritten the next and values would have been lost. Finally both the lower boundaries and the tops of these stacks are incremented. The upper bound of stack i, boundary[i+1], has also grown by one; stack i gains one cell.
Applied to the situation in the trace: stack 0 is full; the stack to its right, stack 1, has room (top[1] = 4, boundary[2] = 7). The only item of stack 1, 7, moves from memory[4] to memory[5]. boundary[1] rises to 4 and top[1] to 5. After that, push(0, 6) succeeds and 6 is written to memory[4]. A test program verified these steps: after making room, top = [3, 5, 8] and boundary = [−1, 4, 7, 11]; after the push, stack 0 held "5 9 2 8 6," stack 1 "7," and stack 2 "4."
The pros and cons of this approach are clear. Pros: a single array and a single malloc suffice and management is easy; push and pop are again O(1); the same idea can be used to keep n queues in one array. Cons: when one segment fills up, a "full" error comes even though there is room in memory; shifting the stacks to make room is expensive. The number of items shifted can reach m. When memory is nearly full, every push may require a shift, and in the worst case every push is O(m). It is also hard to estimate segment sizes in advance. If the stacks grow at different rates, equal division leads to frequent shifting.
6.9Which output orders are possible?
To understand how a stack can change the order of its input, a classic question is asked. The numbers 1, 2, 3, 4 are to be pushed in this order. Any number of pops may be placed between the pushes, and at the end the stack is emptied. In what order can the numbers come out; that is, which permutations are possible as the output order of the pops?
Some orders are easy to get. For 1 2 3 4, a pop is made right after each push. For 4 3 2 1, four pushes are made, followed by four pops. For 2 4 3 1, this sequence is enough: push 1, push 2, pop (2), push 3, push 4, pop (4), pop (3), pop (1). But can 3 1 4 2 be obtained? If 3 is to come out first, 1 and 2 must have been pushed before 3 is pushed; at the moment 3 comes out, the stack holds 1 and 2 from bottom to top. The next item out can be either 2 on top or 4, which has not been pushed yet. Since 1 lies beneath 2, it cannot come out before 2. 3 1 4 2 is therefore impossible.
This reasoning turns into a general rule. At the moment an x comes out, all the items pushed before x and not yet popped are on the stack and must come out in the reverse of the order in which they were pushed. The rule can also be stated as a forbidden pattern.
If 1, 2, …, n are pushed in this order, an output order p1 p2 … pn can be obtained if and only if there are no three positions i < j < k with pj < pk < pi. In other words, the sequence contains no "large, small, medium" pattern.
Proof. First we show that the pattern is impossible. When pi comes out, pj and pk, which are smaller than it, have already been pushed, since numbers are pushed in increasing order. Neither has come out yet, because they come after pi in the output order. So both are on the stack, and since pj < pk, pk was pushed later, that is, it lies above pj. In this case pj cannot come out before pk; yet in the sequence it comes first. Contradiction.
For the converse, a greedy method is used: if the next target is p, push until p has been pushed, then pop the top item. The method gets stuck only if the target is not currently on top of the stack and has already been pushed. In that case, above the target pj there is a larger item q that has not yet come out. q is at some position k in the sequence after pj. All the items on the stack are smaller than the largest value that has come out so far, that is, than some pi at an earlier position. This gives the pattern pj < q = pk < pi. If there is no pattern, the method never gets stuck and the sequence is obtained. ∎
In the sequence 3 1 4 2, the positions of 3, 1, 2 form this pattern: 3 is large, 1 is small, 2 is medium. So it is impossible. In 2 4 3 1 there is no such triple. The number of obtainable orders is also known. For n items this number is the nth Catalan number: Cn = (2n)! / ((n + 1)! · n!). The first values are 1, 2, 5, 14, 42, 132. For n = 4, only 14 of the 24 permutations are obtainable. For n = 3, only one of the six permutations, 3 1 2, is impossible. These numbers were verified for n = 1, …, 6 by a script that tries every permutation with the greedy method; the same script also checked that for n ≤ 7 the pattern condition and the greedy method give the same result on every permutation.
1, 2, 3, 4, 5 will be pushed in this order. Can the orders 3 5 4 2 1 and 5 3 4 1 2 be obtained?
3 5 4 2 1: push 1, push 2, push 3, pop (3); the stack is [1, 2]. Push 4, push 5, pop (5); the stack is [1, 2, 4]. Pop (4), pop (2), pop (1). Each target was on top at the moment it was popped; the order is obtained. Searching for the pattern also finds no "large, small, medium" triple.
5 3 4 1 2: for 5 to come out, all five numbers must have been pushed; when 5 comes out, the stack is [1, 2, 3, 4] from bottom to top. The next target is 3, but 4 is on top. The order cannot be obtained. As a pattern, the triple 5, 3, 4 (large, small, medium) is found.
6.10Complexity summary
Table 6.11 gives the costs of the operations in this chapter for the three implementations side by side. Each value is justified in the relevant section.
| Operation | Fixed array | Growable array | Linked |
|---|---|---|---|
| push | O(1) | O(1) amortized, worst case O(n) | O(1) |
| pop | O(1) | O(1) | O(1) |
| peek / empty / full | O(1) | O(1) | O(1) |
| Memory for n items | MAX (fixed) | ≤ 2n cells | n · (item + pointer) |
| Clearing | O(1) | O(1) (a single free) | Θ(n) |
Call stack of fact(n) | Θ(n) frames (independent of the implementation) | ||
| Multiple-stack push | O(1); making room O(m) | — | — |
The clearing row in the table stresses one difference. Array stacks sit in a single block; to clear a fixed array it is enough to set top = -1, and for a growable array a single free suffices. In a linked stack, however, each node is a separate block and free is called n times for n nodes. The bound "≤ 2n" in the memory row holds when the capacity starts at 1 and is doubled; if the capacity is never shrunk, after many pops the idle capacity can remain far above n.
6.11Common mistakes
Most of the bugs seen in stack code fall into a few patterns. The list below gathers the mistakes that can be met in each piece of code in this chapter.
- Skipping the bounds check. A pop from an empty stack or a push onto a full stack reads or writes the array outside its bounds. C does not check this; neighboring memory is corrupted and the error shows up much later, in an unrelated place.
- Writing
*top--. The expression reads as*(top--)and decrements the pointer; the caller's top index does not change. The correct form is(*top)--. The compiler gives no warning. - Confusing
topwith the item count.topis the index of the last item; the item count istop + 1. The full test istop == MAX - 1, nottop == MAX. - Writing
*top = new_nodefirst in a linked push. The address of the old list is lost and the new node points to itself. - Reading the value after
freein pop, or never releasing the node. The first is undefined behavior through a dangling pointer; the second is a memory leak. - Calling
mallocneedlessly on a temporary pointer.node *old = malloc(…); old = *top;leaks a node at every call. An assignment is enough to point to an existing node. - Writing the result of
reallocstraight into the real pointer. On failure, the address of the old block is lost. - Ignoring
boolresults. The item of a failed push is silently lost; after a failed pop the old value goes on being used.
6.12Exercises and solutions
The six questions on the exercise slide of the presentation are given below with their solutions. All the solutions were compiled and run with small test programs.
6.12.1A push that returns an error
Question. Rewrite push of the global-array stack to return a bool instead of calling exit.
bool push(int *top, element item) {
if (*top >= MAX_STACK_SIZE - 1)
return false; /* overflow: the caller decides */
stack[++*top] = item;
return true;
}
bool pop(int *top, element *item) {
if (*top < 0)
return false; /* underflow */
*item = stack[(*top)--];
return true;
}On overflow the function returns false and leaves the stack alone. If there is room, it writes the item and returns true. pop has to be written the same way; since the item can no longer be delivered as the return value, it is delivered through an output parameter, element *item. A test program that tried to push 10, 20, 30, 40 with capacity 3 printed "1 1 1 0": the fourth push was rejected. The loop that then emptied the stack gave 30, 20, 10, and top returned to −1. At no point did the program end through exit.
6.12.2Two stacks in one array
Question. Write the routines push(k, x) and pop(k, &x) for two stacks in one array (k = 1 or 2).
#define M 10
int buf[M];
int top1 = -1, top2 = M; /* both empty */
bool push(int k, int x) {
if (top1 + 1 == top2) return false; /* tops have met: full */
if (k == 1) buf[++top1] = x; /* stack 1 grows up */
else buf[--top2] = x; /* stack 2 grows down */
return true;
}
bool pop(int k, int *x) {
if (k == 1) {
if (top1 == -1) return false; /* stack 1 empty */
*x = buf[top1--];
} else {
if (top2 == M) return false; /* stack 2 empty */
*x = buf[top2++];
}
return true;
}When both are empty, top1 = −1 and top2 = M. The full test is shared by the two stacks: top1 + 1 == top2. Pushing onto stack 1 is done with buf[++top1] and onto stack 2 with buf[--top2]; since stack 2 grows downward, its top decreases. In pop, the empty tests are separate: top1 == -1 for stack 1 and top2 == M for stack 2. Popping from stack 2 is done with buf[top2++].
With M = 10, seven pushes onto stack 1 and five onto stack 2 were tried. All seven of stack 1 went in; the first three of stack 2 went in and the next two were rejected, because the ten cells in total were full (top1 = 6, top2 = 7). That one stack held many items and the other few wasted no cell. All the operations are O(1).
6.12.3A linked stack that knows its size
Question. Move the linked stack into a struct that keeps a size field along with top.
typedef struct {
node *top;
int size;
} SizedStack;
void sized_init(SizedStack *s) { s->top = NULL; s->size = 0; }
bool sized_push(SizedStack *s, int x) {
if (!push(&s->top, x)) return false; /* reuse the linked push */
++s->size;
return true;
}
bool sized_pop(SizedStack *s, int *x) {
if (!pop(&s->top, x)) return false;
--s->size;
return true;
}
void sized_clear(SizedStack *s) {
stack_clear(&s->top);
s->size = 0;
}SizedStack keeps the top pointer and the item count together. The routines reuse the linked stack's push, pop, and stack_clear; they pass them &s->top, that is, the address of the pointer field inside the structure. size changes only after successful operations: a failed push (out of memory) or a failed pop (empty stack) does not corrupt the counter. This way the number of items is known in O(1) without counting the list. After six pushes and one pop size was 5; after clearing it was 0, and the counting wrapper counted six free calls against six malloc calls.
6.12.4Reversing a string with a stack
Question. Write a routine void reverse(char *s) that reverses a string using a stack.
Solution. This routine is the same as reverse traced in Table 6.5: the characters are pushed in order, then popped and written back into the same array. The time is Θ(n) and the extra memory is Θ(n). A robust version first finds the length of the string with strlen and creates the stack with that capacity (for example with stack_create(n)), so that the assumption about CAP is no longer needed.
6.12.5The bottom item
Question. Write a routine that returns the bottom item of a stack using only push and pop; an auxiliary stack may be used.
/* if s is not empty, store the bottom item in *x; restore s */
bool bottom(Stack *s, int *x) {
Stack aux; int v;
if (stack_empty(s)) return false;
stack_init(&aux);
while (pop(s, &v)) /* move everything to the auxiliary stack */
push(&aux, v);
*x = v; /* the last one out was the bottom */
while (pop(&aux, &v)) /* move back: order is preserved */
push(s, v);
return true;
}The routine moves all the items of the stack to the auxiliary stack. The item popped last during the transfer is the bottom item of the original stack; the variable v holds it when the loop ends. Then the items are moved from the auxiliary stack back to the original one. Since both transfers reverse the order, the original stack returns to its initial state. If the stack is empty to begin with, v would never be assigned, so the routine returns false at the very start. On a stack holding 4, 7, 1, 9 from bottom to top, the routine gave 4, and reading the stack from the top still gave 9, 1, 7, 4. In a stack of n items, 2n pushes and 2n + 2 pops are made; the time is Θ(n) and the extra memory is Θ(n).
6.12.6Number of frames in a fact(5) call
Question. What is the maximum number of frames on the stack during the call fact(5)? Draw them, counting main.
Solution. Since the base case is n <= 1, the calls are fact(5), fact(4), fact(3), fact(2), fact(1). While fact(1) runs, these five frames and the frame of main are on the stack together: at most 6 frames. The drawing is the row "fact(1) is called" of Table 6.9: from bottom to top, main, fact(5), fact(4), fact(3), fact(2), fact(1). Had the base case been written as n == 0, fact(0) would be called too and the number would be 7.
6.13Summary
- A stack is an ordered list in which insertion and deletion take place at the top end only. It is last in, first out (LIFO). Insertion is called push, removal pop, and reading without removing peek.
- Adding to a full stack is overflow, and removing from an empty stack is underflow. The stack ADT defines the operations and these error conditions independently of the implementation.
- In an array stack,
topis the index of the top item:top= −1 means empty,top= MAX − 1 means full; the item count istop + 1. Push is writtenstack[++*top] = itemand popreturn stack[(*top)--].*top--decrements the pointer and is wrong. - Routines that return
boolleave the decision to the caller, unlike routines that end withexit. The array and the top index are kept in astruct; no global variables are used. An opaque type in the header file hides the implementation from the code that uses it. - In a linked stack,
topis the head of the list; push and pop are O(1). In push, link first and then change the top; in pop, save the value and the link first and callfreelast. Everymallocmust have afree; the stack is emptied in Θ(n) withstack_clear. - A growable array doubles its capacity with
reallocwhen it fills up. A single push can be O(n), but over n pushes the total number of copies is less than 2n; the amortized cost of push is O(1). In practice array stacks are much faster than a linked stack that callsmallocat every push. - The call stack pushes a frame made of the return address, the parameters, and the locals for each call. Infinite recursion and large local arrays overflow it; returning the address of a local variable creates a dangling pointer. Every recursive algorithm can be turned into a loop that keeps its own stack.
- With multiple stacks, one memory array is shared through
top[i]andboundary[i]. Two stacks growing from the ends waste no cells. With n stacks, when a segment fills up, room is made by shifting stacks; this can take O(m). - The output orders obtainable when 1, …, n are pushed in this order are those that contain no "large, small, medium" pattern; their number is a Catalan number (14 for n = 4).
6.14Key terms
- stack
- last in, first out (LIFO)
- top
- push
- pop
- overflow
- underflow
- abstract data type (ADT)
- implementation
- interface
- header file
- include guard
- opaque type
- incomplete type
- global variable
- call by value
- operator precedence
- associativity
- const qualifier
- linked list
- node
- malloc
- free
- realloc
- memory leak
- dangling pointer
- dynamic array
- capacity
- amortized analysis
- cache
- call stack
- stack frame (activation record)
- return address
- stack overflow
- recursion
- base case
- balanced brackets
- expression evaluation
- postfix
- backtracking
- undo
- depth-first search (DFS)
6.15Test Yourself
On a
structstack withCAP= 3, the following are applied in turn:push 4,push 7,pop,push 1,push 6,push 2; then the stack is emptied with the loopwhile (pop(&st, &x)). Which push returnsfalse, and which values does the loop print?Answer
4 and 7 go in; pop removes 7 and the stack is [4]. 1 and 6 go in; the stack is full with [4, 1, 6] (
top= 2). Sopush 2returnsfalse. The loop prints 6, 1, 4 and stops at the fourth pop.In
pop,return stack[*top--];has been written in place ofreturn stack[(*top)--];. What does a loop that callspopuntil the stack is empty do?Answer
*top--reads as*(top--): what is decremented is the function's local pointer, and the caller'stopdoes not change. Every call returns the same top item and the stack never empties; the loop runs forever. The compiler does not report this bug with a warning.1, 2, 3, 4, 5 are pushed in this order. Which of the output orders 3 5 4 2 1 and 5 3 4 1 2 can be obtained?
Answer
3 5 4 2 1 can be obtained: push 1, 2, 3, pop (3), push 4, 5, pop (5), pop (4), pop (2), pop (1). 5 3 4 1 2 cannot: when 5 comes out the stack is [1, 2, 3, 4], and 3 lies beneath 4. As a pattern, the triple 5, 3, 4 is "large, small, medium."
On an empty linked stack,
push 10,push 20,push 30,pop,push 40are applied. What does the stack look like from head to tail? How manymallocand how manyfreecalls have been made so far? What is the total number offreecalls afterstack_clear?Answer
The stack is 40 → 20 → 10 → NULL. Four pushes made four
malloccalls and one pop made onefree.stack_clearreleases the remaining three nodes; the total number offreecalls is 4, equal to the number ofmalloccalls.9 pushes are made onto an empty growable-array stack of capacity 1, doubling the capacity each time it fills. How many enlargements happen, how many items are copied in total, and what is the final capacity?
Answer
The enlargements happen at the 2nd, 3rd, 5th, and 9th pushes, at capacities 1, 2, 4, and 8: 4 enlargements. The number of items copied is 1 + 2 + 4 + 8 = 15 (less than 2n = 18). The final capacity is 16.
In the linked pop, the line
free(old);is moved before the line*x = old->data;. The program often works correctly in tests. Why is it wrong all the same?Answer
After
free,oldis a dangling pointer and readingold->datais undefined behavior. Because released memory is not given to another use immediately, the old value often stays in place; that is why the tests pass. The value is corrupted when anothermallocintervenes or when the allocator writes its own bookkeeping into the block.With the multiple-stack structure for m = 12, n = 3 in its initial state, how many
push(1, ·)calls in a row succeed? What doespop(0, &x)return in the meantime?Answer
Stack 1 uses cells 4–7; four pushes succeed while
top[1]goes from 3 to 7, and the fifth is rejected becausetop[1] == boundary[2](7 == 7). Stack 0 is empty (top[0] == boundary[0]= −1);pop(0, &x)returnsfalse.Two stacks in one array (
M= 10) start empty; 4 items are pushed onto stack 1 and 6 onto stack 2. What does the nextpush(1, x)return? Why?Answer
top1= 3 andtop2= 4. Becausetop1 + 1 == top2is true, the array is full and the call returnsfalse. All ten cells are occupied.If the capacity were raised by 10 cells each time instead of being doubled, what would the total cost of n pushes be?
Answer
There would be about n/10 enlargements, each copying all the current items: 10 + 20 + … ≈ n²/20. The total cost is Θ(n²) and the amortized cost per push is Θ(n). For an amortized O(1), the capacity must grow by a constant factor.
6.16Further reading
- E. Horowitz, S. Sahni, and S. Anderson-Freed, Fundamentals of Data Structures in C (2nd ed.), Sections 3.1–3.2, 3.7, and 4.3: the source of the array stack, dynamic-array stack, multiple-stack, and linked-stack code these notes follow.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (3rd ed.), Section 10.1 and Chapter 17: defines the stack briefly in pseudocode; gives the amortized analysis of dynamic tables in detail with the aggregate, accounting, and potential methods.
- R. Sedgewick, Algorithms in C, Parts 1–4, Chapter 4: treats the stack in C as an example of an abstract data type, with the separation of interface and implementation.
- D. E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, Sections 2.2.1–2.2.2: studies sequential implementations of stacks, the shifting management of multiple stacks, and the permutations obtainable with a stack, with exercises.
6.17References
- E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2nd ed., Sections 3.1–3.2, 3.7, and 4.3.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, Section 10.1 (stacks) and Chapter 17 (amortized analysis).
- R. Sedgewick, Algorithms in C, Parts 1–4, 3rd ed., Addison-Wesley, Chapter 4.
- D. E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed., Addison-Wesley, 1997, Sections 2.2.1–2.2.2.
Related pages: Chapter 6 slides · © Sercan Külcü. All rights reserved.