Search for notes by fellow students, in your own course and all over the country.
Browse our notes for titles which look like what you need, you can preview any of the notes via a sample of the contents. After you're happy these are the notes you're after simply pop them into your shopping cart.
Document Preview
Extracts from the notes are below, to see the PDF you'll receive please use the links above
2/27/2015
STACK & QUEUE VS
...
STACKS AND QUEUES
Stack – a container that allows push and pop
Queue - a container that allows enqueue and dequeue
No concern on implementation details
...
THE STACK ADT
STATIC AND DYNAMIC STACKS
Think of a spring-loaded plate or paper dispenser
Static Stacks
The Stack ADT stores arbitrary objects
Insertions and deletions follow the last-in first-out scheme
Main stack operations:
push(object): inserts an element
object pop(): removes the last inserted element
Fixed size
Can be implemented with an array
Dynamic Stacks
Grow in size as needed
Can be implemented with a linked list
1
2/27/2015
STACK INTERFACE IN C++
EXCEPTIONS
Auxiliary stack operations:
Attempting the execution of an operation of ADT may sometimes cause an error
condition, called an exception
object top(): returns the last inserted element without removing it
integer size(): returns the number of elements stored
Boolean isEmpty(): Returns true if the stack is empty
...
Otherwise, returns false
Exceptions are said to be “thrown” by an operation that cannot be executed
In the Stack ADT, operations pop and top cannot be performed if the stack is empty
...
)
A simple way of implementing the Stack ADT uses an array
The array storing the stack elements may become full
We add elements from left to right
A push operation will then throw a StackFull exception
A variable keeps track of the index of the top element
Limitation of the array based implementation
Not intrinsic to the Stack ADT
3
2/27/2015
SAMPLE DEFINITION FOR A STACK
ARRAY-BASED STACK IN C++
template
class ArrayStack {
private:
myStack[];
// array holding the stack
int cap;
// capacity
int t;
// index of top element
public:
// constructor given capacity
ArrayStack( int c) {
……
...
h>
#include "intstack
...
\n";
}
else
{
top++;
stackArray[top] = num;
}
}
4
2/27/2015
SAMPLE DEFINITION OF FUNCTION POP()
void numStack::pop(int &num)
{
if (isEmpty())
{
cout << "The stack is empty
...
#include
h“
void main(void)
{
numStack stack(5);
int catchVar;
cout << "Pushing
stack
...
push(10);
cout << "Pushing
stack
...
push(20);
cout << "Pushing 25\n";
stack
...
\n";
stack
...
pop(catchVar);
cout << catchVar << endl;
stack
...
pop(catchVar);
cout << catchVar << endl;
stack
...
25
20
15
10
5
}
OTHER EXAMPLES IN C++
ArrayStack
// A = [ ], size = 0
A
...
push(13);
// A = [7, 13*], size = 2
cout << A
...
pop(); // A = [7*], outputs: 13
APPLICATION OF STACKS: INFIX EXPRESSIONS
An infix expression is what we typically use in arithmetic (or algebra), where an operator (+,
–, *, etc
...
For example, a + b, or a + b * c (multiply first before add due to higher precedence)
(a + b) * c (use parentheses to alter precedence)
A
...
top() << endl;
// A = [7, 9*], outputs: 9
they are harder for the computer to process and evaluate
...
top() << endl; A
...
push("Bob");
// B = [Bob*], size = 1
B
...
top() << endl; B
...
push("Eve");
// B = [Bob, Eve*], size = 2
6
2/27/2015
APPLICATION OF STACKS: POSTFIX
EXPRESSIONS
THE IDEA OF CONVERTING INFIX TO POSTFIX
USING A STACK:
Example
...
A postfix expression uses a different convention for writing arithmetic expressions
next token
stack
output
totally doing away the parentheses and making the expressions more efficient to
evaluate by computers
...
A
empty
A
always output operand
For example, ab+, abc*+, ab+c*, respectively, are the postfix expressions
corresponding to the preceding examples
...
incorrect: )(( )){([( )])}
incorrect: ({[ ])}
incorrect: (
7
2/27/2015
EXAMPLE USING VECTORS
PARENTHESES MATCHING ALGORITHM
Algorithm ParenMatch(X,n):
Input: An array X of n tokens, each of which
is either a grouping symbol, a
variable, an arithmetic operator, or a
number
Output: true if and only if all the grouping
symbols in X match
Let S be an empty stack
for i=0 to n-1 do
if X[i] is an opening grouping symbol then
S
...
empty() then
Return false {nothing to match}
If S
...
pop()
If S
...
This mechanism is called First-In-First-Out (FIFO)
...
Vector
Vector
While (cin) {
String line;
Getline(cin, line);
Int pos =0;
Int ts =line
...
fine(“>”,ts+1);
Tags
...
substr(ts,te-ts+1));
Pos=te+1;
Ts=line
...
g
...
Auxiliary data structure for algorithms
Some of the applications are : printer queue, keystroke queue, etc
...
g:
Using std::queue;
// an interface for a queue
// is the queue empty?
const E& front() const throw(QueueEmpty);
// the front element
void enqueue (const E& e);
// enqueue element at rear
void dequeue() throw(QueueEmpty);
// dequeue element at front
};
9
2/27/2015
CIRCULAR QUEUE
CIRCULAR QUEUE
When a new item is inserted at the rear, the pointer to rear moves
upwards
...
Similarly, when an item is deleted from the queue the front arrow
moves downwards
...
Both the front and the rear pointers wrap around to the beginning
of the array
...
It is also called as “Ring buffer”
...
Circular Queue (Normal Queue)
Items can be inserted and deleted from either ends
...
Priority Queue
E
...
policy-based application (e
...
low priority go to the end, high
go to the front)
In a case where you want to sort the queue once in a while,
What sorting algorithm will you use ?
10
2/27/2015
PRIORITY QUEUES
More specialized data structure
...
Items are removed from the front
...
Items are inserted in proper position to maintain the order