- Forward


Stacks and Queues
An Introduction with Examples in Java


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Motivation
Back Forward
  • Collections:
    • We now know how to use several
    • We need to know something about implementing them
  • Data Structures:
    • We now know about contiguous and linked data structures
    • We need to know how to implement collections using both
Implementing Collections Using Contiguous Memory
Back Forward
  • A Limitation:
    • Only appropriate for fixed capacity collections
  • Issues that Arise:
    • Keeping track of the next empty space
    • Keeping track of the "current" filled space
    • Shuffling
Implementing Collections Using Linked Memory
Back Forward
  • The Basics:
    • Use a node that contains a value and a "pointer" to the next node
    • The pointers "link" the different nodes together
  • An Illustration:
    • images/linked_structure_components.gif
Stacks
Back Forward
  • Defined:
    • An ordered collection in which elements can be pushed/added onto the top and popped/removed from the top
  • An Important Acronym:
    • Last-in, first-out (LIFO)
  • A Physical Analogy:
    • A box of paper -- when you add a piece of paper to the box it gets put on the top; the only piece of paper that can be removed is the top sheet
Stacks that Use Contiguous Memory
Back Forward
  • Capacity:
    • 3
  • Push on a 1:
    • 1 . .
  • Push on a 2:
    • 1 2 .
Stacks that Use Contiguous Memory (cont.)
Back Forward

One Approach

javaexamples/stackqueue/contiguous/Stack.java
 
Stacks that Use Linked Memory
Back Forward

The Node Class

javaexamples/stackqueue/linked/Node.java
 
Stacks that Use Linked Memory (cont.)
Back Forward

One Possible Linked Stack

javaexamples/stackqueue/linked/Stack.java
 
Queues
Back Forward
  • Defined:
    • An ordered collection in which elements can be pushed/added onto the back and popped/removed from the front
  • An Important Acronym:
    • First-in, first-out (FIFO)
  • Physical Analogy:
    • A "waiting line" -- when you add a person to the line they go to the back and people are served from the front
Queues that Use Contiguous Memory
Back Forward
  • Capacity:
    • 3
  • Push on a 1:
    • 1 . .
  • Push on a 2:
    • 1 2 .
Queues that use Contiguous Memory (cont.)
Back Forward

Using Constant Shuffling

javaexamples/stackqueue/contiguous/Queue.java
 
Queues that use Contiguous Memory (cont.)
Back Forward
  • Periodic Shuffling:
    • Keep a pointer to the front and rear elements and move all of the elements down when space at the back runs out
    • This is analgous to a waiting line in which the server moves (until space runs out)
    • Think about a clock in which the ticks are on a line, not a circle
  • Using a "Circular Array":
    • Keep a pointer to the front and rear elements and have them "wrap around"
    • This is analgous to a waiting line in which the server moves in a circle
Queues that use Linked Memory
Back Forward

One Possible Linked Queue

javaexamples/stackqueue/linked/Queue.java
 
There's Always More to Learn
Back -