Page 126 - DCAP407_DATA_STRUCTURE

Anil Sharma, Lovely Professional University Unit 7: Stacks

Unit 7: Stacks

CONTENTS
Objectives
Introduction
7.1 Fundamentals of Stacks

7.1.1 Stack Structure
7.2 Basic Operations of Stack
7.2.1 Push Operation
7.2.2 Pop Operation
7.3 Representing Stacks in Memory
7.4 Stack Implementation using Arrays

7.5 Summary
7.6 Keywords
7.7 Self Assessment
7.8 Review Questions
7.9 Further Readings
Objectives

After studying this unit, you will be able to:
• Describe the fundamentals of stacks

• Explain the basic operations of stack
• Analyze representing stacks in memory
• Discuss stack implementation using arrays
Introduction

Stacks are simple data structures and an important tool in programming language. Stacks are linear lists
which have restrictions on the insertion and deletion operations. These are special cases of ordered list
in which insertion and deletion is done only at the ends.
The basic operations performed on stack are push and pop. Stack implementation can be done in two
ways - static implementation or dynamic implementation. Stack can be represented in the memory
using a one-dimensional array or a singly linked list.
7.1 Fundamentals of Stacks

A stack is a linear data structure in which allocation and deallocation are made in a last-in-first-out
(LIFO) method. In the LIFO method, the insertions and deletions are done at one end which is known as
the top of the stack (TOS). In a stack, the top is a variable which points to the top element in the stack.
Consider a stack of books or stack of coins. The items can be added or removed only from the top. This
means that the last item that is added to the stack is the first item to be removed.

Did you know? The stack was first proposed in 1955 and then patented in 1957 by the German
Friedrich L. Bauer. The same concept was developed independently, at around the
same time, by the Australian Charles Leonard Hamblin.

LOVELY PROFESSIONAL UNIVERSITY 119