Data Structures & Algorithms Lecture Notes

6 October 2010 • Stacks

---

Outline

Motivation Stack properties. The stack ADT. ADT implementations. Extension and details.

Lists

• List value access is non-uniform.

  

  • End values are accessed in constant time.
  • Middle values are accessed in linear time.
• Restricting list access to the ends may result a more efficient data structure.
  • And a more limited one.

The Trade-Off

• The trade-off is between restricted access and more efficient value management.
  • Lists trade off unrestricted access for less efficient management.
• How does the trade-off work in the other direction?
  • What do we gain by restricting list access to the ends?
• Access can be restricted to either or both ends.
  • Assume one end for now.

ADT Properties

• The desirable ADT properties are:
  • Unrestricted ability to hold varying numbers of values.
  • The ability to add and remove values at one end only.
  • Value reference restricted to the value at one end.
  • Sequential access impossible.
• These properties work well together.

The Stack ADT

The maintenance operations are create and delete. The manipulation operations are add and remove. “Add” is traditionally called push. “Remove” is traditionally called pop. Value references are unnecessary. Although they can be provided.

Adding and Removing Values

• The pop argument is implicit.
• The before or after question for pushing is irrelevant.
• Pushing with no value is simple.

  

Query Operations

• The usual operations: size, empty, ...
  • Query operations may access non-end values.
  • find() for example.
• Access the end value (traditionally called top).
  • No value references required.
• No traversal or navigation operations.

Stack ADT Implementations

• Stack ADTs can be array-based or based on dynamic storage.
• Dynamic storage implementations can be direct or based on other dynamic data structures.
  • Using a linked list to implement a stack, at high overhead.
• There are other implementation techniques.
  • Adapting an existing data structure as a stack, for example.

Array Representation

• An n-value array represents an (at most) n-value stack.
• One array end (0 or n - 1) is the stack bottom.
• A variable keeps track of the stack-top index.

  

Stack Push and Pop

• Push and pop are simple constant-time operations with a minimum of parameters.

  class Stack<V> {
    void push(V v) { ... }
    V pop() { ... }
    }
  

• There are two error conditions:
  • Pushing into a full array (stack overflow).
  • Popping from an empty array (stack underflow).

List-Stack Comparison

		List		Stack
create		fast		fast
delete		fast		fast
add		slow		fast
remove		slow		fast
traversal		fast		na
navigation		slow		na
dynamic		no		no

• Both implementations based on arrays.
  Fast: at most one value involved.
  Slow: potentially all values involved.
  Na: not applicable.

Dynamic Stacks

• As with lists, array-based stacks are not dynamic.
• A dynamic-storage implementation removes the upper limit on value count.

List Implementation

• A list-implemented stack ADT can use either
  1. a list ADT and a top-value reference, or
  2. an private linked-list implementation.
• A private linked list seems wasteful.
  • Unless the linked-list ADT is doubly linked.

  

Push And Pop

• Pushing a new value adds it before the stack top.
  • No worries about stack overflow.
• Popping removes the top value.
• The top variable is reset in either case.

  class Stack<V>
    // should have error checking.
    void push(V v) { 
      s.addBefore(s.head(), v) }
    V pop() { return s.remove(s.head()) }
    private LinkedList<V> s;
  

Stack Comparison

		List		Stack		Stack
				(Array)		(List)
create		fast		fast		fast
delete		fast		fast		fast
add		slow		fast		fast
remove		slow		fast		fast
traversal		fast		na		na
navigation		slow		na		na
dynamic		no		no		yes

• Fast: at most one value involved.
  Slow: potentially all values involved.

List Overkill

• Using lists to implement stacks is overkill.
  • Stacks don’t need lists’ more general before-after relation.
  • Links take up space, but aren’t useful.
• Arrays are a closer match to stacks then are lists.
  • But how can arrays provide dynamic stacks?

Dynamic-Array Stacks

• An array can be made dynamic by allocating a new one when the old one’s full.
  • This also works in the other direction when the array’s half empty
  • The smaller array wastes less space.
• The size increase can be additive or multiplicative.
  • The multiplier need not be integral.

Dynamic Example

Pushing 4 causes a stack overflow. Create a new array, twice as big. Copy values from the old to the new array. Replace old with the new array. Do the push.

Dynamic-Array Costs

• Dynamic arrays make pushes and pops “lumpy.”
  • Most pushes and pops touch one value, except the ones that create a new array.
• New arrays touch all the values.
  • But this occurs no more than 1 out of n/2 times for an n-value array.

  

Stack Comparison

		List		Stack		Stack		Stack
				(Array)		(List)		(DArray)
create		fast		fast		fast		fast
delete		fast		fast		fast		fast
add		slow		fast		fast		fast*
remove		slow		fast		fast		fast*
traversal		fast		na		na		na
navigation		fast		na		na		na
dynamic		No		No		Yes		Yes

* Most of the time, slow occasionally.

Value Ordering

• Restricting value access to one end imposes an order on values.

  Values added more recently come before values earlier. This order is known as last in first out (or lifo) order.

Stacks Everywhere

• Most language run-time systems provide stacks, even if the language doesn’t.
  • And sometimes even when the language run-time doesn’t (e.g. Smalltalk).
• And most CPUs provide instruction-level support for stacks.
  • Making them fast and efficient.

Activation Records

int f() int i, j double x // whatever	Given a function with local variables, where are the local variables stored?
	In a storage block called the activation record.

Activation Stack

• Procedures return in reverse of their calling order.

  a()
    a() calls b()
      b() calls c()
        c() returns
      b() returns
    a() returns
  

  • Procedures return in lifo order.
• Use a stack, the activation (or run-time) stack.

Array-Reverse Example

void reverse(T a[], int n, int i)
  if i < n
    T c = a[i]
    reverse(a, n, i + 1)
    a[n - (i + 1)] = c

Summary

• Know a data structure’s strengths and weaknesses.
  • Exploit strengths and avoid weaknesses.
• Stacks exploit linked lists’ constant-time end access.
• Restricted capabilities should lead to more efficient and simpler implementations.
  • If not, something may be wrong somewhere.

References

• Stacks and Queues, Chapter 16 in Data Structures & Problem Solving Using Java, fourth edition, by Mark Weiss, Addison Wesley, 2010.
• Stacks, Queues, and Deques, Chapter 5 in Data Structures & Algorithms in Java, fifth edition, by Michael Goodrich and Roberto Tamassia, Wiley, 2010.

Credits

• Acrobat stacking by Brent and MariLynn under an AT NC Creative Commons license.
• Spring/Summer Stack by msbhaven under an AT Creative Commons license.

---

This page last modified on 6 October 2010.