# Shared Flashcard Set

## Details

Exam 2
Stacks, Heaps, Recursion, Binary Trees
10
Computer Science
Undergraduate 3
03/30/2012

## Cards Return to Set Details

Term
 Stack ADT
Definition
 An ordered group of homogeneous type where the elements are added and removed from only one end. LIFO. Operation are: Push, Pop, Top, IsEmpty, IsFull.
Term
 Queue ADT
Definition
 An ordered group of homogeneous type where the elements are added at one end and elements are removed from the other end. FIFO. Operations: Enqueue, Dequeue, Push, Pop, Add, Insert.
Term
 Linked List
Definition
 A list in which the order of the components is determined by an explicit link field in each node, rather than by the sequential order of the components in memory.
Term
 Recursion
Definition
 method for defining objects and processes in terms of themselves. There must be a terminal condition and recursive reference
Term
 Heap
Definition
 A complete binary tree, each of whose elements contains a value that is greater than or equal to the value of each of its children.
Term
 Algorithm to Pop item from Stack
Definition
 Pop(item)If stk is notemptyItem = top -> dataTemptop = topTop = top->nextDelete temptopElseUnderflow error
Term
 Algorithm to Deque item in Circular Queue
Definition
 Deque (item)If not emptyItem=data[next(head)]Head=next(head)ElseUnderflow
Term
 Describe how a stack implemented when storing data in array?
Definition
 class StackType{public:StackType();bool IsEmpty() const;bool IsFull() const;void Push(ItemType item);void Pop();ItemType Top () const;private:int top;ItemType items[Max_Items];};
Term
 Limitations into implementations of a Queue using Circular array?
Definition
 IsFull will cause overflowKeep track of the head and tail, the array is empty when head and tail are the same.The space is one less then array.
Term
 Use a stack to evaluate Reverse Polish Notation?
Definition
 Get a token (operator or operand) from the input text.If the token is an operand, push it onto the top of the stack.If the token is an operator, pop the top two operands from the stack, perform the operation, and push the result onto the top of the stack.Repeat 1...3 until there are no more tokens.
Supporting users have an ad free experience!