Dark Bit Factory & Gravity

PROGRAMMING => Coding tutorials => Topic started by: rdc on January 17, 2010

Title: FB Data Structures: Stack Concepts
Post by: rdc on January 17, 2010

The stack is one of the most useful of the data structures and at the same time, one of the easiest to understand. A stack is a collection of items, a list, that is accessed from one end called the *Top*. To put an item on the stack, an operation called a *Push* is executed that puts an item on the stack. If the stack is empty, the item is placed at the top of the stack. If the stack is not empty, the new item is placed at the top of the stack, and the other items are "behind" the top item. That is, the last item placed on the stack is the first item to be removed from the stack. A stack is *LIFO* data structure: Last In First Out. To retrieve an item from the stack an operation called a *Pop* is executed that removes the item at the top of the stack and makes the next item the new Top, or if the stack does not contain any items, sets the stack to empty.

Stack Dynamics

Code: [Select]

----- = Top
stack = empty

A stack starts out as empty, that is, it has no items in the list. The empty condition is an important concept of the stack, since you obviously can't Pop an item from a stack that does not contain any items. Any implementation of a stack will need to keep track of the number of items in a stack and signal when the stack is empty. On an empty stack, the Top is undefined, that is, since there are no items on the stack, the Top does not point to any items. In practice, Top is usually set to a marker value like -1, 0, or NULL to indicate the stack does not have a Top index.

Code: [Select]

1 PUSH(item1)

item1 = Top
-----
stack = 1

When the stack is empty, a Push places an item on the stack, sets the number of items on the stack to 1 and sets the Top of the stack to the newly pushed item.

Code: [Select]

1 PUSH(item2)

item2 = Top
item1
-----
stack = 2

A subsequent Push places the new item on "top" of the previous items, making the new item the new top and incrementing the stack count by 1.

Code: [Select]

1 PUSH(item3)
2 PUSH(item4)

item4 = Top
item3
item2
item1
-----
stack = 4

Subsequent pushes will place the items on the stack in the order of the pushes, incrementing the Top and count with each push. You can readily see the LIFO nature of the stack. The last item pushed onto the stack will be the first item removed from the stack with a Pop operation.

Code: [Select]

1 POP() = item4

item3 = Top
item2
item1
-----
stack = 3

When a Pop is executed, the Top item is returned and removed from the stack, the Top is then set to the next item in the list (if any exist) and the count is adjusted. Since item4 was the last item to be placed on the stack, it is the first item to be removed from the stack.

Code: [Select]

1 POP() = item3
2 POP() = item2
3 POP() = item1

----- = Top
stack = empty

Subsequent Pops will remove each top item until the stack is empty.

Code: [Select]

1 POP() = STACKEMPTY

----- = Top
stack = empty

Popping an item from an empty stack should generate an error since the stack has no items to return.

Depending on the implementation of the stack, an additional condition may exist, the upper limit of the stack. If the stack is implemented as a static array, then the array size limits the number of items that can be placed on the stack. If you Push more items onto the stack that the array can hold, a stack full error should be generated on the push operation to signal that the stack is full.

Code: [Select]

1 PUSH(item5) = STACKFULL

item4 = Top
item3
item2
item1
-----
stack = 4 (size = 4)

In the case of a stack full condition, an error should be generated and the stack should remain unchanged.

Example: Matching Parentheses

Parsing data often requires a stack structure, and operations like matching parentheses naturally lend themselves to a stack structure. For example, suppose the following equation needs to be checked to make sure all the parentheses match.

(3 * (4 + 6) / 4 - (4 + 2))

Ignoring the numbers and math operations, we can parse the equation from left to right, looking for matching parenthesis. When we encounter an open paren ( push the paren on the stack. When we encounter a closing paren ) we pop the top item off the stack and check to see if it is open paren. If it is, we have matched a set of parentheses and they are removed from the stack, otherwise the paren is pushed onto the stack for later evaluation. If we get to the end of the expression with no items left on the stack, all the parentheses match. If there are still items left on the stack, or we try to pop an item from an empty stack while evaluating the expression, then the parentheses do not match. The following set of diagrams illustrate the parsing process using a stack.

(3 * (4 + 6) / 4 - (4 + 2))

Code: [Select]

1 PUSH("(")

(     = Top
-----
stack = 1

Since the stack is empty, the first paren we encounter is simply pushed onto the stack since there is nothing yet to compare.

(4 + 6) / 4 - (4 + 2))

Code: [Select]

1 POP() = "(" - Current top is open which does not match next paren.
2 PUSH("(")   - Push popped item back onto stack.
3 PUSH("(")   - Push new paren onto stack.

(     = Top
(     
-----
stack = 2

When we encounter the next paren we need to pop the last element from the stack to see if we have a matching set of parentheses. In this case, the stack contains an open paren (not a closing paren) so we push the paren we popped back onto the stack and then push newly parsed parenthesis onto the stack.

) / 4 - (4 + 2))

Code: [Select]

1 POP() = "(" - Current top is open which does match next paren. Discard both parenthesis.

     
(     = Top
-----
stack = 1

The next paren is closed which matches the top open paren in the stack. Since we have matching parentheses we can discard both leaving the stack with a single open paren.

(4 + 2))

Code: [Select]

1 POP() = "(" - Current top is open which does not match next paren.
2 PUSH("(")   - Push popped item back onto stack.
3 PUSH("(")   - Push new paren onto stack.

(     = Top
(     
-----
stack = 2

The next parenthesis is open which doesn't match the current stack top (an open paren) so both are pushed back onto the stack as in a previous step.

))

Code: [Select]

1 POP() = "(" - Current top is open which does match next paren. Discard both parentheses.

     
(     = Top
-----
stack = 1

Again, we have matching parentheses so we discard both. This leaves one paren on the stack, the original open parenthesis.

)

Code: [Select]

1 POP() = "(" - Current top is open which does match next paren. Discard both parentheses.

     
     
----- = Top
stack = empty

Finally the last parenthesis is parsed which matches the open paren still on the stack. We know all the parenthesis have been matched since the stack is empty.

What would have been the result if the last closed parenthesis in the expression had been omitted? At the end of the expression, the opening paren would still be on the stack indicating that the expression had mismatched parentheses. While this example is a trivial use of a stack, it illustrates the principles of the stack and why it is used in so many applications that requires a last-in first-out structure. A subroutine stack in a programming language, while more complex in its actions, basically follows this same pattern to create and unwind the recursion stack. A macro language that supports macro-expansion has to use a stack structure to unwind nested unexpanded macros properly. And in this example, we can extend the stack to not only handle the parentheses, but to actually solve the equation since the process is much the same as illustrated here.

Next Step: Coding a Stack Object

Conceptually, the stack process is straightforward. The code is also quite straightforward. In the next two tutorials, an array-based and pointer-based stack will be created.

Additional Resources

Stack article on Wikipedia: http://en.wikipedia.org/wiki/Stack_(data_structure)