Page 63 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms Anil Sharma, Lovely Professional University

Notes Unit 3: Stacks

CONTENTS

Objectives
Introduction
3.1 Stack Model
3.2 Implementation of Stacks
3.2.1 Array-based Implementation

3.2.2 Pointer-based Implementation
3.3 Applications of Stacks
3.3.1 Maze Problem
3.3.2 Simulating Recursive Function using Stack

3.3.3 Simulation of Factorial
3.4 Summary
3.5 Keywords
3.6 Self Assessment
3.7 Review Questions

3.8 Further Readings

Objectives

After studying this unit, you will be able to:
Describe the stack model
Explain the implementation and applications of stacks

Introduction

Stack is another linear data structure having a very interesting property. Unlike arrays and link
lists, an element can be inserted and deleted not at any arbitrary position but only at one end.
Thus, one end of a stack is sealed for insertion and deletion while the other end allows both the
operations.

3.1 Stack Model

A stack is a linear data structure in as much as its member elements are ordered as 1st, 2nd,….
and last. However, an element can be inserted in and deleted from only one end. The other end
remains sealed. This open end to which elements can be inserted and deleted from is called stack
top or top of the stack. Consequently, the elements are removed from a stack in the reverse order
of insertion. A stack is said to possess LIFO (Last In First Out) property. A data structure has

LIFO property if the element that can be retrieved first is the one that was inserted last.

58 LOVELY PROFESSIONAL UNIVERSITY