Stacks

From MMAE

Stacks are a Last in First Out (LIFO) data structure. They are restricted to two operations, push and pop. Push adds an item to the top of a stack while Pop removes and returns the item at the top of the stack.

Contents 1 Implementations 1.1 Arrays 1.2 Linked List 2 Uses 3 Analysis of Stack Operations 4 Tracing

[edit] Implementations

Stacks can be implemented using either an Array or using a linked list. In either implementation you should create separate push and pop operations.

[edit] Arrays

• Set a max size of the stack.

[edit] Linked List

Using a Linked List there is no max data size of the stack.

• The pointer to the first node is known as the stacktop.
• Push
  • Create a new node
  • Set next to stacktop
  • Set stacktop to be the new node.
• Pop
  • Return error if stack is empty.
  • Create a temp pointer to stacktop
  • Set stacktop to be temp->next
  • Temporarily store the value in temp
  • Free temp and return the value that was in it.

[edit] Uses

• RPN (postfix) to infix conversions
• Evaluating RPN (postfix) expressions
• Functions are usually called utilizing a stack frame. When a function returns it is popped off the stack.
• Large number addition

[edit] Analysis of Stack Operations

• Pushing and Popping on a linked list - O(1)

[edit] Tracing

On the test you may be asked to trace a series of push and pop operations.