What real world uses of the "Stack" object (.Net) have you used

We have all read about or heard about the stack class, but many of us have probably never found a reason to us开发者_StackOverflow中文版e the LIFO object. I am curious to hear of real world solutions that used this object and why.

http://msdn.microsoft.com/en-us/library/system.collections.stack.aspx

I recently saw an example where a programmer used a stack to keep track of his current position while traversing a hierarchical data source. As he moved down the hierarchy, he pushed his position identifier on to the stack and as he moved back up he popped items off the stack. I thought this was a very efficent way to keep track of his current position in a mamoth hierarchy. I had never seen this before.

Anyone else have any examples?

I've used them to keep track of Undo and Redo actions.

I use an interface something like this:

interface ICommand
{
    void Execute();
    void Undo();
    string Description { get; }
}

Undo and Redo are both of type Stack<ICommand>. Then I create a concrete class for a given action. In the class's constructor, I pass in any information I'd need to hold on to. Execute does the action initially, and also redoes it; Undo undoes it, obviously. It works like this:

• Undo an action: Pop the Undo stack and add to the Redo stack.
• Redo an undone action: Pop the Redo stack and add to the Undo stack again.
• Perform a new action: Add to the Undo stack and clear the Redo stack (since the state is no longer consistent).

I found that you have to take care that you're really undoing what was done. For instance, say you have a UI with two listboxes, and each has five items in it. Your action might be to click a button to move everything on the left list to the right list (so it now has ten, and the left list has zero).

The undo action is not to move everything back; the undo action is to move back only the five you actually moved, and leave the others.

Stacks are used whenever a stored procedure / sub-routine is called to store local variables and return address.

Stacks are used for expression evaluation (eg in a calculator, or your compiler), first the expression is converted to RPN then a simple stack machine is used to evaluate. This works as follows, when you see an operand push it on the stack. When you see an operator pop operands and evaluate.

example

5 6 + 3 *

steps-
 see 5 push 5
 see 6 push 6
 see + pop 2 times and apply + get 11 push 11
 see 3 push 3
 see * pop 2 times and apply get 33 push 33

result is on the top of the stack.   

If you have a recursive algorithm, you can typically rewrite them using a stack. (since recursive algorithms implicitly already use a stack)

You can validate string inputs that require balanced tokens. Think LISP:

(+ (- 3 2) (+ (+ 4 5) 11))

When you hit an opening paren:

stack.Push("(")

Then when you hit a closing paren:

stack.Pop()

If there are any tokens left in your stack when you're done, it's not balanced.

You can get fancier and validate proper nesting in inputs like HTML. In a highly-contrived example:

//see opening body
stack.Push("body")

//see opening div
stack.Push("div")

//see opening p
stack.Push("p")

///see closing div
if(!stack.Pop().Equal("div")){
    //not balanced
}

I've used stacks for image processing, where the "processing language" must be specified in a URL. A stack-based form lets you represent a tree of operations in an easy-to-parse, easy-to-think-about form.

See:

http://www.hackification.com/2008/10/29/stack-based-processing-part-1/

and

http://www.hackification.com/2008/10/29/stack-based-processing-part-2/

In one real-life use, a postscript generator class has a "current_font" state, used as the font for any operations which draw text. Sometimes a function needs to set the font temporarily, but then have it go back to the way it was. We could just use a temporary variable to save and restore the font:

def draw_body
  old_font = ps.get_font
  ps.set_font('Helvetica 10')
  draw_top_section
  draw_bottom_section
  ps.set_font(old_font)
end

But by the third time you've done that you'll want to stop repeating yourself. So let's let the ps object save and restore the font for us:

class PS

  def save_font
    old_font = get_font
  end

  def restore_font
    set_font(old_font)
  end

end

Now the caller becomes:

def draw_body
  ps.save_font
  ps.set_font('Helvetica 10')
  draw_top_section
  draw_bottom_section
  ps.restore_font
end

That works fine, until we use the same pattern inside one of the subroutines called by draw_page:

def draw_top_section
  ps.save_font
  ps.set_font('Helvetica-bold 14')
  # draw the title
  ps.restore_font
  # draw the paragraph
end

When draw_top_section calls "save_font", it clobbers the font that was saved by draw_page. It's time to use a stack:

def PS

  def push_font
    font_stack.push(get_font)
  end

  def pop_font
    set_font(font_stack.pop)
  end

end

And in the callers:

def draw_top_section
  ps.push_font
  ps.set_font('Helvetica-bold 14')
  # draw the title
  ps.pop_font
  # draw the body
end

There are further refinements possible, such as having the PS class automatically save and restore the font, but it's not necessary to go into those to see the value of a stack.

I find stacks quite useful in multithreaded aplications to keep track of statuses in an inverse-time fashion...

Every thread puts a status message in a synchronized shared stack and you have kind of a "breadcrumb" of what has happened.

Not quite .NET but... it's my oppinion =)

Here's an implementation of a deep compare where a Stack is used to keep track of the path to the current object being compared.

C# implementation of deep/recursive object comparison in .net 3.5

I've also used it in similar types of code working with generating xpath statements for particular xml nodes.

To provide a specific example to illuminate what other people are commenting on: to implement a Z-machine interpreter three different stacks should be used. A call stack, and a couple different kinds of object stacks. (The specific requirements can be found here.) Note that, like all of these examples, while using a stack isn't strictly required, it is the obvious choice.

The call stack keeps track of recursive calls to subroutines, while the object stack is used to keep track of internal items.

In a computer graphics class (not .NET) we used a Stack to keep track of objects that were drawn on the screen. This allowed all the objects to be redrawn on the screen for each refresh as well as keeping track of the order or "z-layer" of each object, so when they moved they could overlap other objects.