List and Stack Data Structure
Dr.M.Jayasudha
Associate Professor
SCOPE
VIT-Chennai
Insertion and Deletion: (Stack)
Perform insertion and Deletion at the same end in a
list would result in Stack Data Structure. (Linear
Persistent Data Structure).
0 1 2 3 Insert
Delete
Insertion and Deletion: (Stack)
Perform insertion and Deletion at the same end in a
list would result in Stack Data Structure. (Linear
Persistent Data Structure) (LIFO or FILO).
0 1 2 3 Insert
10 20 30 40
Delete
Insertion and Deletion: (Queue)
Perform insertion and Deletion at the same end in a list would
result in Queue Data Structure. (Linear non-Persistent Data
Structure).
0 1 2 3 Insert
Delete
Insertion and Deletion: (Queue)
Perform insertion and Deletion at the same end in a list would
result in Queue Data Structure. (Linear non-Persistent Data
Structure) (FIFO or LILO).
0 1 2 3 Insert
Delete
10 20 30 40
Stack Operations:
Push Inserting element on to the stack.
Pop Deleting the top most element(Last In)
from the stack.
Peek Printing the top most element in a
stack.
View Displaying the elements of a stack.
Stack Operations:
Definition:
#define SIZE 5
int stack[SIZE];
int top=-1;
4 4 50
empty()
{ 3 3 40
if(top ==-1)
return(1); 2 2 30
1 1 20
}
0 0 10
Full( )
{
if(top==size-1)
return(1);
}
top = -1; top=top+1=0; x=10;
stack[0]=x=10
Push()
{
if(top==size-1)
{
print stack is full;
return(); top 4 50
} 3 40
else
{ 2 30
read x; 1 20
assign stack[++top] = x;
0 10
}
pop( )
{if(top=-1)
{ print(“Stack is empty”)
return()}
{ print deleted element is stack[top];
top--;
} }
top 4 50
display( )
{ 3 40
if(top=-1) 2 30
{ print(“Stack is empty”)
4 return()} 1 20
top 3 40 { i=0;
0 10
until(i<=top)
2 30 {
1 20 printf stack[i];
i=i+1;
0 10 } }
List Operations:
Create Creating a new list
Insert Inserting element on to the list.
1.Insert Last
2.Insert First
3.Insert Middle
Delete Deleting the element from the list.
Modify Modifying an element in a list.
View Displaying the elements of a list.
Create( ) Creation Operation:
{ if(top!=-1)
{ print ”Already list is created”
return( );
}
if(top==size-1)
{
print(“List is full further elements cannot be inserted”);
retunr( );
}
Read n number of elements to be inserted;
Assign i=0;
Until(i<n)
{ Read list[++top];
}
Insert Last Operation:
Before Insertion
insertlast( )
0 1 2
{ 10 20 30
if(top==size-1)
Top=2
{
print ”list is full” After Insertion
return( ); 0 1 2 3
10 20 30 40
}
Read list[++top]; Top=3
Return( );
}
Insert First Operation:
insertfirst( ) Before Insertion
{ 0 1 2
if(top==size-1) 10 20 30
{
print ”list is full” Top=2
return( );
} After Insertion
j=top+1; 0 1 2 3
While(j!=0) 40 10 20 30
{
list[j]=list[j-1]; Top=3
j--;
}
Read list[j]; //Read list[0];
Return( );
Before Insertion
0 1 2
Insert middle Operation: 10 20 30
insertmiddle( )
Top=2
{
if(top==size-1)
{
print ”list is full”
return( );
}
After Insertion
0 1 2 3
10 20 40 30
Top=3
Read element after which insertion is to be done ‘x’ //input = 20
i=0;
While(i<=top)
{
Before Insertion
if(x==list[i])
0 1 2
{ top++;
10 20 30
j=top;
while(j!=i+1)
Top=2
{
list[j]=list[j-1];
j--;
}
After Insertion
Read list[j]; //Read list[i+1];
0 1 2 3
Return( ); }
10 20 40 30
else
i++; Top=3
}
1. Develop a menu driven program to implement the basic operations in a stack.
*****MENU******
1.Push
2.Pop
3.Peek
4.Display
Enter your option: 1
10
2. Create a data structure twoStacks that represents two stacks. Implementation of
twoStacks should use only one array, i.e., both stacks should use the same array for
storing elements. Following functions must be supported by twoStacks.
push1(int x) –> pushes x to first stack
push2(int x) –> pushes x to second stack
pop1() –> pops an element from first stack and return the popped element
pop2() –> pops an element from second stack and return the popped element
Display1()-> Display stack1 elements
Display2()-> Display stack2 elements
Implementation of twoStack should be space efficient.
0 1 2 3 4 5 6 7
10 20 30 100 200 300
stack1 stack2
Push1(int x) = x =10 Push2(int x) = x =100
Push1(int x) = x =20 Push2(int x) = x =200
Push1(int x) = x =30 Push2(int x) = x =300
Push1(int x) = x =40 Push2(int x) = x =400
Push1(int x) = x =50 Push2(int x) = x =500
Pop1()= 40 Pop2()= 400
Pop1()= 30 Pop2()= 300
Pop1()= 20 Pop2()= 200
Pop1()= 10 Pop2()= 100
Pop1()= Pop2()=
display1()= 0 to top1 display2()= n/2 to top2
= 10 to 30 = 100 to 300
