Stack
It is a linear data structure that follows a particular order in which the operations are
performed.
LIFO (Last In First Out)/ FILO:
This strategy states that the element that is inserted last will come out first.
You can take a pile of plates kept on top of each other as a real-life example. The
plate which we put last is on the top and since we remove the plate that is at the top, we
can say that the plate that was put last comes out first.
Basic Operations on Stack
In order to make manipulations in a stack, there are certain operations provided to us.
push() to insert an element into the stack
pop() to remove an element from the stack
top() Returns the top element of the stack.
PEEP : To find ith element from stack.
CHANGE : To change ith element from stack.
isEmpty() returns true is stack is empty else false
size() returns the size of stack
Stack
Push:
Adds an item to the stack. If the stack is full, then it is said to be an Overflow condition.
Algorithm for push:
begin
if stack is full
return
endif
else
increment top
stack[top] assign value
end else
end procedure
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.
Algorithm for pop:
begin
if stack is empty
return
endif
else
store value of stack[top]
decrement top
return value
end else
end procedure
Top:
Returns the top element of the stack.
Algorithm for Top:
begin
return stack[top]
end procedure
isEmpty:
Returns true if the stack is empty, else false.
Algorithm for isEmpty:
begin
if top < 1
return true
else
return false
end procedure
Complexity Analysis: Time Complexity
Operations Complexity
push() O(1)
pop() O(1)
isEmpty() O(1)
size() O(1)
Types of Stacks:
Register Stack: This type of stack is also a memory element present in the memory unit
and can handle a small amount of data only. The height of the register stack is always
limited as the size of the register stack is very small compared to the memory.
Memory Stack: This type of stack can handle a large amount of memory data. The height
of the memory stack is flexible as it occupies a large amount of memory data.
Applications of the stack:
Infix to Postfix /Prefix conversion
Redo-undo features at many places like editors, photoshop.
Forward and backward features in web browsers
Used in many algorithms like Tower of Hanoi, tree traversals, stock span problems,
and histogram problems.
Backtracking is one of the algorithm designing techniques. Some examples of
backtracking are the Knight-Tour problem, N-Queen problem, In Graph Algorithms
like Topological Sorting and Strongly Connected Components
In Memory management, any modern computer uses a stack as the primary management
for a running purpose. Each program that is running in a computer system has its own
memory allocations
String reversal is also another application of stack. Here one by one each character gets
inserted into the stack. So the first character of the string is on the bottom of the stack
and the last element of a string is on the top of the stack. After Performing the pop
operations on the stack we get a string in reverse order.
Implementation of Stack:
There are two ways to implement a stack
Using array
Using linked list
Implementing Stack using Arrays:
// C# program to implement basic stack// operations using
System;
namespace ImplementStack {
class Stack {
private int[] ele;
private int top;
private int max;
public Stack(int size)
{
ele = new int[size]; // Maximum size of Stack
top = -1;
max = size;
}
public void push(int item)
{
if (top == max - 1) {
Console.WriteLine("Stack Overflow");
return;
}
else {
ele[++top] = item;
}
}
public int pop()
{
if (top == -1) {
Console.WriteLine("Stack is Empty");
return -1;
}
else {
Console.WriteLine("{0} popped from stack ", ele[top]);
return ele[top--];
}
}
public int peek()
{
if (top == -1) {
Console.WriteLine("Stack is Empty");
return -1;
}
else {
Console.WriteLine("{0} popped from stack ", ele[top]);
return ele[top];
}
}
public void printStack()
{
if (top == -1) {
Console.WriteLine("Stack is Empty");
return;
}
else {
for (int i = 0; i <= top; i++) {
Console.WriteLine("{0} pushed into stack", ele[i]);
}
}
}
}
// Driver program to test above functions
class Program {
static void Main()
{
Stack p = new Stack(5);
p.push(10);
p.push(20);
p.push(30);
p.printStack();
p.pop();
}
}
}
Output
10 pushed into stack
20 pushed into stack
30 pushed into stack
30 Popped from stack
Top element is : 20
Elements present in stack : 20 10
Advantages of array implementation:
Easy to implement.
Memory is saved as pointers are not involved.
Disadvantages of array implementation:
It is not dynamic.
It doesn’t grow and shrink depending on needs at runtime.
Implementing Stack using Linked List:
// C# Code for Linked List Implementation
using System;
public class StackAsLinkedList {
StackNode root;
public class StackNode {
public int data;
public StackNode next;
public StackNode(int data) { this.data = data; }
}
public bool isEmpty()
{
if (root == null) {
return true;
}
else
return false;
}
public void push(int data)
{
StackNode newNode = new StackNode(data);
if (root == null) {
root = newNode;
}
else {
StackNode temp = root;
root = newNode;
newNode.next = temp;
}
Console.WriteLine(data + " pushed to stack");
}
public int pop()
{
int popped = int.MinValue;
if (root == null) {
Console.WriteLine("Stack is Empty");
}
else {
popped = root.data;
root = root.next;
}
return popped;
}
public int peek()
{
if (root == null) {
Console.WriteLine("Stack is empty");
return int.MinValue;
}
else {
return root.data;
}
}
// Driver code
public static void Main(String[] args)
{
StackAsLinkedList sll = new StackAsLinkedList();
sll.push(10);
sll.push(20);
sll.push(30);
Console.WriteLine(sll.pop() + " popped from stack");
Console.WriteLine("Top element is " + sll.peek());
}
}
/* This code contributed by PrinciRaj1992 */
Output
10 pushed to stack
20 pushed to stack
30 pushed to stack
30 popped from stack
Top element is 20
Elements present in stack : 20 10
Advantages of Linked List implementation:
The linked list implementation of a stack can grow and shrink according to the needs at
runtime.
It is used in many virtual machines like JVM.
Stacks are more secure and reliable as they do not get corrupted easily.
Stack cleans up the objects automatically.
Disadvantages of Linked List implementation:
Requires extra memory due to the involvement of pointers.
Random accessing is not possible in stack.
The total size of the stack must be defined before.
If the stack falls outside the memory it can lead to abnormal termination.
