UNIT III- STACK
Stack as an ADT - Representation and implementation of Stack using Sequential and Linked
Organization - Applications of Stack - Simulating Recursion using Stack – Arithmetic
Expression Conversion and Evaluation - Time complexity analysis of Stack operations.
STACK as an ADT
• Stack is a linear data structure which follows the principle of Last In First
Out(LIFO). In stack insertion and deletion are done at only one end called top.
• Stack is an abstract data type, which doesn’t define the underlying structure itself.
• Stack only defines a set supported operations that we can we implement by different
concrete data structures (such as arrays or linked lists)
Basic operations:
• push(): Insert an element at one end of the stack called the top.
• pop(): Remove and return the element at the top of the stack, if it is not empty.
• peek(): Return the element at the top of the stack without removing it, if the stack is
not empty.
• size(): Return the number of elements in the stack.
• isEmpty(): Return true if the stack is empty; otherwise, return false.
• isFull(): Return true if the stack is full; otherwise, return false.
, Representation and implementation of Stack using Sequential and Linked
Organization:
Representation of Stack Data Structure:
Representation of Stack Data Structure using sequential organization
(Arrays):
A Stack is a linear data structure that follows the principle of (Last-In-First-Out) LIFO . In
Stack there is one end through which insertion and deletion takes place. Whenever an element
is added in the stack, it is added on the top of the stack, and the element can be deleted only
from the stack. In other words, a stack can be defined as a container in which insertion and
deletion can be done from the one end known as the top of the stack. A stack is a data structure
that can be represented as an array.
An array is used to store an ordered list of elements. Using an array for representation of stack
is one of the easy techniques to manage the data. But there is a major difference between an
array and a stack.
• Size of an array is fixed.
• While, in a stack, there is no fixed size since the size of stack changed with the number
of elements inserted or deleted to and from it.
Despite the difference, an array can be used to represent a stack by taking an array of
maximum size; big enough to manage a stack.
Stack as an ADT - Representation and implementation of Stack using Sequential and Linked
Organization - Applications of Stack - Simulating Recursion using Stack – Arithmetic
Expression Conversion and Evaluation - Time complexity analysis of Stack operations.
STACK as an ADT
• Stack is a linear data structure which follows the principle of Last In First
Out(LIFO). In stack insertion and deletion are done at only one end called top.
• Stack is an abstract data type, which doesn’t define the underlying structure itself.
• Stack only defines a set supported operations that we can we implement by different
concrete data structures (such as arrays or linked lists)
Basic operations:
• push(): Insert an element at one end of the stack called the top.
• pop(): Remove and return the element at the top of the stack, if it is not empty.
• peek(): Return the element at the top of the stack without removing it, if the stack is
not empty.
• size(): Return the number of elements in the stack.
• isEmpty(): Return true if the stack is empty; otherwise, return false.
• isFull(): Return true if the stack is full; otherwise, return false.
, Representation and implementation of Stack using Sequential and Linked
Organization:
Representation of Stack Data Structure:
Representation of Stack Data Structure using sequential organization
(Arrays):
A Stack is a linear data structure that follows the principle of (Last-In-First-Out) LIFO . In
Stack there is one end through which insertion and deletion takes place. Whenever an element
is added in the stack, it is added on the top of the stack, and the element can be deleted only
from the stack. In other words, a stack can be defined as a container in which insertion and
deletion can be done from the one end known as the top of the stack. A stack is a data structure
that can be represented as an array.
An array is used to store an ordered list of elements. Using an array for representation of stack
is one of the easy techniques to manage the data. But there is a major difference between an
array and a stack.
• Size of an array is fixed.
• While, in a stack, there is no fixed size since the size of stack changed with the number
of elements inserted or deleted to and from it.
Despite the difference, an array can be used to represent a stack by taking an array of
maximum size; big enough to manage a stack.
