Data Structures & Algorithms Lecture Notes

18 November 2008 • Stacks

Outline

• Motivation

• Stack properties.

• The stack ADT.

• ADT implementations

• Extension and details.

Lists

• List element access is non-uniform.

  • End elements are accessed in constant time.

  • Middle elements are accessed in linear time.

• Restricting list access to the ends may result a more efficient data structure.

  • And a more limited one.

• Access can be restricted to either or both ends.

  • Assume one end for now.

The Trade-Off

• The trade-off is between restricted access and more efficient element 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 access to one end?

• What happens when list access is restricted to one end?

Properties

• The desirable data-structure properties are:

  • Unrestricted ability to hold varying numbers of elements.

  • The ability to add and remove elements at one end only.

  • Element reference restricted to the element at one end.

  • Sequential access impossible.

• These properties work well together.

Element Ordering

• Restricting element access to one end imposes an order on elements.

  • Elements added more recently come before elements earlier.

• This order is known as last in first out (or lifo) order.

  • Added in the order 1, 2, 3.

  • Removed in the order 3, 2, 1.

The 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.

• Element references are unnecessary.

Adding and Removing Elements

• The pop argument is implicit.

• The before or after question for pushing is irrelevant.

• Pushing with no elements is simple.

Query Operations

• The usual operations: size, empty, ...

  • Query operations may access non-end elements.

• Access the end element (traditionally called top).

  • No element 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-element array represents an (at most) n-element stack.

• One array end (0 or n - 1) represents the stack bottom.

• A variable keeps track of the index of the last top.

  

Stack Push and Pop

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

• There are two error conditions:

  • Pushing on a full array (stack overflow).

  • Popping an empty array (stack underflow).

List-Stack Comparison

	List	Stack
create	O(1)	O(1)
delete	O(1)	O(1)
add	O(n)	O(1)
remove	O(n)	O(1)
traversal	O(1)	na
navigation	O(1)	na
dynamic	No	No

• Both implementations based on arrays.

Dynamic Stacks

• As with lists, array-based stacks are not truly dynamic.

• A dynamic-storage implementation removes the upper limit on element count.

List Representation

• A list implementation of a stack ADT can use either

  1. a list ADT and a reference to the top element, or

  2. an private linked-list implementation.

• Reimplementing a linked-list ADT seems wasteful.

  • Unless the linked-list ADT is doubly linked.

Push And Pop

• Pushing a new element adds it before the stack top.

  • No worries about stack overflow.

• Popping removes the top element.

• The top variable is reset accordingly in either case.

Stack Comparison

	List	Stack	Stack
		(Array)	(List)
create	O(1)	O(1)	O(1)
delete	O(1)	O(1)	O(1)
add	O(n)	O(1)	O(1)
remove	O(n)	O(1)	O(1)
traversal	O(1)	na	na
navigation	O(1)	na	na
dynamic	No	No	Yes

List Overkill

• Lists implement a dynamic stack.

• But lists are overkill (read “have link overhead”).

  • Stacks don’t need lists’ more general before-after relation.

• 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 element copy imposes an O(n) cost.

• The size increase can be additive or multiplicative.

  • The multiplier need not be integral.

Dynamic-Array Costs

• Dynamic arrays make pushes “lumpy.”

  • Most take constant time, except the ones that take O(n).

• Charge each push a penny (a constant amount).

  • After n pushes the copy has been paid for.

  • This is a (really simple) example of amortized analysis.

Stack Comparison

	List	Stack	Stack	Stack
		(Array)	(List)	(DArray)
create	O(1)	O(1)	O(1)	O(1)
delete	O(1)	O(1)	O(1)	O(1)
add	O(n)	O(1)	O(1)	O(1)*
remove	O(n)	O(1)	O(1)	O(1)*
traversal	O(1)	na	na	na
navigation	O(1)	na	na	na
dynamic	No	No	Yes	Yes

* Amortized.

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.

Points to Remember

• 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.