Scribd
Upload
4 views6 pages

Data Structure Stack

The document provides an overview of data structures, focusing on stacks as a linear structure that operates on a Last In First Out (LIFO) basis. It explains the basic operations of a stack, including push, pop, and display, along with algorithms for implementing these operations in Python. Additionally, it discusses applications of stacks and includes sample questions for practical implementation.

Uploaded by

alanmatthew07
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views6 pages

Data Structure Stack

The document provides an overview of data structures, focusing on stacks as a linear structure that operates on a Last In First Out (LIFO) basis. It explains the basic operations of a stack, including push, pop, and display, along with algorithms for implementing these operations in Python. Additionally, it discusses applications of stacks and includes sample questions for practical implementation.

Uploaded by

alanmatthew07
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

12/11/22, 7:04 PM Data_Structure_Stack

Chapter Name

Data Structure

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Index:
1. What is Data Structure
2. Different Data Structure: 2.1 Simple Data Structure 2.2 Compound Data Structure

2.2.1 Linear Data Structure


2.2.2 Non Linear Data Structure

3. Stack

1. What is Data Structure


A Data structure is a named group of data of different data types which is stored in a specific way and can be processed as a single unit.

A data structure has well-defined operations. behaviour and properties.

2. Different Data Structure


2.1 Simple Data Structure

2.2 Compound Data Structure

2.1 Simple Data Stucture

Simple data structure are normally built from primitive(atomic) data types such as integer,real,characters,boolean,etc.

Example of SDS:

array
linear list

2.2 Compound Data Struture

Simple Data Structure can be combined in various ways to form more complex strutures called compound data strucure.

Compound Data Structure two categories are:

2.2.1. Linear Data Structure


2.2.2. Non-Linear Data Structure.

2.2.1 Linear Data Structure

These data structure are single level data strucure.

Example of LDS:

- Stack
- Queue
- Linked List

2.2.2 Non-Linear Data Structure

These are multilevel data structures

Example of NLDS:

- Tree
- Graph

localhost:8888/notebooks/OneDrive/Documents/Notes_XII_CS_2022_23_Batch/PythonFile/Data_Structure_Stack.ipynb 1/6
12/11/22, 7:04 PM Data_Structure_Stack

3. STACK
A stack is a linear structure implemented in LIFO(Last In First Out) manner where insertions and deletions are restricted to occure only at one end - Stack's top.

LIFO means element last inserted would be the first one to be deleted.

A stack is a list of data that follows these rules:

1. Data can only be removed from the top(pop),top is basically top(last place) of the stack

(The removal of element from a stack is technically called POP opearion.)


2. A new data element can only be added to the top of the stack(push).

(The insertions of element in a stack is technically called PUSH opearion)

Method-I

Implementation of STACK using List

In [ ]:

The basic operations performed on the stack are:


1. Creating Stack
2. PUSH Opearation/Adding Elements to a STACK
3. Checking for Empty Stack
4. Pop Operation/Deleting Elements from a STACK
5. Traversal/Displaying a STACK

1. Creating STACK

In [ ]:

stack = []
stack = list()

2. Adding Elements into a STACK

In [ ]:

[Link](value)

Algorithm for PUSH operation

In [ ]:

[Link]
2. Initlize top with -1 or None
3. ele=input("Value to be inserted into stack")
4. [Link](ele)
5. END

3. Checking for Empty Stack

Algorithm for Empty Stack

In [ ]:

1. START
2. length=len(STACK)
3. if length == 0:
print("STACK is empty")
OR
3. if stack == []:
print("STACK is Empty")

4. Pop Operation/Deleting Elements from a STACK

In [ ]:

ele=[Link]()
print(ele)

5. Traversal/Displaying a STACK

localhost:8888/notebooks/OneDrive/Documents/Notes_XII_CS_2022_23_Batch/PythonFile/Data_Structure_Stack.ipynb 2/6
12/11/22, 7:04 PM Data_Structure_Stack

In [1]:

stack=[45,75,95,42,63]

In [5]:

for i in range(len(stack)-1 , -1 , -1):


print(stack[i],i)

63 4
42 3
95 2
75 1
45 0

In [7]:

for i in range(-1,-len(stack)-1,-1):
print(stack[i],i)

63 -1
42 -2
95 -3
75 -4
45 -5

In [8]:

print(stack)
[Link]()
print(stack)
for ele in stack:
print(ele)

[45, 75, 95, 42, 63]


[63, 42, 95, 75, 45]
63
42
95
75
45

Implementation of All basic operation of a STACK

Method - I
In [ ]:

#Implementation of List as STACK


STACK = []
ans='y'
while ans=='y' or ans=='Y':
print("1. PUSH")
print("2. POP")
print("3. DISPLAY")
choice = int(input("Enter Your Choice:- "))
if choice == 1:
ele=input("Enter Value to insert into STACK:- ")
[Link](ele)
elif choice == 2:
if len(STACK)==0: # STACK == []
print("STACK is EMPTY(Underflow)")
break
else:
ele=[Link]()
print("Poped Value of Stack:- ",ele)
elif choice == 3:
for i in range(len(STACK)-1 , -1 ,-1):
print(STACK[i])
else:
print("Wrong Choice")
ans=input("Do U Want to Continue")

Method-II

localhost:8888/notebooks/OneDrive/Documents/Notes_XII_CS_2022_23_Batch/PythonFile/Data_Structure_Stack.ipynb 3/6
12/11/22, 7:04 PM Data_Structure_Stack

In [ ]:

def PUSH(stk,item):
[Link](item)
TOP = len(stk)-1

def POP(stk):
if len(stk) == 0: # stk == []
return "Underflow"
else:
ret = [Link]()
if len(stk)==0: # stk == []
TOP=None
else:
TOP = len(stk)-1
return ret

def Display(stk):
if len(stk) == 0:
print("Empty Stack")
else:
for i in range(len(stk)-1 , -1 , -1 ):
print(stk[i])

def PEEK(stk):
if len(stk)==0:
return "Underflow"
else:
TOP = len(stk)-1
return stk[TOP]

#-----MAIN------
STACK = []
TOP = None
while True:
print("1. PUSH")
print("2. POP")
print("3. PEEK")
print("4. DISPLAY")
print("5. EXIT")
choice = int(input("Enter Your Choice:- "))
if choice == 1:
item=input("Enter Value which u want to push into STACK")
PUSH(STACK,item)
elif choice == 2:
ret = POP(STACK)
if ret == "Underflow":
print("Underflow")
break
else:
print("Poped element of STACK is :- ",ret)
elif choice == 3 :
ret = PEEK(STACK)
if ret == "Underflow":
print("Empty Stack")
else:
print("Peek element of STACK is :- ",ret)
elif choice == 4:
Display(STACK)
elif choice == 5:
break
else:
print("Wrong Choice!!!")

Application of Stack
In [ ]:

1. Reversing a Word/Line
2. Compilers use stacks to store the previous state of a program when a function is called or during recursion.
3. Another important Stack appliation is backtracking.
4. Undo Mechanism in Text Editor.

Sample Questions
Write a program to implement a stack for these book-details(bookno,bookname).That is,now each item node of the Stack contains two types of information - a book no
and its name. Just implement PUSH and display operations

localhost:8888/notebooks/OneDrive/Documents/Notes_XII_CS_2022_23_Batch/PythonFile/Data_Structure_Stack.ipynb 4/6
12/11/22, 7:04 PM Data_Structure_Stack

In [ ]:

def PUSH(stk,item):
[Link](item)
TOP = len(stk)-1

def POP(stk):
if len(stk) == 0: # stk == []
return "Underflow"
else:
ret = [Link]()
if len(stk)==0: # stk == []
TOP=None
else:
TOP = len(stk)-1
return ret

def Display(stk):
if len(stk) == 0:
print("Empty Stack")
else:
for i in range(len(stk)-1 , -1 , -1 ):
print(stk[i])

def PEEK(stk):
if len(stk)==0:
return "Underflow"
else:
TOP = len(stk)-1
return stk[TOP]

#-----MAIN------
BOOK = []
TOP = None
while True:
print("1. PUSH")
print("2. POP")
print("3. PEEK")
print("4. DISPLAY")
print("5. EXIT")
choice = int(input("Enter Your Choice:- "))
if choice == 1:
bno=int(input("Enter Book No:- "))
bname = input("Enter Book Name")
item = [bno,bname]
PUSH(BOOK,item)
elif choice == 2:
ret = POP(BOOK)
if ret == "Underflow":
print("Underflow")
break
else:
print("Poped element of STACK is :- ",ret)
elif choice == 3 :
ret = PEEK(BOOK)
if ret == "Underflow":
print("Empty Stack")
else:
print("Peek element of STACK is :- ",ret)
elif choice == 4:
Display(BOOK)
elif choice == 5:
break
else:
print("Wrong Choice!!!")

Write a function in Python, MakePush(Package) and MakePop(Package), to add a new package and delete a packate from a list of package Description, considering
them to act as PUSH and POP operations of the Stack data sturcure.

Package contians following information:

1. title - string
2. price - float

localhost:8888/notebooks/OneDrive/Documents/Notes_XII_CS_2022_23_Batch/PythonFile/Data_Structure_Stack.ipynb 5/6
12/11/22, 7:04 PM Data_Structure_Stack

In [ ]:

def MakePush(Package,data):
item = input("Enter value of Item")
or
title=input("Enter PAckage ")
price = float(input("Enter Price"))
item = [title,price]
[Link](item)
TOP=len(Package)-1
​
def MakePop(Package):
if Package == []:
print("Stack Empty, Underflow")
else:
ret = [Link]()
print("Deleted Element from Package:- ",ret)
TOP = len(Package)-1

localhost:8888/notebooks/OneDrive/Documents/Notes_XII_CS_2022_23_Batch/PythonFile/Data_Structure_Stack.ipynb 6/6

You might also like