Mastering Algorithms With C - Kyle Loudon [47]
Function calls in C
An essential part of modular programming. When we call a function in a C program, an activation record containing information about the call is pushed onto a stack called the program stack. When a function terminates, its activation record is popped off the stack. A stack is the perfect model for this because when functions call one another, they return in the opposite order as they were called.
Abstract stack machines
An abstraction used by compilers and hand-held calculators to evaluate expressions (see the example in Chapter 9).
Description of Stacks
The distinguishing characteristic of a stack is that it stores and retrieves data in a last-in, first-out, or LIFO, manner. This means that the last element placed on the stack is the first to be removed. A convenient way to think of a stack is as a can of tennis balls. As we place balls in the can, the can is filled up from the bottom to the top. When we remove the balls, the can is emptied from the top to the bottom. Furthermore, if we want a ball from the bottom of the can, we must remove each of the balls above it. In computing, to place an element on the top of a stack, we push it ; to remove an element from the top, we pop it (see Figure 6.1). Sometimes it is useful to inspect the element at the top of a stack without actually removing it, in which case we peek at it.
Figure 6.1. A stack (1) with some elements already stacked; (2) after pushing 8, 9, and 2; and (3) after popping 2 and 9
Interface for Stacks
Name
stack_init
Synopsis
void stack_init(Stack *stack, void (*destroy)(void *data));
Return Value
None.
Description
Initializes the stack specified by stack. This operation must be called for a stack before the stack can be used with any other operation. The destroy argument provides a way to free dynamically allocated data when stack_destroy is called. For example, if the stack contains data dynamically allocated using malloc, destroy should be set to free to free the data as the stack is destroyed. For structured data containing several dynamically allocated members, destroy should be set to a user-defined function that calls free for each dynamically allocated member as well as for the structure itself. For a stack containing data that should not be freed, destroy should be set to NULL.
Complexity
O (1)
Name
stack_destroy
Synopsis
void stack_destroy(Stack *stack);
Return Value
None.
Description
Destroys the stack specified by stack. No other operations are permitted after calling stack_destroy unless stack_init is called again. The stack_destroy operation removes all elements from a stack and calls the function passed as destroy to stack_init once for each element as it is removed, provided destroy was not set to NULL.
Complexity
O (n), where n is the number of elements in the stack.
Name
stack_ push
Synopsis
int stack_push(Stack *stack, const void *data);
Return Value
0 if pushing the element is successful, or -1 otherwise.
Description
Pushes an element onto the stack specified by stack. The new element contains a pointer to data, so the memory referenced by data should remain valid as long as the element remains in the stack. It is the responsibility of the caller to manage the storage associated with data.
Complexity
O (1)
Name
stack_ pop
Synopsis
int stack_pop(Stack *stack, void **data);
Return Value
0 if popping the element is successful, or -1 otherwise.
Description
Pops an element off the stack specified by stack. Upon return, data points to the data stored in the element that was popped. It is the responsibility of the caller to manage the storage associated with the data.
Complexity
O (1)
Name
stack_ peek
Synopsis
void *stack_peek(const Stack *stack);
Return Value
Data stored in the element at the top of the stack, or NULL if the stack is empty.
Description
Macro that evaluates to the data stored in the element