Stack
is an abstract data type with a bounded (predefined) capacity. It is a simple
data structure that allows adding and removing elements in a particular order.
Every time an element is added, it goes on the top of the stack, the only
element that can be removed is the element that was at the top of the stack,
just like a pile of objects.
Basic
features of Stack
Stack
is an ordered list of similar data type.
Stack
is a LIFO structure. (Last in First out).
push() function is
used to insert new elements into the Stack and pop() is used
to delete an element from the stack. Both insertion and deletion are allowed at
only one end of Stack called Top.
Stack
is said to be in Overflow state when it is completely full and
is said to be in Underflow state if it is completely empty.
Java
program to create Stack using array:
Implement
stack using array. Define the size of array and declare an in pointer top
Initialize
the top with -1, when you push an element increment the top with 1 so top will
always point the latest inserted element.
When
we pop the top element decrement the top by 1.
package com.mk.ds.stack;
public class Stack {
private int size;
private int top;
private int[] stackArr;
public Stack(int size){
stackArr = new int[size];
this.size = size;
top = -1;
}
public void push(int value){
if(size == top) {
throw new RuntimeException("stack is full");
}
stackArr[++top] = value;
}
public int pop(){
if(top < 0) {
throw new RuntimeException("stack is empty");
}
int topValue = stackArr[top--];
return topValue;
}
public boolean isEmpty(){
if(top < 0) {
return true;
}
return false;
}
public int size(){
return size;
}
public static void main(String[] args){
Stack stack = new Stack(10);
for(int val = 11 ; val < 21 ; val++) {
stack.push(val);
} // insertion order 11 12 13 14 15 16 17 18 19 20
while (!stack.isEmpty()) {
System.out.print(stack.pop());
} // pop from top first
// 20 19 18 17 16 15 14 13 12 11
}
}
public class Stack {
private int size;
private int top;
private int[] stackArr;
public Stack(int size){
stackArr = new int[size];
this.size = size;
top = -1;
}
public void push(int value){
if(size == top) {
throw new RuntimeException("stack is full");
}
stackArr[++top] = value;
}
public int pop(){
if(top < 0) {
throw new RuntimeException("stack is empty");
}
int topValue = stackArr[top--];
return topValue;
}
public boolean isEmpty(){
if(top < 0) {
return true;
}
return false;
}
public int size(){
return size;
}
public static void main(String[] args){
Stack stack = new Stack(10);
for(int val = 11 ; val < 21 ; val++) {
stack.push(val);
} // insertion order 11 12 13 14 15 16 17 18 19 20
while (!stack.isEmpty()) {
System.out.print(stack.pop());
} // pop from top first
// 20 19 18 17 16 15 14 13 12 11
}
}
Java
program to create Stack using Linkedlist:
Implement
stack using linked List, refer below code snippet-
package com.mk.ds.stack;
public class StackUsingLinkedList {
private Node top;
private static class Node {
int data; // integer data
Node next; // pointer to the next node
}
public StackUsingLinkedList() {
this.top = null;
}
public void push(int x) {
Node node = new Node();
if (node == null) {
throw new RuntimeException("Overflow");
}
node.data = x;
node.next = top;
top = node;
}
public boolean isEmpty(){
if(top == null) {
return true;
}
return false;
}
public int pop() {
if (top == null) {
throw new RuntimeException("underflow");
}
int data = top.data;
top = top.next;
return data;
}
}
class StackImpl {
public static void main(String[] args) {
StackUsingLinkedList stack = new StackUsingLinkedList();
for(int val = 11 ; val < 21 ; val++) {
stack.push(val);
} // insertion order 11 12 13 14 15 16 17 18 19 20
while (!stack.isEmpty()) {
System.out.print(stack.pop()+ " ");
} // pop from top first
// 20 19 18 17 16 15 14 13 12 11
}
}
public class StackUsingLinkedList {
private Node top;
private static class Node {
int data; // integer data
Node next; // pointer to the next node
}
public StackUsingLinkedList() {
this.top = null;
}
public void push(int x) {
Node node = new Node();
if (node == null) {
throw new RuntimeException("Overflow");
}
node.data = x;
node.next = top;
top = node;
}
public boolean isEmpty(){
if(top == null) {
return true;
}
return false;
}
public int pop() {
if (top == null) {
throw new RuntimeException("underflow");
}
int data = top.data;
top = top.next;
return data;
}
}
class StackImpl {
public static void main(String[] args) {
StackUsingLinkedList stack = new StackUsingLinkedList();
for(int val = 11 ; val < 21 ; val++) {
stack.push(val);
} // insertion order 11 12 13 14 15 16 17 18 19 20
while (!stack.isEmpty()) {
System.out.print(stack.pop()+ " ");
} // pop from top first
// 20 19 18 17 16 15 14 13 12 11
}
}
Check
if an expression is a balanced expression
If
current braces is ( or { or [ than push it into stack.
If
current braces is closing ) or } or ] than pop from stack, if braces is not
available in stack than expression in not balanced. Please refer below code
snippet-
package com.mk.ds.stack;
public class StackUsingLinkedList {
private Node top;
private static class Node {
char data; // integer data
Node next; // pointer to the next node
}
public StackUsingLinkedList() {
this.top = null;
}
public void push(char value) {
Node node = new Node();
if (node == null) {
throw new RuntimeException("Overflow");
}
node.data = value;
node.next = top;
top = node;
}
public boolean isEmpty(){
if(top == null) {
return true;
}
return false;
}
public char pop() {
if (top == null) {
throw new RuntimeException("underflow");
}
char data = top.data;
top = top.next;
return data;
}
}
class StackImpl {
public static void main(String[] args) {
StackImpl stackImpl = new StackImpl();
char[] balArr = {'{','[',']','}'};
char[] unBalArr = {'{','[','}'};
System.out.println("Balanced expression : "+stackImpl.checkBalanced(balArr));
System.out.println("Balanced expression : "+stackImpl.checkBalanced(unBalArr));
}
public boolean checkBalanced(char[] array){
StackUsingLinkedList stack = new StackUsingLinkedList();
for(int count = 0; count < array.length; count++) {
if(array[count] == '(' || array[count] == '{' || array[count] == '[' ) {
stack.push(array[count]);
}
else if (array[count] == ')' || array[count] == '}' || array[count] == ']' ) {
if(stack.isEmpty())
return false;
char top = stack.pop();
if(top == '(' && array[count] != ')'
|| top == '{' && array[count] != '}'
|| top == '[' && array[count] != ']' ) {
return false;
}
}
}
return stack.isEmpty();
}
}
public class StackUsingLinkedList {
private Node top;
private static class Node {
char data; // integer data
Node next; // pointer to the next node
}
public StackUsingLinkedList() {
this.top = null;
}
public void push(char value) {
Node node = new Node();
if (node == null) {
throw new RuntimeException("Overflow");
}
node.data = value;
node.next = top;
top = node;
}
public boolean isEmpty(){
if(top == null) {
return true;
}
return false;
}
public char pop() {
if (top == null) {
throw new RuntimeException("underflow");
}
char data = top.data;
top = top.next;
return data;
}
}
class StackImpl {
public static void main(String[] args) {
StackImpl stackImpl = new StackImpl();
char[] balArr = {'{','[',']','}'};
char[] unBalArr = {'{','[','}'};
System.out.println("Balanced expression : "+stackImpl.checkBalanced(balArr));
System.out.println("Balanced expression : "+stackImpl.checkBalanced(unBalArr));
}
public boolean checkBalanced(char[] array){
StackUsingLinkedList stack = new StackUsingLinkedList();
for(int count = 0; count < array.length; count++) {
if(array[count] == '(' || array[count] == '{' || array[count] == '[' ) {
stack.push(array[count]);
}
else if (array[count] == ')' || array[count] == '}' || array[count] == ']' ) {
if(stack.isEmpty())
return false;
char top = stack.pop();
if(top == '(' && array[count] != ')'
|| top == '{' && array[count] != '}'
|| top == '[' && array[count] != ']' ) {
return false;
}
}
}
return stack.isEmpty();
}
}
Outout-
Balanced
expression : true
Balanced
expression : false
Reverse
a stack
To
reverse a stack we can use a temporary stack and push all element into this temporary
stack, now all the element into this new stack are in reversed order.
Nice information, very usefull thanks
ReplyDeletenice programs for Btech students
ReplyDelete