Transcript document

Implementing Stacks Using
Arrays
CSC 1401: Introduction to Programming with Java
Week 14 – Lecture 1
Wanda M. Kunkle
What is a stack?

A stack is a collection of related data items
based on the principle of last-in, first-out (LIFO):


The last item placed on the stack is the first item
removed from the stack.
A stack is analogous to a pile of trays in a
cafeteria:


A person taking a tray removes the tray from the top
of the pile.
A person returning a tray places the tray on the top of
the pile.
2
Manipulating Stacks


A stack differs from a pile of trays, however, in
that a stack only allows us to see and access the
item on the top; to access items farther down in
the stack we must first remove those above it.
The two primary operations for manipulating
items on a stack are:

push


Places an item on the top of the stack
pop

Removes an item from the top of the stack
3
How can we implement a stack
using an array?

Steps:
1.
2.
3.
Determine the size of the stack
Determine the kind of data the stack will
store
Implement (minimally) the push and pop
operations
4
How can we implement a stack
using an array?
1.
Determine the size of the stack

Example from today’s demo program,
demoStack.java:
static final int MAXSIZE = 10;
(Aside:
Actually, the stack will be size 11, with the 0th
element reserved for a special purpose.
Specifically, the 0th slot will be used to keep track
of the next available stack location.
)
5
How can we implement a stack
using an array?
2.
Determine the kind of data the stack will store

Example from today’s demo program,
demoStack.java:
// Define a stack that will store integers
int intStack[] = new int[MAXSIZE+1];
6
How can we implement a stack
using an array?
3.
Implement (minimally) the push and pop
operations

Example push and pop functions from today’s
demo program, demoStack.java, appear on the
next two slides.
7
Implementation of “push”

// Pushes an element onto the stack
static void push ( int[] a, int val ) {
int topelementindex;
input
output
in = new input();
out = new output();
if (!isfull(a)) {
topelementindex = a[0];
a[topelementindex] = val;
a[0]--;
} else {
out.writeln("Severe error!!!!!");
out.writeln("Try to push onto full stack");
out.writeln("Press ENTER to end the program");
String junk = in.readline();
System.exit(1);
}
} // end push
8
Implementation of “pop”

// Removes an element from the top of the stack
static int pop ( int[] a ) {
int returnval = 0;
int topelementindex;
input
output
in = new input();
out = new output();
if (!isempty(a)) {
a[0]++;
topelementindex = a[0];
returnval = a[topelementindex];
} else {
out.writeln("Severe error!!!!!");
out.writeln("Try to pop from empty stack");
out.writeln("Press ENTER to end the program");
String junk = in.readline();
System.exit(1);
}
return returnval;
} // end pop
9
Additional Methods for
Manipulating Stacks

isempty


isfull


Returns true if the stack is empty, false
otherwise
Returns true if the stack is full, false otherwise
print

Prints the contents of the stack
10
Sample Program & Animation

Now let’s take a look at a sample program
that implements a stack:


demoStack.java
As well as a Java applet that
demonstrates basic stack operations:

Stack
11