-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathCode : Stack Using LL
95 lines (78 loc) · 2.4 KB
/
Code : Stack Using LL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
You need to implement a Stack class using linked list.
The data members should be private.
Implement the following public functions :
1. Constructor -
Initialises the data member (i.e. head to null).
2. push :
This function should take one argument of type T and has return type void. This function should insert an element in the stack. Time complexity should be O(1).
3. pop :
This function takes no input arguments and has return type T. This should removes the last element which is entered and return that element as an answer. Time complexity should be O(1).
4. top :
This function takes no input arguments and has return type T. This should return the last element which is entered and return that element as an answer. Time complexity should be O(1).
5. size :
Return the size of stack i.e. count of elements which are present ins stack right now. Time complexity should be O(1).
6. isEmpty :
Checks if the stack is empty or not. Return true or false.
----------------------------Solution----------------------------------
template <typename T>
class node{
public:
T data;
node<T>* next;
node<T>* prev;
node(T data){
this->data=data;
prev=NULL;
next=NULL;
}
};
template <typename T>
class Stack {
node<T> *head;
node<T>* tail;
int size; // number of elements prsent in stack
public :
Stack() {
head=NULL;
tail=NULL;
size=0;
}
int getSize() {
return size;
}
bool isEmpty() {
return size==0;
}
void push(T element) {
node<T>* newnode=new node<T>(element);
if(head==NULL){
head=newnode;
tail=newnode;
}else{
tail->next=newnode;
node<T>* temp=tail;
tail=newnode;
tail->prev=temp;
}
size++;
}
T pop() {
// Return 0 if stack is empty. Don't display any other message
if(size==0) return 0;
/* T ans=tail->data;
node<T>* temp=tail;
tail=tail->prev;
temp->prev=NULL;
tail->next=NULL;*/
node<T>* temp=tail;
tail=tail->prev;
temp->prev=NULL;
size--;
return temp->data;
}
T top() {
// Return 0 if stack is empty. Don't display any other message
if(size==0) return 0;
return tail->data;
}
};