Scribd
Upload
63 views7 pages

Program 4

The document discusses implementing a stack using a linked list in C++. It provides the theory, algorithm, code and output for push and pop operations on the stack. It also discusses the time and space complexity and what was learned from the implementation.

Uploaded by

2K18/CO/166 KAMAL ROHILLA
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
63 views7 pages

Program 4

The document discusses implementing a stack using a linked list in C++. It provides the theory, algorithm, code and output for push and pop operations on the stack. It also discusses the time and space complexity and what was learned from the implementation.

Uploaded by

2K18/CO/166 KAMAL ROHILLA
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

PROGRAM 4

AIM: WAP to perform push and pop operations on a stack


implemented using linked list.

THEORY: The other way of implementing the stack is by using linked


list. Push operation is implemented by inserting element at the
beginning of linked list. Pop operation is implemented by deleting
the node from the beginning of the linked list.

ALGORITHM:

a. Push:
1. Initialise the data of temp node with given data.
2. Assign the next of temp node with top.
3. Assign top with temp top.
b. Pop:
1. Check if stack is empty.
2. If yes return -1.
3. Else initialise temp node with top.
4. *top=*top->next;
5. Initialise data with temp->data.
6. Release temp from memory.
7. Return data.

CODE:

#include<iostream>

#include<stdlib.h>

using namespace std;

struct node

{
int data;

struct node* next;

};

struct node* Createstack()

return NULL;

int Isempty(struct node* top)

return top==NULL;

void push(struct node**top,int d)

struct node* temp=(struct node*)malloc(sizeof(struct node));

temp->data=d;

temp->next=*top;

*top=temp;

int pop(struct node**top)

{
int d;

struct node* temp;

if(Isempty(top))

return -1;

temp=*top;

*top=(*top)->next;

d=temp->data;

free(temp);

return d;

int main()

struct node* top=Createstack();

cout<<"Enter the data you want to put in stack\nPress -1 to stop


providing the input\n";

int d;

cin>>d;

while(d!=-1)

push(&top,d);

cin>>d;
}

cout<<"After performing pop operation on the stack"<<endl;

while(!Isempty(top))

cout<<pop(&top)<<" ";

return 0;

OUTPUT:

DISCUSSION:

Every operation takes O(1) constant time.

Every operation takes extra space and time to deal with references.

LEARNING:

I learnt that implementation of stack using linked list has extra space
complexity but it is done by dynamic memory allocation which
prevents any waste of memory whatsoever. I also learnt that all the
operations in this implementation take constant time.
FLOWCHARTS:

a. Push

Declare temp variable


of node type

Temp->data=data

Temp->next=*top

*top=temp
b. Pop:

Check if
Return stack is
empty

NO

Initialise temp variable of node type


with address of top node

*top=*top->next;

data=temp->data

free(temp)

Return data

You might also like