COP 3540 Data Structures with OOP
Chapter 4
Stacks and Queues
1 / 23
A Different Kind of Structure
 Stacks, queues, and priority queues –
different kinds of storage structures.
 Different data structures have different sets of
problems that they are most suited to
 Consider Arrays – as a data storage structure:
 very useful.
 easy to insert into, delete from, and search for
specific items.
2 / 23
Access (interface)
 Arrays: theoretically, access is immediate via index
or by searching through cells sequentially.
 If ordered, can access more quickly via binary
 Only one item can be accessed.
 ‘That’ is the interface.’
 In abstract data structures (stacks, queues, trees,
priority queues), real access (that is, how do we
get to it…) is:
 defined a bit differently and is
 controlled by an interface that is normally not
visible to the user.
3 / 23
 Stacks - access to only one item at a time.
 Think of a stack of dishes.
 It is a LIFO data structure.
 Extremely useful tool in programming:
 Evaluate parenthesized expressions,
 Evaluate arithmetic expressions even with lots
of parentheses,
 Traversing binary trees,
 Searching vertices of a graph, and much more.
 Consider stacked-based architecture and
calling sequences / return addresses….
4 / 23
 Stacks are conceptual (logical), abstract structures.
 We can envision them.
 Really no such thing as a real stack!
 But we are interested in how we can implement the
logical structure on a machine.
 Basic operations – four. Know these!:
 Push (onto top of stack)
 Pop (top item off of stack)
 Stack overflow (stack full) – cannot push!
• (normally error condition or special processing needed.
Same for underflow…)
 Stack underflow (stack empty) – cannot pop!
 Let’s look at Java Code for a Stack
5 / 23
class StackApp
public static void main(String[] args)
StackX theStack = new StackX(10); // makes new stack of size 10.
//note: argument sent to the Stack object for use by constructor
// note: we DO NOT KNOW how the stack actually looks!!!!!
// that is, we do NOT know what the underlying data structure looks like!!!!!
// push items onto stack
// These are ‘logical’ operations!!!
(How to evaluate??)
while( !theStack.isEmpty() ) // until it's empty, delete item from stack
long value = theStack.pop();
// what is author doing here???
// display it
System.out.print(" ");
} // end while
} // end main()
} // end class StackApp
6 / 23
// demonstrates stacks Note: I have taken liberties with the ‘{‘ to fit this code on one page.
class StackX
private int maxSize;
// size of stack array
private long[] stackArray;
// recall: ‘instance variables’
private int top;
// top of stack
//-------------------------------------------------------------public StackX(int s)
// constructor // (How can you tell this is the Constructor??)
maxSize = s;
// set array size
// Recall: ‘ local variables’ Where are they known??
stackArray = new long[maxSize];
// Create array; ARRAY IS OF ‘LONGS’
//’long’ is a primitive data structure; how longs are implemented and
accessed are defined in system. No need for separate class for this.
top = -1;
// no items yet
} // end StackX()
//-------------------------------------------------------------public void push(long j)
// put item on top of stack
stackArray[++top] = j; // increment top, insert item
//  tell me exactly how this works!!
} // end push()
// How many operators do you see?
//-------------------------------------------------------------public long pop()
// take item from top of stack
return stackArray[top--]; // access item, decrement top
// tell me exactly how this works!!
}// end pop ()
//recall: What is the ‘other kind’ of variable?????
//-------------------------------------------------------------public long peek() {
// peek at top of stack
return stackArray[top];
// when we come into this object, the pointer is
} // end peek()
// pointing to the topmost element.
//-------------------------------------------------------------public boolean isEmpty() { // true if stack is empty
return (top == -1);
// tell me exactly how this works!!
} // end isEmpty()
//-------------------------------------------------------------public boolean isFull() { // true if stack is full
//Ah ha! We see (above) that the Stack is ‘implemented’ as
return (top == maxSize-1);
array! But it doesn’t have to be!!!!!
/ 23
} // end class StackX
// Storage structure transparent to client. Good!!! Why???
 Always check to see if there are items on the stack
before popping the stack or if there is room before
pushing the stack
 isFull?
 isEmpty?
 Appropriate error routines are up to the developer / user
 Best approach: in Push() and Pop(), check for
isEmpty and isFull within these methods.
 Regardless, they need to be specified.
 Go through Reversing a Word routine in book.
 We will look at Delimiter Matching.
8 / 23
Delimiter Matching
 Stacks are used a lot to temporarily store tokens
like a char or parts of arithmetic expressions having
parentheses in them and later retrieve them when
we have a number of delimiters.
 ‘Delimiters’ = normally special characters (e.g. commas,
white space, braces, brackets, parentheses, …)
 They normally set something off or bracket something.
 Delimiters (but not white spaces) must always
‘balance’ – the first right parenthesis balances the
‘most recent’ unbalanced left parenthesis, etc.
9 / 23
Delimiter Matching – more
 Consider: x = (a+b*(c/d**4-e/(2*a)-5)-14.2/g);
 How do you and the machine evaluate this?
 (You will see this again.)
 You absolutely need to know the order of
evaluation of most common operators.
 Note: this ‘order of evaluation’ (operator
precedence) is basic to all programming
10 / 23
Delimiters – the Algorithm
 Algorithm: tries to evaluate as it goes.
 But when it encounters an opening delimiter, it must process
it and may push a token onto a stack only to pop it later.
 When the algorithm encounters closing delimiter or operator
of lesser precedence), the algorithm may
 pop the stack and
 perform the evaluation thus creating a temporary (or partial) value,
 May push temporary result ‘back’ onto stack if more terms follow.
 If no closing delimiter is found (or if unbalanced), syntax error!
 For pairs of delimiters, such as ‘parentheses’ the one opened last 
closed first.
 If different delimiters are used (brackets, parentheses, etc.) then the
correct delimiter must be found, if syntax of the expression is valid.
 Different delimiters? Parentheses; brackets for indexes …
 If syntax is invalid,  compilation error!
 Let’s look at some code.
11 / 23
// Discuss: stack for handling string input / evaluations…
// for I/O
// Discuss each method briefly.
class StackX
private int maxSize;
//Here’s my ‘instance’ data, right?
private char[] stackArray;
//declares a pointer (reference), stackArray, to a char array
private int top;
// where the array itself is not yet allocated / built.
//-------------------------------------------------------------public StackX(int s)
// constructor
// when object of class StackX is created in its client,
maxSize = s;
// BracketChecker, size of the stack is passed to this Constructor
stackArray = new char[maxSize];
// Constructor uses this parameter to determine size of array object.
top = -1;
// Stack object, just created, is empty, so top of stack is set to -1, an invalid array reference.
} // end StackX()
no change
public void push(char j) // put item on top of stack
stackArray[++top] = j;
// Exactly how does this work for first item? Values of top?
}//end push()
//-------------------------------------------------------------public char pop()
// take item from top of stack
return stackArray[top--];
// Note top is decremented AFTER item is popped!
} // end pop()
//-------------------------------------------------------------public char peek()
// peek at top of stack
// note: encapsulation; see stack and
methods that process
return stackArray[top];
} // end peek()
//-------------------------------------------------------------public boolean isEmpty
// cut
off for space…
12 / 23
class BracketChecker {
private String input;
public BracketChecker(String in)
{ input = in; }
//-------------------------------------------------------------public void check() {
int stackSize = input.length();
StackX theStack = new StackX(stackSize);
// input string
// constructor; When object is created, a String is
// passed to it. Becomes value of ‘input.’
// get max stack size. Where does input.length() come from?
// make stack Creates stack object of size stackSize. Do you see???
// Stack (array) is declared to be the size of input string.
// Get chars in turn
// get a char
Where does input.charAt(j) come from?
for(int j=0; j<input.length(); j++) {
char ch = input.charAt(j);
switch(ch) {
case '{':
// opening symbols
case '(':
// push the symbol onto the Stack. Check it out.
case '}':
// closing symbols
case ']':
case ')':
if( !theStack.isEmpty() )
// if stack not empty and came in with ‘closing’ delimiter…
char chx = theStack.pop(); // pop and check
if( (ch=='}' && chx!='{') || ch==']' && chx!='[') || (ch==')' && chx!='(') )
System.out.println("Error: "+ch+" at "+j);
// prematurely empty
System.out.println("Error: "+ch+" at "+j);
default: // no action on other characters. Routine is only looking for delimiters; not evaluating; checking!!
} // end switch
} // end for
// at this point, all characters have been processed
if( !theStack.isEmpty() )
System.out.println("Error: missing right delimiter");
} // end check()
13 / 23
} // end class BracketChecker
class BracketsApp
public static void main(String[] args) throws IOException
String input;
//Notice indentation and scope terminators.
System.out.print ( "Enter string containing delimiters: ");
input = getString(); // read a string from keyboard Note
if( input.equals("") ) // quit if [Enter]
// otherwise, make a BracketChecker
the static method in Main
BracketChecker theChecker = new BracketChecker(input);
// OK. Now, this creates an object of type BracketChecker. Object name is theChecker.
// Pass the string, ‘input’ to the Constructor.
theChecker.check(); // calls check() within theChecker.
} // end while
// the check() method
} // end main()
//-------------------------------------------------------------public static String getString() throws IOException
InputStreamReader isr = new InputStreamReader(;
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
} // end getString()
//-------------------------------------------------------------} // end class BracketsApp // note the DESIGN! Note how all of these objects have their
// responsibilities and how they collaborate to provide the needed functionality; reusability too.
14 / 23
Stack as a Conceptual Aid
 The notion (vision) of a stack is simple.
 Once a Stack (very reusable) is set up, you don’t
have to keep track of indices
 But there is limited access to the stack elements
via push() and pop()
 Efficiency:
Push() and pop() take O(1) time – a constant. Why??
No dependency on number of items in stack.
No comparisons or moves necessary.
For many applications, this is a very convenient logical
data structure.
15 / 23
 A FIFO data structure; is a ‘line.’
 A Stack is a LIFO data structure.
 What is a FISH data structure?
 A queue
 another conceptual data structure (logical data structure)
 can be implemented using an array, linked list or other structure.
 Queues: VERY useful for many different applications.
 Typically used to model waiting lines, such as planes waiting to
take off; waiting lines at McDonalds, etc. and much more!
 Many queues in your operating system:
• Print queues
• Job queues
• Ready queues
• Keyboard queues – data not lost; just ‘queued up.’
16 / 23
Queues - terminology
 Queues
 data entered in one end
 Data extracted from the other end, as envisioned.
 Thus, our queue operations are
 insert() and remove()
• insert() at the rear (back or tail) of the queue
• remove() at the front (head) of the queue.
 These are reasonably common terms.
 Rear of queue is the tail (back or tail or end)
 Front of queue is head.
 We will use: insert, remove, front and rear.
17 / 23
Queues – more
 Potential error conditions
 Attempt to remove an item from an empty queue??
• Want ‘empty queue’ message returned.
 Attempt to insert an item into a ‘full queue’
• Want full queue message returned.
 As in a Stack, we must ‘create’ the Queue.
 Can also have Circular Queues: extremely useful!
 Must be careful to keep track of the front and rear of the
queue so that they do not wrap!
 Consider: Java code for a Queue.
18 / 23
class QueueApp
public static void main(String[] args)
Queue theQueue = new Queue(5);
// queue holds 5 items; Creates Queue theQueue and
// passes a 5 as argument to theQueue’s Constructor.
// insert 4 items
// remove 3 items
// (10, 20, 30)
// insert 4 more items
// (wraps around)
while( !theQueue.isEmpty() ) // remove and display all items.
long n = theQueue.remove(); // (40, 50, 60, 70, 80)
System.out.print(" ");
} // end while()
} // end main()
} // end class QueueApp
/ 23
class Queue { // Please note my moving of ‘{‘ and a few other things to poor spots – in the interest of space...
private int maxSize;
private long[] queArray;
// reference to an array of ‘longs.’
private int front, rear, nItems;
public Queue (int s) {
// constructor
 Note: size and structure of queue determined here. User does not
maxSize = s;
// see (or care) how queue is implemented. (See: array here.
queArray = new long[maxSize];
Note: Constructor is passed desired queue size from client.
front = 0;
Note: See instance and local variables??
rear = -1;
Note: Here’s the queue; implemented as an array; front and rear
nItems = 0;
and number of Items setup and initialized.
} // end Constructor
public void insert(long j) { // put item at rear of queue
if(rear == maxSize-1)
// deals with wraparound //Note: insert() FIRST checks to see if there’s room for an insert.
rear = -1;
If rear is at maxSize-1, then we need to wrap to 0.
queArray[++rear] = j; // increment rear and insert
So rear is set to -1 and it is set to 0 in this statement.
// one more item
// note: number of items in queue is incremented.
} // end insert()
public long remove() { // take item from front of queue
long temp = queArray[front++]; // get value and increments front //Note: creates a temp variable, temp, and moves
if (front == maxSize)
// deal with wraparound
// the queue item into it and increments front pointer.
front = 0;
// it then checks to see if the new value causes wrap.
// one less item
// Lastly, it decrements the queue size; returns temp.
return temp;
} // end remove()
public long peekFront() { // peek at front of queue
return queArray[front];
} // end peek()
public boolean isEmpty() { // true if queue is empty
return (nItems==0);
} // end isEmpty()
public boolean isFull() { // true if queue is full
return (nItems==maxSize);
} // end isFull()
public int size()
// number of items in queue
return nItems;
} // end size()
// Do
20 / 23
you see a problem with insert() ?
Efficiency of Queues
 insert() and remove() are considered O(1) times;
that is, a constant. (immediate!)
 Always know the value of the appropriate index
 Simply a matter of ‘inserting’ or ‘removing’ at that
 Just about simply inserting or removing and
• a minor change in value of front or rear
• (unless we wrap).
 Deques
 A double-ended queue
 Can insert() and delete() from either end.
• Can insertLeft() and insertRight(), etc.
 Know it is there and is quite useful and versatile. Look
for it if you need it.
21 / 23
22 / 23

Object Oriented Analysis and Design Using the UML …