Logout

Stacks and Queues Implemented from List

 

Recall that a stack is a list in which the last thing added is the first thing removed - i.e. we access things in a LIFO (Last-in-first-out) fashion.

And a queue is a list in which the first thing added is the first thing removed - i.e. we access thigns in a FIFO (First-in-first-out) fashion.

 

Do refer to the full code images, but here is the theory behind how we extend a list class to be either a stack or a queue.

Note that in the List class, we have methods which allow us to add at either end and remove from either end of the list. But, actually, we can choose to use three of those to fully implement both the stack and the queue. For the examples in this part of Java Revolution, we will choose to use the removeFirst() method for BOTH the stack and queue to remove nodes. This means that we don't have to use the removeRear() method at all. But this will mean we will need two differnet methods for adding items to the two kinds of lists:

- For the adding to the stack, we'll use the insertAtFront()method, which moves the head on up the list as nodes are added - that way by accessing the head, we can immediately pop off what we are looking for (i.e. the last thing added.)

- And for adding to the queue we'll use the insertAtRear() method, which keeps the head where it initially was, but migrates down the list to add. That way when we remove the head, we are removing the node that has been there the longest.

In summary, this means the following:

Stack:

(adding) push() ------------> extends insertAtFront()
(removing) pop() ------------> extends removeFirst()

Queue:

(adding) enqueue() ----------> extends insertAtRear()
(removing) dequeue() ------------> extends removeFirst()