-
Notifications
You must be signed in to change notification settings - Fork 16
Expand file tree
/
Copy pathP4.java
More file actions
118 lines (95 loc) · 3.22 KB
/
P4.java
File metadata and controls
118 lines (95 loc) · 3.22 KB
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
package stack_and_queue;
// Problem Title => Java Program to implement a stack that supports findMiddle() and deleteMiddle in O(1) time
public class P4 {
/* A Doubly Linked List Node */
static class DLLNode {
DLLNode prev;
int data;
DLLNode next;
// Constructor
DLLNode(int d) {
data = d;
}
}
// Representation of the stack data structure that supports findMiddle() in O(1) time.
// The Stack is implemented using Doubly Linked List.
// It maintains pointer to head node, pointer to middle node and count of nodes.
static class myStack {
DLLNode head;
DLLNode mid;
int count;
}
/* Function to create the stack data structure */
myStack createMyStack() {
myStack ms = new myStack();
ms.count = 0;
return ms;
}
/* Function to push an element to the stack */
void push(myStack ms, int new_data) {
/* allocate DLLNode and put in data */
DLLNode new_DLLNode = new DLLNode(new_data);
/*
* Since we are adding at the beginning, prev is always NULL
*/
new_DLLNode.prev = null;
/* link the old linkedList.list off the new DLLNode */
new_DLLNode.next = ms.head;
/* Increment count of items in stack */
ms.count += 1;
// Change mid_pointer in two cases 1) Linked List is empty 2) Number of nodes in linked linkedList.list is odd
if (ms.count == 1)
ms.mid = new_DLLNode;
else {
ms.head.prev = new_DLLNode;
if ((ms.count % 2) != 0) // Update mid if ms->count is odd
ms.mid = ms.mid.prev;
}
/* move head to point to the new DLLNode */
ms.head = new_DLLNode;
}
/* Function to pop an element from stack */
int pop(myStack ms) {
/* Stack underflow */
if (ms.count == 0) {
System.out.println("Stack is empty");
return -1;
}
DLLNode head = ms.head;
int item = head.data;
ms.head = head.next;
// If linked linkedList.list doesn't become empty,
// update prev of new head as NULL
if (ms.head != null)
ms.head.prev = null;
ms.count -= 1;
// update the mid_pointer when we have even_number of elements in the stack,
// i,e move down the mid_pointer.
if (ms.count % 2 == 0)
ms.mid = ms.mid.next;
return item;
}
// Function for finding middle of the stack
int findMiddle(myStack ms) {
if (ms.count == 0) {
System.out.println("Stack is empty now");
return -1;
}
return ms.mid.data;
}
// Driver program to test functions of myStack
public static void main(String[] args) {
P4 ob = new P4();
myStack ms = ob.createMyStack();
ob.push(ms, 11);
ob.push(ms, 22);
ob.push(ms, 33);
ob.push(ms, 44);
ob.push(ms, 55);
ob.push(ms, 66);
ob.push(ms, 77);
System.out.println("Item popped is " + ob.pop(ms));
System.out.println("Item popped is " + ob.pop(ms));
System.out.println("Middle Element is " + ob.findMiddle(ms));
}
}