The Stack Data Structure

-

Introduction

 A stack is an ordered collection of items into which insertion and deletion operations occurs at only one end, called top of the stack (TOS). Unlike that of the array, the definition of stack provides for the insertion and deletion of items so that stack is dynamic and constantly changing object. 

Stacks are the subclass of lists that permits the insertion and deletion

operation to be performed at only one end.

So, how does stack change? The definition of stack specifies that a single end which is designated as the stack top. New items may be put on top of the stack where TOS moves upward and items which are at top of the stack may be removed in which TOS moves downward. 

stack data structure


Here insertion and deletion is done from the same end, last element inserted will be the first element to be removed out of the stacks resulting FILO (First In Last Out) or LIFO (Last In First Out). It can be implemented into two ways:

1. Static implementation

    - Using array

2. Dynamic implementation 

    - Using linked list


Operations on stacks

A pointer TOS keeps track of the top element in stack. Initially when stack is empty, TOS is equals to -1 and when stack contains a single element, TOS has value of zero and so on. Each time a new element is inserted in the stack, the pointer TOS is incremented by one before the element is placed in the stack. The pointer is decremented when deletion is made from the stack. Here max is define for the maximum size of stack in case of static implementation. Then the following operations can be carried out:

1. isFull()

Check whether the stack is full or not.
  1. if TOS == max-1, return true
  2. else return false

2. isEmpty()

Check whether the stack is empty or not.
  1. if TOS == -1, return true
  2. else return false

3. push()

Insert new element at new position of TOS.
  1. if isFull(), then display "stack is full" and stop
  2. read data
  3. TOS = TOS + 1
  4. stack [TOS] = data
  5. stop

4. pop()

Delete element from TOS.
  1. if isEmpty(), then display "stack is empty" and stop
  2. item = stack [TOS]
  3. TOS = TOS - 1
  4. return item

Application of Stack

  • Used to process function calls
  • Implementing recursive functions in high level languages
  • To check the validity of an arithmetic expression
  • Evaluating and converting the mathematical expression
  • Counting parenthesis and matching nested parenthesis
  • Maintaining browsing history
  • For undo operations
  • String reversing
  • Interop handling in microprocessor etc.

Comments

Post a Comment

Popular posts from this blog

Abstract Data Type ( ADT ) and Abstraction

-
Abstraction is the process of hiding many information and showing only the information of greater importance. Before writing the program first thing we have is problem. However, the problems that we asked to solve in real life are complicated. We need to list out most fundamental parts and describe these part in simple language. This overall process is called abstraction. Hiding all the information from outside world and  focus on  the  info of greater importance is abstraction. Through abstraction we can generate the model of the problem. That model includes the data and operations that are required to access and modify data. For example consider a program that manages the student records. There are many properties we could think about a student such as name, id, date of birth, major, email, phone, address etc. But all these properties are not necessary to solve the problem so we only consider name and id and the operations are add, search and display. This concept is th...
Read more

Data Structures and Algorithms : Introduction, Type and Uses

-
Image
 Introduction to Data Structures and Algorithm Data structures and algorithms are different topics but both are comes together because they are interrelated to each-other. To construct and implement any data structure we need efficient algorithm in terms of time and space. So for the proper understanding we need to learn both topic together.                A data structure is a way of storing data in a computer                           so that it can be used efficiently. Simply data structure is a way of storing data in a computer so that it can be used efficiently . Data structure begins from the choice of abstract data type, which is the mathematical model of a data structure  that specifies the type of data, operations on data and parameters of the operations. For the organization of mathematical and logical concept, data structure provides a method...
Read more

What is Algorithm? and its types

-
Image
Algorithm is a finite sequence of instructions, each of which have clear meaning and can be executed with a finite amount of effort in finite time. It is the instruction for operation to the computer of any input values to produce output. An algorithm is any well defined computational procedure that takes some value or set of values as input and produces some value or set of values as output. Thus the algorithm is a sequence of steps that transform the input into output. An algorithm is a set of instruction to be performed  to solve the desired problem. We can view an algorithm as a tool for solving well-defined computational problem. In algorithm, we define the statements for computer to solve the specific problem in general terms with desired input and output relationship. Step-by-step procedure to solve the problem Well done now we are aware about what actually algorithm is? But why algorithm is needed? As we know computer have limited space and speed. To make any program faster...
Read more