Algorithms Reading Notes 1.3 Backpacks, Queues and Stacks

Links to the original text: http://www.cnblogs.com/viinye/archive/2012/12/22/2829160.html

Chapter 1

Structure of this chapter

1.1 Java grammar

1.2 Data Abstraction

1.3 Collection class abstract data types: Bags, Queues, Stacks

1.4 Operational-oriented abstract data types

1.5 Connectivity Problem-Case Study: Union-Find ADT

 

There are two main contents of this note:

1. Two key characteristics of abstract data types of set classes: Generic Iterable summary;

2. The different characteristics of three basic set data types, knapsack, queue and stack, and their implementation analysis.

 

Generics and iterations

1. Generics, also known as parameterized types, can be used to store arbitrary data types. In each API, the < Item > notation after the class name defines Item as a type parameter, which is a symbolic placeholder, representing a specific data type that the use case will use. Stack < Item > can be understood as "a stack of elements". Item can be replaced by any reference data type. With the help of generics, our API can process all types of data at once, even those that are defined only in the future.

For some historical and technical reasons, creating generic arrays is not allowed in Java, and type conversion is required.

  1: Item[] a = (item[]) new Object[cap];

Java will automatically cast a primitive type to a wrapper type.

Autoboxing - Type parameters must be instantiated as reference types. Java's Wrapper Types - Builtin reference types include static methods such as parseInt(); instance methods such as toString(); compareTo(); equals(). Automatically converting an original data type into an encapsulated data type is called auto-encapsulation, and automatically converting an encapsulated data type into an original data type is called auto-encapsulation.

 

2. Iteration: Accessing all elements in a collection in some way. This grammar should be the foreachc statement in C #. The main reason Why we use the iteration statement is that the code can become concise and fresh, and does not depend on the specific implementation of the set data type.

  1: for (Transaction t : collection)

  2: { StdOut.println(t); }

The foreach above here is just a shorthand for the while statement:

  1: while (t.hasNext())

  2: {

  3:     String s = t.next();

  4:     StdOut.println(s);

  5: }

In any iterative set data type, to achieve the iteratability of a class, it is necessary to:

a. Add import java.util.Iterator at the beginning of the program;

b. Include in the class declaration statements related to Iterable interfaces that inherit Java definitions:

  1: public interface Iterable<Item>

  2: {

  3:     Iterator<Item> iterator();

  4: }

Note: Iterable has a method that returns an Iterator method.

c. Implement the iterator() method in the class, which returns an object Iterator < Item> from the class that implements the Iterator interface. We then implement hasNext() and next() methods in the iterator.

  1: public Iterator<Item> iterator()

  2: {    return new ReverseArrayIterator();    }

  3: public class ReverseArrayIterator implements Iterator<Item>

  4: {

  5:     private int i = N;

  6:     public boolean hasNext() {  return i > 0;  }

  7:     public    Item next()    {  return a[--i]; }  

  8:     public    void remove()  {                 }

  9: }

Note: Exceptions need to be thrown in two cases: Unsupported OperationException is thrown if the use case calls remove(), and NoSuchElementException is thrown if i is 0 when the use case calls next().

 

Backpacks, queues and stacks

1. Stack (Down Stack)

Basic Classification of Stacks

Fixed-Capacity Stacks: cap is the maximum capacity, and if the set becomes larger than the array, the use case may Overflow.

b. Adjustable array size stack: In order to solve the problem of memory wasting by large-capacity arrays and overflow caused by small-capacity arrays, the length of arrays will be doubled automatically when no extra space is found on the stack; similarly, if the top element of the stack is deleted, if the array is too large (the stack size is less than a quarter of the array), the array length will be doubled automatically. Halve the degree. From this we can see that the utilization rate of non-empty stack is always between 25% and 100%.

Aspects to consider for stacks

A. Avoid Loitering, which saves a reference to an object that is not needed, for example

  1: public String pop()

  2: {  return a[--N];  }

Although a[N] still exists here, it is no longer needed. Improvement plan:

  1: public String pop()

  2: {

  3:     String item = a[--N];

  4:     a[N] = null;

  5:     return item;

  6: }

In this way, a[N] can be recycled by the Java garbage collection mechanism.

 

b.Overflow and Underflow issues:

overflow can be solved by using resizing array.

Unflow throws an exception when the stack is empty and subjected to the pop method.

The implementation of stack:

data structure

Advantage

shortcoming

array
(sequential storage)

Any element can be accessed directly by indexing
Less waste space.

You need to know the number of elements when initializing
Every operation takes constant amortized time.

linked list
(Chain Storage)

The space used is proportional to the number of elements
Every operation takes constant time in the worst case.
It is more convenient to insert elements into or delete elements from a list.

Any element needs to be accessed by reference
Uses extra time and space to deal with the links.
Link list programming can be more troublesome in debugging

Array implementation

  1: import java.util.Iterator;

  2: public class ResizingArrayStack<Item> implements Iterable<Item>{

  3: 	private Item[] a = (Item[])new Object[1];

  4: 	private int N = 0;

  5: 	private void resize(int max)

  6: 	{

  7: 		Item[] temp = (Item[])new Object[max];

  8: 		for (int i = 0; i < N; i++)

  9: 			temp[i] = a[i];

 10: 		a = temp;

 11: 	}

 12: 	

 13: 	//implementations of API

 14: 	public boolean isEmpty()

 15: 	{	return N == 0;	}

 16: 	public int size()

 17: 	{	return N;		}

 18: 	public Item pop()

 19: 	{

 20: 		Item temp = a[--N];

 21: 		a[N] = null;

 22: 		if (N > 0 && N == a.length/4) resize(a.length/2);

 23: 		return temp;

 24: 	}

 25: 	public void push(Item item)

 26: 	{

 27: 		if (N == a.length) resize (2*a.length);

 28: 		a[N++] = item;

 29: 	}

 30: 	

 31: 	//implementation of Iterator

 32: 	public Iterator<Item> iterator()

 33: 	{	return new ReverseArrayIterator();	}

 34: 	private class ReverseArrayIterator implements Iterator<Item>

 35: 	{

 36: 		private int i = N;

 37: 		public boolean hasNext()	{	return i > 0;	}

 38: 		public    Item next()		{	return a[i--];	}

 39: 		public    void remove()		{					}

 40: 	}

 41: 	

 42: 	//client code

 43: 	public static void main(String[] args)

 44: 	{

 45: 		ResizingArrayStack<String> s = new ResizingArrayStack<String>();

 46: 		while (!StdIn.isEmpty())

 47: 		{

 48: 			String item = StdIn.readString();

 49: 			if (!item.equals("-"))

 50: 				s.push(item);

 51: 			else if (!s.isEmpty())	StdOut.print(s.pop() + ' ');

 52: 		}

 53: 		StdOut.println("(" + s.size() + " left on stack)");

 54: 	}

 55: }

 56:

Link List Implementation

  1: 

  2: public class Stack<Item> 

  3: {

  4: 	private Node first;

  5: 	private int N;

  6: 	

  7: 	private class Node

  8: 	{

  9: 		Item item;

 10: 		Node next;

 11: 	}

 12: 	

 13: 	//implementations of Stack's API with Linked-list

 14: 	public boolean isEmpty() 	{	return first == null;	}

 15: 	public     int size()		{	return N;				}

 16: 	

 17: 	public void push(Item item)

 18: 	{

 19: 		Node oldfirst = first;

 20: 		first = new Node();

 21: 		first.item = item;

 22: 		first.next = oldfirst;

 23: 		N++;

 24: 	}

 25: 	public Item pop()

 26: 	{

 27: 		Item item = first.item;

 28: 		first = first.next;

 29: 		N--;

 30: 		return item;

 31: 	}

 32: 	

 33: 	//client

 34: 	public static void main(String[] args)

 35: 	{

 36: 		Stack<String> s = new Stack<String>();

 37: 		

 38: 		while(!StdIn.isEmpty())

 39: 		{

 40: 			String item = StdIn.readString();

 41: 			if (!item.equals("-"))

 42: 				s.push(item);

 43: 			else if (!s.isEmpty())

 44: 				StdOut.print(s.pop() + "");

 45: 		}

 46: 		StdOut.println("(" + s.size() + " left on stack)");

 47: 	}

 48: 

 49: }

Linked list - An appropriate choice for representing data in an abstract data type implementation of a collection class. It is a recursive data structure, either empty or referring to a Node. Node is an abstract entity that may contain any type of data. A linked list represents a series of elements.

How to Realize Link List

First, a nested class is used to define the abstract data type of the node. A Node object contains two instance variables, Item and Node. Item is a placeholder indicating any data type we want to process with a linked list. The instance variables of type Node show the chain nature of this data structure. At the same time, Noe as a private nested class, only the class containing it can directly access its instance variables, so it is not necessary to declare its instance variables as Public or private.

  1: private class Node

  2: {

  3:     Item item;

  4:     Node nexxt;

  5: }
The use of linked list achieves our optimum design goal:
  1. - It can handle any data type (item);
  2. - The required space is always proportional to the size of the set; (A stack with N items uses ~40N bytes)
  3. - The time required to operate is always independent of the size of the collection.

 

2. Queues

Queues are the natural model of many everyday phenomena and the core of numerous applications. The main reason for using queues in applications is to save elements in a set while preserving their relative order: to make them in the same order as they are in the same order.

Array implementation

  1: import java.util.Iterator;

  2: public class ResizingArrayQueue<Item> implements Iterable<Item>	 {

  3: 	

  4: 	private Item[] a = (Item[])new Object[1];

  5: 	private int N = 0;

  6: 	private int head = 0;       //needs two variables to index

  7: 	private int tail = a.length;

  8: 	private void resize(int max)

  9: 	{

 10: 		Item[] temp = (Item[])new Object[max];

 11: 		for (int i = 0; i < N; i++)

 12: 			temp[i] = a[i];

 13: 		a = temp;

 14: 	}

 15: 	

 16: 	//implementations of API

 17: 	public void enqueue(Item item)

 18: 	{

 19: 		if (N == a.length) resize(2*a.length);

 20: 		a[N++] = item;

 21: 		tail++;

 22: 	}

 23: 	public Item dequeue()

 24: 	{

 25: 		Item temp = a[head];

 26: 		if (N > 0 && N == a.length) resize(a.length/4);

 27: 		a[head] = null;

 28: 		head++;

 29: 		return temp;

 30: 	}

 31: 	public boolean isEmpty()

 32: 	{	return N > 0;	}

 33: 	public int size()

 34: 	{	return N;		}

 35: 	

 36: 	//implementations of Iterator

 37: 	public Iterator<Item> iterator()

 38: 	{	return new ForwardArrayIterator();	}

 39: 	private class ForwardArrayIterator implements Iterator<Item>

 40: 	{	//FIFO iteration

 41: 		private int i = head;

 42: 		public boolean hasNext()	{	return i > tail;	}

 43: 		public    Item next()		{	return a[head++];	}

 44: 		public    void remove()		{						}

 45: 	}

 46: 	

 47: 	//client

 48: 	public static void main(String[] args){

 49: 		

 50: 		ResizingArrayQueue<String> q = new ResizingArrayQueue<String>();

 51: 		

 52: 		while(!StdIn.isEmpty())

 53: 		{

 54: 			String item = StdIn.readString();

 55: 		if (!item.equals("-"))

 56: 			q.enqueue(item);

 57: 		else if (!q.isEmpty()) StdOut.print(q.dequeue() + "");

 58: 		}

 59: 		

 60: 		StdOut.println("(" + q.size() + " left on queue)");

 61: 	}

 62: }

 63:

Link List Implementation

  1: public class Queue<Item> {

  2: 	private Node first;

  3: 	private Node last;

  4: 	private int N;

  5: 	

  6: 	private class Node{

  7: 		Item item;

  8: 		Node next;

  9: 	}

 10: 	

 11: 	//implementations of Queue's API with Linked-list

 12: 	public boolean isEmpty()	{	return N == 0;	}

 13: 	public int size()			{	return N;		}

 14: 	

 15: 	public void enqueue(Item item){

 16: 		Node oldlast = last;

 17: 		last = new Node();

 18: 		last.item = item;

 19: 		last.next = null;

 20: 		if (isEmpty())	first = last;

 21: 		else 			oldlast.next = last;

 22: 		N++;

 23: 	}

 24: 	

 25: 	public Item dequeue(){

 26: 		Item item = first.item;

 27: 		first = first.next;

 28: 		if (isEmpty())	last = null;

 29: 		N--;

 30: 		return item;

 31: 	}

 32: 	

 33: 	//client

 34: 	public static void main(String[] args){

 35: 		

 36: 		Queue<String> q = new Queue<String>();

 37: 		

 38: 		while(!StdIn.isEmpty())

 39: 		{

 40: 			String item = StdIn.readString();

 41: 		if (!item.equals("-"))

 42: 			q.enqueue(item);

 43: 		else if (!q.isEmpty()) StdOut.print(q.dequeue() + "");

 44: 		}

 45: 		

 46: 		StdOut.println("(" + q.size() + " left on queue)");

 47: 	}

 48: }

 

 

 

 

3. Backpack

Knapsack is a collection data type that does not support deleting elements from it

Link List Implementation

  1: import java.util.Iterator;

  2: public class Bag<Item>  implements Iterable<Item>{

  3: 	private Node first;

  4: 	private int N;

  5: 	

  6: 	private class Node{

  7: 		Item item;

  8: 		Node next;

  9: 	}

 10: 	

 11: 	//implementations of Bag's API with Linked-list

 12: 	public boolean isEmpty()	{	return first == null;	}

 13: 	public int size()			{	return N;				}

 14: 	

 15: 	public void add(Item item){

 16: 		Node oldfirst = first;

 17: 		first = new Node();

 18: 		first.item = item;

 19: 		first.next = oldfirst;

 20: 		N++;

 21: 	}

 22: 	

 23: 	//implementations of Iteration

 24: 	public Iterator<Item> iterator(){

 25: 		return new ReverseArrayBag();

 26: 	}

 27: 	public class ReverseArrayBag implements Iterator<Item>{

 28: 		private Node current = first;

 29: 		public boolean hasNext()	{	return current == null;	}

 30: 		public Item next(){

 31: 			Item item = current.item;

 32: 			current = current.next;

 33: 			return item;

 34: 		}

 35: 		public void remove()		{							}

 36: 	}

 37: }

 

Finally, note that Java itself provides some built-in libraries that implement data types such as Stack. However, because the API of java.util.Stack is wide interface, we can not guarantee high efficiency in operation, so we try to avoid using it. Don't use a library until you understand its API!

Reprinted at: https://www.cnblogs.com/viinye/archive/2012/12/22/2829160.html

Keywords: Java less Programming

Added by delhiris on Wed, 10 Jul 2019 22:01:17 +0300

Popular Keywords

©2024 Programming VIP