/
stack
177 lines (147 loc) · 4.79 KB
/
stack
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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
-> Basic concept:
In computer science, a stack is an abstract data type that serves as a collection of elements, with two principal operations:
push, which adds an element to the collection,
and pop, which removes the most recently added element that was not yet removed.
-> The order may be:
1. LIFO(Last In First Out): The last element inserted into the stack is removed first
2. FILO(First In Last Out): Where the first element to be inserted into the stack is removed at the last.
-> Mainly the following three basic operations are performed in the stack:
1. Push: Adds an item in the stack. If the stack is full, then it is said to be an Overflow condition.
2. Pop: Removes an item from the stack. The items are popped in the reversed order in which they are pushed.
If the stack is empty, then it is said to be an Underflow condition.
3. Peek or Top: Returns top element of stack.
4. isEmpty: Returns true if stack is empty, else false.
-> Understanding Stacks- Examples:
There are many real life examples of stack. Consider the simple example of plates stacked over one another in canteen.
The plate which is at the top is the first one to be removed, i.e. the plate which has been placed at the bottommost position
remains in the stack for the longest period of time.So, it can be simply seen to follow LIFO/FILO order.
-> Time Complexities of operations on stack:
push(), pop(), isEmpty() and peek() all take O(1) time. We do not run any loop in any of these operations.
-> Applications of stack:
1. Balancing of symbols
2. Infix to Postfix /Prefix conversion
3. Redo-undo features at many places like editors, photoshop.
4. Forward and backward feature in web browsers
5. Used in many algorithms like Tower of Hanoi, tree traversals, stock span problem, histogram problem.
6. Other applications can be Backtracking, Knight tour problem, rat in a maze, N queen problem and sudoku solver
7. In Graph Algorithms like Topological Sorting and Strongly Connected Components.
-> Implementation:
There are two ways to implement a stack:
1. Using array
2. Using linked list
1.) Implementattion using Arrays:
/* Java program to implement basic stack
operations */
class Stack
{
static final int MAX = 1000;
int top;
int a[] = new int[MAX]; // Maximum size of Stack
boolean isEmpty()
{
return (top < 0);
}
Stack()
{
top = -1;
}
boolean push(int x)
{
if (top >= (MAX-1))
{
System.out.println("Stack Overflow");
return false;
}
else
{
a[++top] = x;
System.out.println(x + " pushed into stack");
return true;
}
}
int pop()
{
if (top < 0)
{
System.out.println("Stack Underflow");
return 0;
}
else
{
int x = a[top--];
return x;
}
}
}
// Driver code
class Main
{
public static void main(String args[])
{
Stack s = new Stack();
s.push(10);
s.push(20);
s.push(30);
System.out.println(s.pop() + " Popped from stack");
}
}
Pros: Easy to implement. Memory is saved as pointers are not involved.
Cons: It is not dynamic. It doesn’t grow and shrink depending on needs at runtime.
2.) Implementation using LinkedLists:
// C program for linked list implementation of stack
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// A structure to represent a stack
struct StackNode
{
int data;
struct StackNode* next;
};
struct StackNode* newNode(int data)
{
struct StackNode* stackNode =
(struct StackNode*) malloc(sizeof(struct StackNode));
stackNode->data = data;
stackNode->next = NULL;
return stackNode;
}
int isEmpty(struct StackNode *root)
{
return !root;
}
void push(struct StackNode** root, int data)
{
struct StackNode* stackNode = newNode(data);
stackNode->next = *root;
*root = stackNode;
printf("%d pushed to stack\n", data);
}
int pop(struct StackNode** root)
{
if (isEmpty(*root))
return INT_MIN;
struct StackNode* temp = *root;
*root = (*root)->next;
int popped = temp->data;
free(temp);
return popped;
}
int peek(struct StackNode* root)
{
if (isEmpty(root))
return INT_MIN;
return root->data;
}
int main()
{
struct StackNode* root = NULL;
push(&root, 10);
push(&root, 20);
push(&root, 30);
printf("%d popped from stack\n", pop(&root));
printf("Top element is %d\n", peek(root));
return 0;
}
Pros: The linked list implementation of stack can grow and shrink according to the needs at runtime.
Cons: Requires extra memory due to involvement of pointers.