January 2011
Intermediate to advanced
760 pages
20h 16m
English
Content preview from Data Structures and the Java Collections Framework, Third Edition
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
CHAPTER 8
Stacks and Queues
In this chapter we introduce two more abstract data types: stacks and queues. Stacks and queues can be modified in only a very limited way, so there are straightforward implementations, that is, data structures, of the corresponding data types. Best of all, stacks and queues have a wide variety of applications. We'll start with stacks because a stack is somewhat easier to implement than a queue.
CHAPTER OBJECTIVES
- Understand the defining properties of stacks and queues, and how these properties are violated by the Java Collections Framework's stack class and Queue interface.
- For both stacks and queues, be able to develop contiguous and linked implementations that do not violate their defining properties.
- Explore the use of stacks in the implementation of recursion and in converting from infix notation to postfix notation.
- Examine the role of queues in computer simulation.
8.1 Stacks
A stack is a finite sequence of elements in which the only element that can be removed is the element that was most recently inserted. That element is referred to as the top element on the stack.
For example, a tray-holder in a cafeteria holds a stack of trays. Insertions and deletions are made only at the top. To put it another way, the tray that was most recently put on the holder will be the next one to be removed. This defining property of stacks is sometimes called "Last In, First Out," or LIFO. In keeping with this view, an insertion is referred to as a push, and ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.