STACK DATA Linear DS

STRUCTURE
DEFINITION
A stack is a linear data structure which can be accessed only at
one of its ends for storing and retrieving data
In which items may be inserted or deleted only from one end called
top of the stack.
The order may be LIFO(Last In First Out) or FILO(First In Last
Out).
LIFO implies that the element that is inserted last, comes out first,
and
FILO implies that the element that is inserted first, comes out last.
STACK REPRESENTATION
APPLICATIONS
Reverse
Undo Mechanism
Recursion
Expression evaluation
Infix to Postfix and Prefix conversion
WHY COMPLEX….?
Stack is considered a complex data structure
because it uses other data structures for
implementation, such as Arrays, Linked lists.
STACK OPERATIONS
push() Adds a new element on the stack.
pop() Removes and returns the top element from the stack.
peek() Returns the top element on the stack without removing
it.
isFull() Checks if the stack is full.
isEmpty() Checks if the stack is empty.
STACK IMPLEMENTATION
(CONSTRAINTS/LIMITATIONS)
Pushing onto a full stack: Overflow
•When TOP=Stack_size
Popping an empty stack: Underflow
•TOP=NULL
BASIC OPERATIONS -
ARRAYS
push() Adds a new element on the
stack.
pop() Removes and returns the top
element from the stack.
peek() Returns the top element on
the stack.
isFull() Checks if the stack is full.
isEmpty() Checks if the stack is
empty.
 def push(self, x):
if [Link] ==
ALGORITHM – PUSH [Link] - 1:
print("Stack Overflow")
return

Checks if the stack is full. [Link] += 1

[Link][[Link]] = x
If the stack is full, produces an error and exit.
If the stack is not full, increments top to point next
empty space.
Adds data element to the stack location, where top
is pointing.
 def pop(self):
if [Link] == -1:
ALGORITHM - POP Print ("Stack Underflow")
•Before popping the element from the stack, return -1
we check if the stack is empty .
value = [Link][[Link]]
•If the stack is empty (top == -1), then Stack
Underflows and we cannot remove any [Link] -= 1
element from the stack.
•Otherwise, we store the value at top, return value
decrement the value of top by 1 (top = top –
1) and return the stored top value.
 ALGORITHM - TOP OR
PEEK OPERATION
Returns the top element of the stack.
•Before returning the top element from the def peek(self):
stack, we check if the stack is empty.
if [Link] == -1:
•If the stack is empty (top == -1), we simply
print “Stack is empty”. ("Stack is Empty")
•Otherwise, we return the element stored at
•index = top. return -1

return [Link][[Link]]
 ALGORITHM - ISEMPTY
OPERATION
Returns true if the stack is empty, else false.
•Check for the value of top in stack.

•If (top == -1) , then the stack is empty so return true.

•Otherwise, the stack is not empty so return false.
def isEmpty(self):
return [Link] == -1
STACK USING LINKED LIST
Stack can be implemented using a Linked List,
where each element of the stack is represented as a
node.
The head of the linked list acts as the top of the
stack.
DECLARATION OF STACK USING
LINKED LIST class Node:
def __init__(self, x):
As each element of the stack is represented by a node,
and we maintain a reference to the top node of the stack. [Link] = x
1. Node Structure / Class [Link] = None
Each node consists of: # Stack class
• data → stores the actual element.
• next → a pointer (or reference) to the next node in the stack. class myStack:
2. Top Pointer def __init__(self):
• The top pointer always refers to the most recently added # initially stack is
node.
• When the stack is empty, top = None (or null), indicating there are empty
no elements in the stack.
[Link] = None
 Time
PUSH OPERATION – LINKED Complexity: O(1)
def push(self, x):
LIST New_node = Node(x)
Create a new node with the given value.
New_node.next = [Link]
Set the next pointer of this new node to the current top node.
Update the top pointer to point to this newly created node.
[Link] = New_node

The new node becomes the top of the stack, and the previous elements
remain linked below it.
Push Push
(12) (13)

11 Null 12 11 Null 13 12 11 Null

Top Top Top

 def pop(self):

POP OPERATION – LINKED if [Link] is None:

LIST
Print ("Stack Underflow")

Removes the top element from the stack. return -1


If the stack is empty (top == NULL) →
Underflow occurs. temp = [Link]
Otherwise: [Link] = [Link]
 Store the current top node in a temporary pointer.
 Move top to the next node. val = [Link]
Time
 Delete the temporary node to free memory.
Complexity: O(1) del temp
The top element is removed, and the next node
becomes the new top. return val

Pop ( ) Pop ()

13 12 11 Null 12 11 Null 11 Null

Top Top Top

PEEK (OR TOP) OPERATION –
LINKED LIST
Returns the value of the top item without removing it from the
stack.
If the stack is empty (top == NULL), then no element exists.
Otherwise, simply return the data of the node pointed by top.
def peek(self):

if [Link] is None:
Time
print("Stack is Complexity: O(1)
Empty")
return -1
INFIX TO POSTFIX
EXPRESSION
 Given a string s representing an infix expression

OPERAND1 OPERATOR OPERAND2

 Convert it into its postfix notation
OPERAND1 OPERAND2 OPERATOR
PRECEDENCE ORDER
(^) has the highest precedence and is evaluated from right to left,
(* and /) come next with left to right associativity,
(+ and -) have the lowest precedence with left to right associativity.
INFIX TO POSTFIX NOTATION
WITH STACK
INFIX Notation

(A + B) * C
Parentheses () make sure A + B is handled first.
After that, result of (A + B) is multiplied by C.
That’s why in postfix, A B + comes before C *.
EXAMPLE - (A + B) * C
POSTFIX NOTATION
A+B*C
A + (B * C)
ABC*+
HOW TO SOLVE A POSTFIX
EXPRESSION
Input: s = a*(b+c)/d
Output: *a/+bcd
PREFIX TO INFIX
CONVERSION
Infix : (OPERAND1 OPERATOR OPERAND2).
• Example : (A+B) * (C-D)

Prefix : (OPERATOR OPERAND1 OPERAND2).

• Example : *+AB-CD (Infix : (A+B) * (C-D) )
EXAMPLE
PREFIX TO POSTFIX
CONVERSION
Prefix : (OPERATOR OPERAND1 OPERAND2).

Postfix: (OPERAND1 OPERAND2 OPERATOR)

Example:
Input : Prefix : *+AB-CD
Output : Postfix : AB+CD-*
Explanation : Prefix to Infix : (A+B) * (C-D)
Infix to Postfix : AB+CD-*
POSTFIX TO PREFIX
CONVERSION
Input : Postfix : AB+CD-*
Output : Prefix : *+AB-CD
Explanation : Postfix to Infix : (A+B) * (C-D)
Infix to Prefix : *+AB-CD