13.1 Stacks
| I l @ ve RuBoard |
| A stack is an algorithm for storing data. Data can be put in the stack using a push operation . The pop operation removes the data. Data is stored in last-in-first-out (LIFO) order. You can think of a stack as a stack of papers. When you perform a push operation, you put a new paper on top of the stack. You can push as many times as you want; each time the new data goes on top of the stack. You get data out of a stack using the pop operation, which takes the top paper off the stack and gives it to the caller. Suppose you start with an empty stack and put three elements on it, 4, 5, and 8, using three push operations. The first pop would return the top element, 8. The elements 4 and 5 remain in the stack. Popping again gives you 5. You then push another value, 9, on the stack. Popping twice gives you the numbers 9 and 4, in that order. This is illustrated by Table 13-1. Table 13-1. Stack operation
13.1.1 Designing a StackThe easiest way to design a stack is to let someone else do it. C++ comes with a very nice stack class as part of the Standard Template Library (See Chapter 25.) But to learn about simple classes, in this chapter we are going to create our own. We start a stack design by designing the data structure. This structure will need a place to put the data (called data ) and a count of the number of items currently pushed on the stack (called count ): const int STACK_SIZE = 100; // Maximum size of a stack // The stack itself struct stack { int count; // Number of items in the stack int data[STACK_SIZE]; // The items themselves }; Next you need to create the routines to handle the push and pop operations. The push function stores the item on the stack and then increases the data count: inline void stack_push(struct stack& the_stack, const int item) { assert((the_stack.count >= 0) && (the_stack.count <= sizeof(the_stack.data)/sizeof(the_stack.data[0]))); the_stack.data[the_stack.count] = item; ++the_stack.count; }
Popping simply removes the top item and decreases the number of items in the stack: inline int stack_pop(struct stack&the_stack) { // Stack goes down by one --the_stack.count; assert((the_stack.count >= 0) && (the_stack.count <= sizeof(the_stack.data)/sizeof(the_stack.data[0]))); // Then we return the top value return (the_stack.data[the_stack.count]); } There is one item you've overlooked: initializing the stack. You must set up the stack before you can use it. Keeping with the spirit of putting everything in a stack_ xxxx routine, create the stack_init function: inline void stack_init(struct stack& the_stack) { the_stack.count = 0; // Zero the stack } Notice that you don't need to zero the data field in the stack, since the elements of data are overwritten by the push operation. You are now finished. To actually use the stack, you declare it and initialize it, then you can push and pop to your heart's content (or at least within the limits of the stack): stack a_stack; // Declare the stack stack_init(a_stack); // Initialize the stack // Stack is ready for use Example 13-1 contains a complete implementation of the structure version of the stack and a short test routine. Example 13-1. stack_s/stack_s.cpp /******************************************************** * Stack * * A set of routines to implement a simple integer * * stack. * * * * Procedures * * stack_init -- initalize the stack. * * stack_push -- put an item on the stack. * * stack_pop -- remove an item from the stack. * ********************************************************/ #include <assert.h> #include <cstdlib> #include <iostream> const int STACK_SIZE = 100; // Maximum size of a stack // The stack itself struct stack { int count; // Number of items in the stack int data[STACK_SIZE]; // The items themselves }; /******************************************************** * stack_init -- initialize the stack. * * * * Parameters * * the_stack -- stack to initalize * ********************************************************/ inline void stack_init(struct stack& the_stack) { the_stack.count = 0; // Zero the stack } /******************************************************** * stack_push -- push an item on the stack. * * * * Warning: We do not check for overflow. * * * * Parameters * * the_stack -- stack to use for storing the item * * item -- item to put in the stack * ********************************************************/ inline void stack_push(struct stack& the_stack, const int item) { assert((the_stack.count >= 0) && (the_stack.count < sizeof(the_stack.data)/sizeof(the_stack.data[0]))); the_stack.data[the_stack.count] = item; ++the_stack.count; } /******************************************************** * stack_pop -- get an item off the stack. * * * * Warning: We do not check for stack underflow. * * * * Parameters * * the_stack -- stack to get the item from * * * * Returns * * The top item from the stack. * ********************************************************/ inline int stack_pop(struct stack& the_stack) { // Stack goes down by one --the_stack.count; assert((the_stack.count >= 0) && (the_stack.count < sizeof(the_stack.data)/sizeof(the_stack.data[0]))); // Then we return the top value return (the_stack.data[the_stack.count]); } // A short routine to test the stack int main( ) { struct stack a_stack; // Stack we want to use stack_init(a_stack); // Push three value on the stack stack_push(a_stack, 1); stack_push(a_stack, 2); stack_push(a_stack, 3); // Pop the item from the stack std::cout << "Expect a 3 ->" << stack_pop(a_stack) << '\n'; std::cout << "Expect a 2 ->" << stack_pop(a_stack) << '\n'; std::cout << "Expect a 1 ->" << stack_pop(a_stack) << '\n'; return (0); } |
| I l @ ve RuBoard |
EAN: 2147483647
Pages: 364