Java Reference
In-Depth Information
Chapter 4
Stacks and Queues
In this chapter, we will explain the following:
•
The notion of an abstract data type
•
What a stack is
•
How to implement a stack using an array
•
How to implement a stack using a linked list
•
How to create a header file for use by other programs
•
How to implement a stack for a general data type
•
How to convert an expression from infix to postfix
•
How to evaluate an arithmetic expression
•
What a queue is
•
How to implement a queue using an array
•
How to implement a queue using a linked list
4.1 Abstract Data Types
We are familiar with the notion of declaring variables of a given type (
double
, say) and then performing operations on
those variables (for example, add, multiply, and assign) without needing to know
how
those variables are stored in the
computer. In this scenario, the compiler designer can change the way a
double
variable is stored, and the programmer
would not have to change any programs that use
double
variables. This is an example of an abstract data type.
An
abstract data type
is one that allows a user to manipulate the data type without any knowledge of how the
data type is represented in the computer. In other words, as far as the user is concerned, all he needs to know are the
operations that can be performed on the data type. The person who is implementing the data type is free to change its
implementation without affecting the users.
In this chapter, we show how to implement stacks and queues as abstract data types.
4.2 Stacks
A
stack
as a linear list in which items are added at one end and deleted from the same end. The idea is illustrated by a
“stack of plates” placed on a table, one on top of the other. When a plate is needed, it is taken from the top of the stack.
When a plate is washed, it is added to the top of the stack. Note that if a plate is now needed, this “newest” plate is the
one that is taken. A stack exhibits the “last in, first out” property.
Search WWH ::
Custom Search