Shared Flashcard Set

Details

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

Additional Computer Science Flashcards

 


 

Cards

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 notempty
Item = top -> data
Temptop = top
Top = top->next
Delete temptop
Else
Underflow error
Term
Algorithm to Deque item in Circular Queue
Definition
Deque (item)
If not empty
Item=data[next(head)]
Head=next(head)
Else
Underflow
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 overflow
Keep 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!