Chapter 9.3.1 – Java Stacks | Introduction to Programming Using Java

Chapter 9.3.1 – Java Stacks | Introduction to Programming Using Java

 

9.3.1  Java Stacks

 

A stack consists of a sequence of items, which should be thought of as piled one on top of the other like a physical stack of boxes or cafeteria trays. Only the top item on the stack is accessible at any given time. It can be removed from the stack with an operation called pop. An item lower down on the stack can only be removed after all the items on top of it have been popped off the stack.

 

Chapter 9.3.1 Stacks | Introduction to Programming Using Java

 

 

A new item can be added to the top of the stack with an operation called push. We can make a stack of any type of items. If, for example, the items are values of type int, then the push and pop operations can be implemented as instance methods

  • void push (int newItem) — Add newItem to top of stack.
  • int pop() — Remove the top int from the stack and return it.

It is an error to try to pop an item from an empty stack, so it is important to be able to tell whether a stack is empty. We need another stack operation to do the test, implemented as an instance method

  • boolean isEmpty() — Returns true if the stack is empty.

This defines a “stack of ints” as an abstract data type. This ADT can be implemented in several ways, but however it is implemented, its behavior must correspond to the abstract mental image of a stack.

 

Chapter 9.3.1 Stacks | Introduction to Programming Using Java

 

In the linked list implementation of a stack, the top of the stack is actually the node at the head of the list. It is easy to add and remove nodes at the front of a linked list—much easier than inserting and deleting nodes in the middle of the list. Here is a class that implements the “stack of ints” ADT using a linked list. (It uses a static nested class to represent the nodes of the linked list. If the nesting bothers you, you could replace it with a separate Node class.) public class StackOfInts {

Chapter 9.3.1 Stacks | Introduction to Programming Using Java

You should make sure that you understand how the push and pop operations operate on the linked list. Drawing some pictures might help. Note that the linked list is part of the private implementation of the StackOfInts class. A program that uses this class doesn’t even need to know that a linked list is being used.

Now, it’s pretty easy to implement a stack as an array instead of as a linked list. Since the number of items on the stack varies with time, a counter is needed to keep track of how many spaces in the array are actually in use. If this counter is called top, then the items on the stack are stored in positions 0, 1, …, top-1 in the array. The item in position 0 is on the bottom of the stack, and the item in position top-1 is on the top of the stack.

Pushing an item onto the stack is easy: Put the item in position top and add 1 to the value of top. If we don’t want to put a limit on the number of items that the stack can hold, we can use the dynamic array techniques from Subsection 7.3.2. Note that the typical picture of the array would show the stack “upside down”, with the top of the stack at the bottom of the array. This doesn’t matter.

The array is just an implementation of the abstract idea of a stack, and as long as the stack operations work the way they are supposed to, we are OK. Here is a second implementation of the StackOfInts class, using a dynamic array:

Chapter 9.3.1 Stacks | Introduction to Programming Using Java

Once again, the implentation of the stack (as an array) is private to the class. The two versions of the StackOfInts class can be used interchangeably, since their public interfaces are identical.

It’s interesting to look at the run time analysis of stack operations. (See Section 8.6). We can measure the size of the problem by the number of items that are on the stack. For the linked list implementation of a stack, the worst case run time both for the push and for the pop operation is Θ(1).

This just means that the run time is less than some constant, independent of the number of items on the stack. This is easy to see if you look at the code. The operations are implemented with a few simple assignment statements, and the number of items on the stack has no effect.

For the array implementation, on the other hand, a special case occurs in the push operation when the array is full. In that case, a new array is created and all the stack items are copied into the new array. This takes an amount of time that is proportional to the number of items on the stack. So, although the run time for push is usually Θ(1), the worst case run time is Θ(n), where n is the number of items on the stack.

 

SEE MORE:

5 thoughts on “Chapter 9.3.1 – Java Stacks | Introduction to Programming Using Java”

Leave a Comment