System.out.print("Please enter element to find: ");
element = keyboard.nextInt();
for (int i = 0; i < size; i++) {
if (stack[i] == element)
return true;
}
return false;
}
Comparing Stacks & Queues
overview
stacks and queues are similar data structures
they’re different only by how an item is removed first
both can be implemented as arrays or linked lists
advantages
implementing a stack as an array is easy, but implementing a queue as an array is more difficult because you have to dequeue from front and enqueue at end
TL; DR
when you want to be able to add or remove values from any position, arrays are the way to go because any value can be accessed through indexes
disadvantages
main limitations of arrays is that they cannot be extended or shrunk so you want to use an array when you know your max upper limit
TL; DR
if you’re not sure how many values there will be in your data structure, then it’s better to not use an array and stick with a linked list (ergo, queues) because arrays always have a fixed size
examples of stacks
CD storage case
cafeteria tray
batteries in a flashlight
cars in a single car garage
Towers of Hanoi
examples of queues
waiting line for a roller coaster
hamburger processing line at Mickey D’s
vehicles on a toll bridge
luggage checking machine
phone answering system for most big tech companies
Queue Algorithms
shift queues
enqueue operation
save value at first index to item you want to enqueue
increment size
if array fills up, all n elements have to be copied to a new, larger array
dequeue operation
save value at first index
shift all elements left
decrement size
circular queues
advance queue indexes front (to delete an item) and back (to insert an item) by moving them both clockwise around array
Basic Definitions & Phrases
abstract data type\taken straight from the textbook
a data structure is the underlying programming construct used to implement a collection
abstractions
ignores or hides certain details at certain times, e.g. collection is abstraction where details of implementation are hidden
“abstract” in abstract data type
means that there are many different ways of implementing data type
algorithm
step by step instructions on how to execute a program or set of instructions
data structure
memory structure with associated representation mapping, e.g. a collection is a type of data structure that acts as an object that gathers & organizes other objects
a data type is specified by describing both
its set of values & operations used for implementation
implementing an abstract data type proceeds in 2 stages
declaring necessary variables of data types
writing methods & procedures to implement operations of data for given data types
TO NOTE
Although stack and queues have been implemented using an array - these ADTs are not accessed as an array. No actual code for a queue on this test; but you should be able to write an algorithm to demonstrate the concept of a queue.