Implementation and Analysis of Stacks
The structure Stack is the
stack data structure . One way to implement a stack is as a linked list. A
simple way to do this is to typedef Stack
to List (see Example 6.1). In addition to simplicity,
using a typedef has the benefit of making the stack somewhat
polymorphic. Informally, polymorphism is a principle normally associated with object-oriented
languages that allows an object (a variable) of one type to be
used in place of another. This means that because the stack is a
linked list, and hence has the same properties as a linked list, we
can use linked list operations on it in addition to those of a stack.
Thus, the stack can behave like a linked list when we want it
to.
As an example, suppose we want to traverse the elements of a stack, perhaps so we can display them or determine whether a specific element resides in the stack. To do this, we get the element at the head of the list using list_head and traverse the list using list_next. Using only stack operations, we would have to pop the elements one at a time, inspect them, and push them onto another stack temporarily. Then, after accessing all of the elements, we would need to rebuild the original stack by popping the elements off the temporary stack and pushing them back onto the original one. This method would be less efficient and undoubtedly would look less than intuitive in a program.
/***************************************************************************** * * * ------------------------------- stack.h -------------------------------- * * * *****************************************************************************/ #ifndef STACK_H #define STACK_H #include <stdlib.h> #include "list.h" /***************************************************************************** * * * Implement stacks as linked lists. * * * *****************************************************************************/ typedef List Stack; /***************************************************************************** * * * --------------------------- Public Interface --------------------------- * * * *****************************************************************************/ #define stack_init list_init #define stack_destroy list_destroy int stack_push(Stack *stack, const void *data); int stack_pop(Stack *stack, void **data); #define stack_peek(stack) ((stack)->head == NULL ? NULL : (stack)->head->data) #define stack_size list_size #endif
stack_init
The stack_init operation initializes a stack so that it can be used in other operations (see Example 6.1). Since a stack is a linked list and requires the same initialization, stack_init is defined to list_init.
The runtime complexity of stack_init is the same as list_init, or O (1).
stack_destroy
The stack_destroy operation destroys a stack (see Example 6.1). Since a stack is a linked list and requires being destroyed in the same manner, stack_destroy is defined to list_destroy.
The runtime complexity of stack_destroy is the same as list_destroy, or O (n), where n is the number of elements in the stack.
stack_ push
The stack_ push operation pushes
an element onto the top of a stack by calling
list_ins_next to insert an element pointing to
data at the head of the list (see Example 6.2).
The runtime complexity of stack_ push is the same as list_ins_next, or O (1).
stack_ pop
The stack_ pop operation pops an
element off the top of a stack by calling
list_rem_next to remove the element at the head of the list (see
Example 6.2). The
list_rem_next operation sets
data to point to the data from the
element removed.
The runtime complexity of stack_ pop is the same as list_rem_next, or O (1).
stack_ peek, stack_size
These macros implement two simple stack operations
(see Example 6.1). The
stack_ peek macro provides a way to inspect the
element at the top of a stack without actually popping it, and
stack_size evaluates to the size of a stack.
Both of these operations work by accessing members of the
Stack structure.
The runtime complexity of these operations is O (1) because accessing members of a structure is a simple task that runs in a constant amount of time.
/*****************************************************************************
* *
* ------------------------------- stack.c -------------------------------- *
* *
*****************************************************************************/
#include <stdlib.h>
#include "list.h"
#include "stack.h"
/*****************************************************************************
* *
* ------------------------------ stack_push ------------------------------ *
* *
*****************************************************************************/
int stack_push(Stack *stack, const void *data) {
/*****************************************************************************
* *
* Push the data onto the stack. *
* *
*****************************************************************************/
return list_ins_next(stack, NULL, data);
}
/*****************************************************************************
* *
* ------------------------------ stack_pop ------------------------------- *
* *
*****************************************************************************/
int stack_pop(Stack *stack, void **data) {
/*****************************************************************************
* *
* Pop the data off the stack. *
* *
*****************************************************************************/
return list_rem_next(stack, NULL, data);
}