Reading Materials
Data Structures: Stack and Queue using List
Data Structure
Data Structure is a way of collecting and organizing data in such a way that we
can perform operations on these data in an effective way.
Stack
A stack is a data structure whose elements are accessed according to the Last-
In First-Out (LIFO) principle. This is because in a stack, insertion and deletion
of elements can only take place at one end, called top of the stack.
Consider the following examples of stacks:
1. A pile of books
2. A stack of coins
3. Ten glass plates placed one above another.
Fig.1 A stack of coins
In the above picture coins are kept one above the other and if any additional coin
is to be added, it can be added only on the top. If we want to remove any coin
from the stack, the coin on the top of the stack has to be removed first. That
means, the coin that was kept last in the stack has to be taken out first.
The two operations performed on the stack are:
Push operation: It means inserting element at the top of the stack. This
can be done with the help of append() method of the list as:
st.append(element) where ‘st’ is a list.
Pop operation: It means removing the topmost element from the stack.
This can be performed using pop() method of the list as: st.pop() where ‘st’
is a list. This method returns the removed element that can be displayed.
Applications of Stack
Recursion
Postfix notations(Evaluation of expressions)
Tower of Hanoi
Program to implement stack using list
Program Output
st=[] #to create an empty list 1.Push
def stkpush(): 2.Pop
n=int(input("Enter a No. : ")) 3.display
st.append(n) Enter choice: 1
def stkpop(): Enter a No. : 10
if st==[ ]: 1.Push
print("Underflow") 2.Pop
else: 3.display
print(st.pop()," removed") Enter choice: 1
def display(): Enter a No. : 20
if st==[ ]: 1.Push
print("Underflow") 2.Pop
else: 3.display
print("stack is: ") Enter choice: 1
L=len(st)-1 Enter a No. : 30
for i in range(L,-1,-1): 1.Push
print(st[i]) 2.Pop
char=True 3.display
while(char): Enter choice: 3
print("1.Push") stack is:
print("2.Pop") 30
print("3.display") 20
ch=int(input("Enter choice: ")) 10
if ch==1: 1.Push
stkpush() 2.Pop
elif ch==2: 3.display
stkpop() Enter choice: 2
elif ch==3: 30 removed
display() 1.Push
else: 2.Pop
char=False 3.display
Enter choice: 1
Enter a No. : 40
1.Push
2.Pop
3.display
Enter choice: 3
stack is:
40
20
10
Queue
A queue is a data structure where the element that is added first will be deleted
first. This is called FIFO (First In First Out) order. A queue has two ends, called
the front end and rear end. Items are always added from the rear end and
removed from the front end. The process of adding items to queue is called insert
operation or enqueue and removal of items from the queue is called delete
operation or dequeue.
Consider the following examples of queues:
1. The consumer who comes first to a shop will be served first.
2. People standing in queue in front of train ticket counter.
Fig.2 People standing in front of ATM machine
The two operations performed on the queue are:
Insert operation: It means inserting element at the rear (or back) end of
the queue. This can be done using append() method of list as:
Q.append(element), where Q is a list.
Delete operation: It represents removing the element from the front of the
queue. This can be done using pop() method of list as: Q.pop(0), where Q
is a list.
Applications of Queue
CPU scheduling
Resource sharing
Multiprogramming
Real time system
Program to implement Queue using list
Program Output
Q=[] #to create empty list 1.Insert
def insertq(): 2.delete
n=int(input("Enter a number: ")) 3.display
Q.append(n) Enter your choice: 1
def deleteq(): Enter a number: 15
if Q==[]: 1.Insert
print("underflow") 2.delete
else: 3.display
print(Q.pop(0),"deleted”) Enter your choice: 1
def display(): Enter a number: 25
if Q==[]: 1.Insert
print("underflow") 2.delete
else: 3.display
for i in Q: Enter your choice: 1
print(i,end=' ') Enter a number: 35
print() 1.Insert
char=True 2.delete
while(char): 3.display
print("1.Insert") Enter your choice: 3
print("2.delete") 15 25 35
print("3.display") 1.Insert
ch=int(input("Enter your choice: ")) 2.delete
if ch==1: 3.display
insertq() Enter your choice: 2
elif ch==2: 15 deleted
deleteq() 1.Insert
elif ch==3: 2.delete
display() 3.display
else: Enter your choice: 3
char=False 25 35
1.Insert
2.delete
3.display
Enter your choice: 1
Enter a number: 45
1.Insert
2.delete
3.display
Enter your choice: 3
25 35 45
1.Insert
2.delete
3.display
Enter your choice:
