Abstract data types and implementations Flashcards
array advantages
Advantages of contiguously-allocated arrays include:
Constant-time access given the index.
Arrays consist purely of data, so no space is wasted with links or other formatting information.
Physical continuity (memory locality) between successive data accesses helps exploit the high-speed cache memory on modern computer architectures.
dynamic array, how many times will you have to double the size to accommodate n items?
only log_2(n) times
list adt operations
A list contains elements of same type arranged in sequential order
operations performed on the list:
get() – Return an element from the list at any given position.
insert() – Insert an element at any position of the list.
remove() – Remove the first occurrence of any element from a non-empty list.
removeAt() – Remove the element at a specified location from a non-empty list.
replace() – Replace an element at any position by another element.
size() – Return the number of elements in the list.
isEmpty() – Return true if the list is empty, otherwise return false.
isFull() – Return true if the list is full, otherwise return false.
advantages of linked lists
The relative advantages of linked lists over static arrays include:
Overflow on linked structures can never occur unless the memory is actually full.
Insertions and deletions are simpler than for contiguous (array) lists.
With large records, moving pointers is easier and faster than moving the items themselves.
Dynamic memory allocation provides us with flexibility on how and where we use our limited storage resources.
what is the stack principle
Stack principle: LAST IN FIRST OUT
= LIFO
It means: the last element inserted is the first one to be removed
stack adt objects and methods
Objects: a finite ordered list with zero or more elements.
Methods:
push() – Insert an element at one end of the stack called top.
pop() – Remove and return the element at the top of the stack, if it is not empty.
peek() – Return the element at the top of the stack without removing it, if the stack is not empty.
size() – Return the number of elements in the stack.
isEmpty() – Return true if the stack is empty, otherwise return false.
isFull() – Return true if the stack is full, otherwise return false.
implementing a stack as an array
Advantages
best performance
Disadvantage
fixed size
Basic implementation
initially empty array
field to record where the next data gets placed into
if array is full, push() returns false, otherwise adds it into the correct spot
if array is empty, pop() returns null, otherwise removes the next item in the stack
stack push and pop pseudocode using array
Allocate an array of some size (pre-defined)
Maximum 𝑁 elements in stack
Associated with each stack is top
Bottom stack element stored at element 0
for an empty stack, set top to -1
last index in the array is the top
Increment top when one element is pushed, decrement after pop
Push
(1) Increment top by 1.
(2) Set Stack[top] = X
Pop
(1) Set return value to Stack[top]
(2) Decrement top by 1
Implementing a Stack: Linked List advantages and disadvantages
Advantages:
always constant time to push or pop an element
can grow to an infinite size
Disadvantages
the common case is slower
can grow to an infinite size
Implementing a Stack: Linked List basic implementation
list is initially empty
push() method adds a new item to the head of the list
pop() method removes the head of the list
balancing symbols algorithm
(1) Make an empty stack.
(2) Read characters until end of file
i. If the character is an opening symbol, push it onto the stack
ii. If it is a closing symbol, then if the stack is empty, report an error
iii.Otherwise, pop the stack. If the symbol popped is not the
corresponding opening symbol, then report an error
(3) At end of file, if the stack is not empty, report an error
evaluation of postfix expressions algorithm
Given a proper postfix expression:
get the next token
if it is an operand push it onto the stack
else if it is an operator
pop the stack for the right-hand operand
pop the stack for the left-hand operand
apply the operator to the two operands
push the result onto the stack
when the expression has been exhausted, the result is the top (and only element) of the stack
time cost of evaluating a postfix expression
The time to evaluate a postfix expression is 𝑂(𝑛)
Infix to Postfix Conversion
Operands: add to the output expression
Open parenthesis: push onto stack
Close parenthesis: pop stack symbols until an open parenthesis appears
Operators:
compare on stack and off stack precedence, except open parenthesis
Pop all stack symbols until a symbol of lower precedence appears. Then push the operator
End of input: Pop all remaining stack symbols and add to the output expression
queue adt Basic operations:
enqueue: insert an element at the rear of the list
dequeue: delete the element at the front of the list
First-in First-out (FIFO) list
