Introducing Data Structures with Java

11

Stacks

Stacks

Contents

• Stacks as data structures
• Stacks: array versus dynamic implementations
• Stack operations—push, pop, view
• A stack class (two versions)
• Stack applications

11.1 INTRODUCTION

A ‘stack’ is a structure based upon the linked list and is similar in some ways to a queue, but with a distinct difference. Whereas the latter is ‘FIFO’ (first in, first out), the former is ‘LIFO’ (last in, first out). A stack resembles a pile of plates (Figure 11.1)-new ones are placed on top of the stack, and an attempt to remove any but the top one is likely to end in disaster!

Figure 11.1 Operations on a stack

11.2 STACKS AND THEIR OPERATIONS ...