-
Notifications
You must be signed in to change notification settings - Fork 1
/
Stack_with_operations_on_middle_element.cpp
134 lines (109 loc) · 2.34 KB
/
Stack_with_operations_on_middle_element.cpp
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/*
Problem Statement:
------------------
How to implement a stack which will support following operations in O(1) time complexity?
1) push() which adds an element to the top of stack.
2) pop() which removes an element from top of stack.
3) findMiddle() which will return middle element of the stack.
4) deleteMiddle() which will delete the middle element.
*/
// Link --> https://www.geeksforgeeks.org/design-a-stack-with-find-middle-operation/
// Code:
#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
int data;
Node *prev, *next;
Node()
{
prev = next = NULL;
}
};
class Stack : public Node
{
private:
Node *head;
Node *middle;
int counter;
public:
Stack()
{
head = middle = NULL;
counter = 0;
}
bool isEmpty()
{
if (head == NULL)
return true;
return false;
}
void push(int data)
{
counter++;
Node *node = new Node();
node->data = data;
cout << data << " is pushed in." << endl;
node->prev = NULL;
node->next = head;
if (head != NULL)
head->prev = node;
head = node;
if (counter == 1)
middle = node;
else
{
if (!(counter & 1))
middle = middle->prev;
}
}
void pop()
{
if (counter == 0 || isEmpty())
cout << "\nStack is empty." << endl;
Node *temp = head;
head = head->next;
if (head != NULL)
head->prev = NULL;
counter--;
// if counter is odd.
if (counter & 1)
middle = middle->next;
cout << temp->data << " is popped out." << endl;
free(temp);
}
void middleElement()
{
if (counter == 0)
cout << "\nStack is empty." << endl;
cout << "\nMiddle element is : " << middle->data << endl;
}
void display()
{
Node *temp;
while (temp->next != NULL)
{
cout << temp->data;
temp = temp->next;
}
cout << endl;
}
};
int main()
{
Stack s;
s.push(11);
s.push(22);
s.push(33);
s.push(44);
s.push(55);
s.push(66);
s.push(77);
s.middleElement();
s.pop();
s.pop();
s.pop();
s.middleElement();
return 0;
}