A Textbook of Data Structures and Algorithms, Volume 1

7Linked Stacks and Linked Queues

In Chapters 4 and 5, we discussed a sequential representation of the stack and queue data structures. Stacks and queues were implemented using arrays and hence inherited all the drawbacks of the sequential data structure.

In this chapter, we discuss the representation of stacks and queues using a linked representation, namely, singly linked lists. The inherent merits of the linked representation render an efficient implementation of the linked stack and linked queue.

We first define a linked representation of the two data structures and discuss the insert/delete operations performed on them. The role played by the linked stack in the management of the free storage pool is detailed. The applications of linked stacks and linked queues in the problems of balancing symbols and polynomial representation, respectively, are discussed later.

7.1. Introduction

To review, a stack is an ordered list with the restriction that elements are added or deleted from only one end of the stack termed the top of stack with the “inactive” end known as the bottom of stack. A stack observes the Last-In-First-Out (LIFO) principle and has its insert and delete operations referred to as Push and Pop, respectively.

The drawbacks of a sequential representation of a stack data structure are as follows:

1. finite capacity of the stack;
2. check for the STACK_FULL condition every time a Push operation is effected.

A queue, on the other hand, is a linear list in which all insertions ...