Implement Stack in Array:
/// <summary> /// Stack implementation using array /// </summary>
public class Stack { private const int MaxSize = 10; private object[] _items = new object[MaxSize]; private int _currentIndex = -1; public Stack() { }
/// <summary> /// Push operation
/// </summary> public void Push(object element) { if (_currentIndex >= MaxSize - 1) { throw new InvalidOperationException("Stack is full"); } _currentIndex++; _items[_currentIndex] = element; }
public object Pop() { if (IsEmpty()) { throw new InvalidOperationException("No elements in stack"); } object element = _items[_currentIndex]; _items[_currentIndex] = null; _currentIndex--; return element; }
public object Peek() { if (IsEmpty()) { throw new InvalidOperationException("No elements in stack"); } return _items[_currentIndex]; }
public bool IsEmpty() { if (_currentIndex < 0) { return true; } else { return false; } } }
|
Implement Stack in Linklist
public class Node { public int Data { get; set; } public Node Next { get; set; } } Node current = null; int nodecount = 0; public void Push(int value) { Node newNode = new Node(); newNode.Data = value; Node prev = current; if (prev == null) { current = newNode; prev = current; } else { prev = current; current = newNode; current.Next = prev; } nodecount++; } public void POP() { current = current.Next; nodecount--; } public void peek() { Console.WriteLine(current.Data); } public void IsEmpty() { if (nodecount==0) Console.WriteLine("Empty"); }
|
Queue using array
public class Queue { private int[] data; private int size; private int front = -1; private int back = 0; private int count = 0; public Queue() { size = 10; data = new int[size]; } public Queue(int size) { this.size = size; data = new int[size]; } public bool IsEmpty() { return count == 0; } public bool IsFull() { return count == size; }
public void Add(int i) { if (IsFull()) throw new ApplicationException("Queue full"); else { count++; data[back++ % size] = i; } } public int Remove() { if (IsEmpty()) throw new ApplicationException("Queue empty"); else { count--; return data[++front % size]; } } public int Head() { if (IsEmpty()) { throw new ApplicationException("Queue empty"); } else return data[(front + 1) % size]; }
|
Infix to Postfix conversion using Stack
/// <summary> /// Convert an Infix Experession to Postfix Expression /// </summary> public static void InfixToPostFix() { string exp = "a+b*(c^d-e)^(f+g*h)-i"; char[] infix = exp.ToCharArray(); //Stack to maintain operators and braces char[] stack = new char[infix.Length]; int top = -1; int index = -1; for (int i = 0; i < infix.Length; i++) { // If the scanned character is an operand, add it to output. if (isOperand(infix[i])) infix[++index] = infix[i]; // If the scanned character is an ‘(‘, push it to the stack. else if (infix[i] == '(') stack[++top] = infix[i]; // If the scanned character is an ‘)’, pop and output from the stack // until an ‘(‘ is encountered. else if (infix[i] == ')') { while (top != -1 && stack[top] != '(') { infix[++index] = stack[top--]; } if (top != -1) { //Remove '(' from stack top--; } } else // an operator is encountered { while (top != -1 && Prec(infix[i]) <= Prec(stack[top])) //Pop from stack infix[++index] = stack[top--]; //push into the stack stack[++top] = infix[i]; } } // pop all the operators from the stack while (top != -1) infix[++index] = stack[top--]; //Print only string to the index (we have removed braces so strng will get short now) Console.WriteLine(new string(infix).Substring(0, index+1)); } // A utility function to check if the given character is operand private static bool isOperand(char ch) { return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'); } // A utility function to return precedence of a given operator // Higher returned value means higher precedence private static int Prec(char ch) { switch (ch) { case '+': case '-': return 1; case '*': case '/': return 2; case '^': return 3; } return -1; }
|
// <summary> /// Evaluate postfix Expression /// </summary> public static void EvaluatePostfix() { string exp = "231*+9-"; char[] postfix = exp.ToCharArray(); //Stack to maintain evaluation result int[] stack = new int[postfix.Length]; int top = -1; int index = -1; for (int i = 0; i < postfix.Length; i++) { // If the scanned character is an operand or number, // push it to the stack. if (postfix[i] >= '0' && postfix[i] <= '9') stack[++top] = Convert.ToInt32(postfix[i] - '0'); else { //pop two values and do operation then push it back int val1 = stack[top--]; int val2 = stack[top--]; switch (postfix[i]) { case '+': stack[++top] = val2 + val1; break; case '-': stack[++top] = val2 - val1; break; case '*': stack[++top] = val2 * val1; break; case '/': stack[++top] = val2 / val1; break; } } } Console.WriteLine(stack[top]); }
|
/// <summary> /// Implement two stacks in an array /// </summary> class TwoStack { int[] arr = null; int size; int top1, top2; public TwoStack(int n) { size = n; arr = new int[size]; // first stack starting point (from first) top1 = -1; //Second stack starting point (From last) top2 = size; } /// <summary> /// Push value in first/second stack based on flag /// </summary> /// <param name="x"></param> /// <param name="InFirstStack"></param> public void Push(int x, bool InFirstStack) { if (InFirstStack) { if (top1 < top2 - 1) arr[++top1] = x; else Console.WriteLine("Stack Overflow"); } else { if (top1 < top2 - 1) arr[--top2] = x; else Console.WriteLine("Stack Overflow"); } } /// <summary> /// Pop Value from first/second Stack based on flag /// </summary> /// <param name="FromFirstStack"></param> /// <returns></returns> public int Pop(bool FromFirstStack) { if (FromFirstStack) { if (top1 >= 0) return arr[top1--]; else { Console.WriteLine("Stack Underflow"); return -1; } } else { if (top2 < size) return arr[top2++]; else { Console.WriteLine("Stack Underflow"); return -1; } } }
|
/// <summary> /// Given an array, print the Next Greater Element (NGE) for every element. /// The Next greater Element for an element x is the first greater element /// on the right side of x in array.Elements for which no greater element exist, /// consider next greater element as -1. /// For the input array [4, 5, 2, 25}, the next greater elements for each element are as follows. /// 4 --> 5, 5 --> 25, 2 --> 25, 25 --> -1 /// </summary> public static void NextGreaterElement() { int[] arr = { 4, 5, 2, 25 }; int n = arr.Length; int[] stack = new int[n]; int top = -1; int element, next; /* push the first element to stack */ stack[++top] = arr[0]; // iterate for rest of the elements for (int i = 1; i < n; i++) { next = arr[i]; if (top != -1) { // if stack is not empty, then pop an element from stack element = stack[top--]; /* If the popped element is smaller than next, then a) print the pair b) keep popping while elements are smaller and stack is not empty */ while (element < next) { Console.WriteLine("{0} --> {1}", element, next); if (top == -1) break; element = stack[top--]; } // If element is greater than next, then push the element back if (element > next) stack[++top] = element; } //push next to stack so that we can find next greater for it stack[++top] = next; } // After iterating over the loop, the remaining // elements in stack do not have the next greater // element, so print -1 for them */ while (top != -1) { element = stack[top--]; Console.WriteLine("{0} --> -1", element); } }
|
/// <summary> /// Print Binary representation of number /// </summary> public static void PrintBinaryNumber() { int n = 20; int[] stack = new int[16]; int top = -1; while (n > 0) { stack[++top] = n % 2; n = n / 2; } while(top != -1) Console.Write(stack[top--]); }
|
Monday, 8 February 2016
suman microsoft stacks
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment