Добавить в FixedCapacityStackOfStrings метод isFull()
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
class FixedCapacityStackOfStrings { private string[] a; public int N; public FixedCapacityStackOfStrings(int ACapacity) { a = new string[ACapacity]; } public bool isEmpty() { return N == 0; } public bool isFull() { return N == a.Length; } // <<< public int size() { return N; } public void push(string item) { a[N++] = item; } public string pop() { return a[--N]; } } |
Балансировка скобок
На уровне псевдокода
– Все скобки либо левые либо правые
– Все скобки разных типов – квадратные, круглые, фигурные
– Скобки одного типа могут быть “левая с правой”, например [], а скобки разного типа не могут быть левая с правой [ ), то есть, для метода Pop(), при доставании из стека, мы можем проверять запрещенные комбинации (] (} {) {] (} (] и вызывать исключение
– Кроме того, число скобок разных типов должно быть четным
Двоичное представление
|
1 2 3 4 5 6 7 8 |
int N = 50; Stack<int> st = new Stack<int>(); while (N > 0) { st.Push(N%2); N = N / 2; } foreach (var i in st) Console.Write(i); |
Этот код переводит из десятичной, в двоичную систему исчисления. Результат для числа 50 будет 110001
Что делает следующий фрагмент с очередью?
Например в очереди были значения 1,2,3,4,5 после попадания в стек они перевернулись 5,4,3,2,1, при попадании в очередь, будет 5,4,3,2,1
То есть, по сути это операция реверса.
Peek для стэка
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class FixedCapacityStackOfStrings { private string[] a; public int N; public FixedCapacityStackOfStrings(int ACapacity) { a = new string[ACapacity]; } public bool isEmpty() { return N == 0; } public bool isFull() { return N == a.Length - 1 + 1; } public int size() { return N; } public void push(string item) { a[N++] = item; } public string pop() { return a[--N]; } public string peek() { return a[N-1]; } } |
Написать класс копирования стэка
|
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 |
class CopyStack<T> : IEnumerable<T> { private CustomStackLinkedList<T> resultStack; private CustomStackLinkedList<T> copiedSt; public CopyStack() { resultStack = new CustomStackLinkedList<T>(); copiedSt = new CustomStackLinkedList<T>(); } public CopyStack(CustomStackLinkedList<T> st) { resultStack = new CustomStackLinkedList<T>(); copiedSt = new CustomStackLinkedList<T>(); Execute(st); } public CustomStackLinkedList<T> Execute(CustomStackLinkedList<T> st) { foreach (var s in st) copiedSt.push(st.pop()); foreach (var s in copiedSt) resultStack.push(copiedSt.pop()); return resultStack; } System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return GetEnumerator(); } public IEnumerator<T> GetEnumerator() { return resultStack.GetEnumerator(); } } |
И сам класс стэка на связных списках
|
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 |
class CustomStackLinkedList<T> : IEnumerable<T> { Node<T> first; private int N; class Node<T> { public T item; public Node<T> next; } public bool isEmpty() { return (first == null) || (N == 0); } public int size() { return N; } public void push(T item) { // adding to the begining Node<T> oldfirst = first; first = new Node<T>(); first.item = item; first.next = oldfirst; N++; } public T pop() { T item = first.item; first = first.next; N--; return item; } System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return GetEnumerator(); } public IEnumerator<T> GetEnumerator() { var node = first; while (node != null) { yield return node.item; node = node.next; } } } |
Связные списки
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
public void DeleteLastNode() { var node = first; while (node != null) { if (node.next.next == null) { //delete last node node.next = null; } node = node.next; } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
public void DeleteNode(int k) { int i = 0; var node = first; Node<T> previousNode = first; while ((i!=k)||(node!=null)) { node = node.next; if (previousNode != node) // initially they both on first level previousNode = previousNode.next; i++; } if (i == k) { previousNode.next = previousNode.next.next; } } |
|
1 2 3 4 5 6 7 |
public void RemoveAfter(Node<T> node) { if (node.next != null) { node.next = node.next.next; } } |