Stack and Queue
- Queue: First in First out (FIFO)
- Stack: Last in First out (LIFO)
Linked List Implementation
ListNode
class ListNode <AnyType>{
public ListNode(AnyType Myelement) {
this(Myelement, null);
}
public ListNode(AnyType Myelement, ListNode<AnyType> n) {
element = Myelement;
next = n;
}
public AnyType element;
public ListNode<AnyType> next;
}
Stack
public class stack<AnyType>
{
private ListNode<AnyType> top;
public stack(){
top = null;
}
public boolean isEmpty(){
if(top == null)
return true;
else
return false;
}
public void push(AnyType value){
if(top == null){
top = new ListNode<AnyType>(value);
}
else {
ListNode<AnyType> newNode = new ListNode<AnyType>(value);
newNode.next = top;
top = newNode;
}
}
public void pop() {
if(top == null){
System.out.println("Empty stack");
}
else {
top = top.next;
}
}
public void peek(){
if(top == null){
System.out.println("Empty stack");
}
else {
AnyType TopValue = top.element;
System.out.println(TopValue);
}
}
public void peekAndpop(){
if(top == null){
System.out.println("Empty stack");
}
else {
AnyType TopValue = top.element;
System.out.println(TopValue);
top = top.next;
}
}
}
Queue
public class queue<AnyType>{
private ListNode<AnyType> head;
private ListNode<AnyType> tail;
public queue() {
head = null;
tail = null;
}
public void enqueue(AnyType val) {
if(head == null) {
head = new ListNode<AnyType>(val);
tail = head;
}
else {
tail.next = new ListNode<AnyType>(val);
tail = tail.next;
}
}
public ListNode dequeue() {
if(head == null) {
System.out.println("Queue is Empty");
return null;
}
else {
ListNode<AnyType> temp = head;
head = head.next;
temp.next = null;
return temp;
}
}
public boolean isEmpty(){
if(head == null)
return true;
else
return false;
}
public void display() {
ListNode cur = head;
while(cur != null) {
System.out.println(cur.element);
cur = cur.next;
}
}
}
Array Implementation
Stack
public class ArrayStack<AnyType> {
private AnyType [] arrayStack;
private int capacity;
private int size;
public ArrayStack() {
size = 0;
capacity = 4;
arrayStack = (AnyType[]) new Object[capacity];
}
public void push(AnyType value) {
checkCapacity();
for(int i = size; i >= 1; i--) {
arrayStack[i] = arrayStack[i-1];
}
arrayStack[0] = value;
size++;
}
public AnyType pop() {
if(size == 0) {
System.out.println("stack is empty");
return null;
}
else {
AnyType temp = arrayStack[0];
for(int i = 0; i < size-1; i++) {
arrayStack[i] = arrayStack[i+1];
}
arrayStack[size-1] = null;
size--;
return temp;
}
}
public AnyType peek() {
if(size == 0) {
System.out.println("stack is empty");
return null;
}
else {
System.out.print(arrayStack[0]);
return arrayStack[0];
}
}
private void checkCapacity() {
if(size >= capacity) {
AnyType [] temp = arrayStack;
arrayStack = (AnyType[]) new Object[capacity*2];
for(int i = 0; i < capacity; i++) {
arrayStack[i] = temp[i];
}
capacity *= 2;
}
}
}
Queue
public class ArrayQueue<AnyType> {
private AnyType [] arrayQueue;
private int capacity;
private int size;
public ArrayQueue() {
size = 0;
capacity = 4;
arrayQueue = (AnyType[]) new Object[capacity];
}
public void enqueue(AnyType value) {
checkCapacity();
arrayQueue[size] = value;
size++;
}
public AnyType dequeue() {
if(size == 0) {
System.out.println("Queue is empty");
return null;
}
else {
AnyType temp = arrayQueue[0];
for(int i = 0; i < size-1; i++) {
arrayQueue[i] = arrayQueue[i+1];
}
arrayQueue[size-1] = null;
size--;
return temp;
}
}
private void checkCapacity() {
if(size >= capacity) {
AnyType [] temp = arrayQueue;
arrayQueue = (AnyType[]) new Object[capacity*2];
for(int i = 0; i < capacity; i++) {
arrayQueue[i] = temp[i];
}
capacity *= 2;
}
}
public AnyType peek() {
if(size == 0) {
System.out.println("stack is empty");
return null;
}
else {
System.out.print(arrayQueue[0]);
return arrayQueue[0];
}
}
}