STACKS AND QUEUES Flashcards
What is a stack?
A stack is a LIFO data structure of items such that items can be inserted and removed only at one end.
Stacks allows access to only one item at a time.
What are the different uses of stacks?
- Evaluate arithmetic expressions even with lots of parentheses
- Traversing binary trees, searching vertices of a graph,
-Programming languages and compilers:
method calls are placed onto a stack (call=push, return=pop)
compilers use stacks to evaluate expressions
-Matching up related pairs of things:
find out whether a string is a palindrome
convert “infix” expressions to pre/postfix
-Sophisticated algorithms:
many programs use an “undo stack” of previous operations
What are the two ways of implementing a stack
Using an array
Using a linked list
What are the basic stack operations
Push - place an item on the stack
Peek - Look at the item on top of the stack, but do not remove it
Pop - Look at the item on top of the stack and remove it
What are the two stack errors that can occur
Underflow: trying to pop (or peek at) an empty stack
Overflow: trying to push onto an already full stack
-For underflow, you should throw an exception. If you don’t catch it yourself, Java will throw an ArrayIndexOutOfBounds exception.
-For overflow, you could do the same things
Or, you could check for the problem, and copy everything into a new, larger array
What is a queue
It is an abstract data type or a linear data structure that stores the elements sequentially. It uses the FIFO approach (First In First Out) for accessing elements
What are the applications of queues
Operating systems:
queue of print jobs to send to the printer
queue of programs / processes to be run
queue of network data packets to send
Programming:
modeling a line of customers or clients
storing a queue of computations to be performed in order
Real world examples:
people on an escalator or waiting in a line
cars at a gas station (or on an assembly line)
List two situations in which a circular queue is considered full
1.
FRONT = 0 && REAR == SIZE - 1
2.
FRONT = REAR + 1
Why would you prefer vectors to arrays when dealing with dynamic structures?
A vector is a dynamic array, whose size can be increased, whereas THE array size can not be changed.
Reserve space can be given for vector, whereas for arrays you cannot give reserved space.
Highlight and explain four applications of the Queue data structure in the field of
computing
When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk Scheduling.
When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes. Examples include IO Buffers, pipes, file IO, etc.
Spooling in printers
Buffer for devices like keyboard
In Networks: Queues in routers/ switches and Mail queues
