A stack allows access to only one data item: the last item inserted. If you remove this item, then you can access the next-to-last item inserted, and so on.
To insert a data item on the stack is called Push, and to remove a data item from the top of the stack is called Pop(take item from top of the stack) . Peek is sometimes useful to be able to read the value from the top of the stack without removing it.
usage: reverse the words; delimiter Matching- the delimiters are the braces '{] and '}, brackets '[' and ']', and parentheses '(' and ')'. Each opening or left delimiter should be matched by a closing or right delimiter; e.g. a{b[c]d}e
The word queue is British for line, "queue up" means to get in line. Queue is similar to a stack, except that in a queue the first item inserted is the first to be removed(FIFO), while in a stack, the last itme inserted is the first to be removed(LIFO). Methods include insert, remove,peek, isEmpty, isFull and size().
Postfix Notation: everyday arithmetic expression are written with an operator placed between two operands. this is called infix notation, because the operator is written inside the operands. In posifix notation(Which is also called Reverse Polish Notation,or RPN), the operator follows the two operands. thus
A+B-c becomes AB+C-
A*(B+C) becomes ABC+*
(A+B)*(C-D) becomes AB+CD-*
The rules of translate infix to postfix,
1.read from left to right, looking at each character in turn. As you go along, you copy these operands and operators to the postfix output String.
2. if the character in the infix string is an operand, you copy it immediately to the postfix string. you copy the operands as you get to them, no matter how long you must wait to copy their associated operators.
3. Whenever you could have used the operator to evaluate part of the infix expression, you instead copy it to the postfix string.
Implement in Java:
Item read from Input(infix):
Operand -> Write it to output(postfix)
Open parenthesis ( -> push it on stack
close parenthesis ) -> While stack not empty, repeat the following: Pop an item, if item is not (, write it to output
2. when you've read enough to evaluate two operands and an operator, you do the calculation and substitute the answer for these two operands an operator.
3 .both * and / have a high percedence than + and - unless parentheses dictate otherwise).
In a Linked list, each data item is embedded in a link, each link object contains a reference(usually called next) to the next link in the list. You can't access a data item directly and you must use relationships between the items to locate it.
Iterators: suppose you wanted to traverse a list, performing some operation on certain links. It's far more efficient to step from link to link, checking if each one meets certain criteria and performing the appropriate operation if it does.
ADT(Abstract Date Type) is a data-storage class considered without reference to its implementation. Stacks and Queues are ADTS. They can be implemented using either arrays or linked list.
To insert a data item on the stack is called Push, and to remove a data item from the top of the stack is called Pop(take item from top of the stack) . Peek is sometimes useful to be able to read the value from the top of the stack without removing it.
usage: reverse the words; delimiter Matching- the delimiters are the braces '{] and '}, brackets '[' and ']', and parentheses '(' and ')'. Each opening or left delimiter should be matched by a closing or right delimiter; e.g. a{b[c]d}e
The word queue is British for line, "queue up" means to get in line. Queue is similar to a stack, except that in a queue the first item inserted is the first to be removed(FIFO), while in a stack, the last itme inserted is the first to be removed(LIFO). Methods include insert, remove,peek, isEmpty, isFull and size().
Postfix Notation: everyday arithmetic expression are written with an operator placed between two operands. this is called infix notation, because the operator is written inside the operands. In posifix notation(Which is also called Reverse Polish Notation,or RPN), the operator follows the two operands. thus
A+B-c becomes AB+C-
A*(B+C) becomes ABC+*
(A+B)*(C-D) becomes AB+CD-*
The rules of translate infix to postfix,
1.read from left to right, looking at each character in turn. As you go along, you copy these operands and operators to the postfix output String.
2. if the character in the infix string is an operand, you copy it immediately to the postfix string. you copy the operands as you get to them, no matter how long you must wait to copy their associated operators.
3. Whenever you could have used the operator to evaluate part of the infix expression, you instead copy it to the postfix string.
Implement in Java:
Item read from Input(infix):
Operand -> Write it to output(postfix)
Open parenthesis ( -> push it on stack
close parenthesis ) -> While stack not empty, repeat the following: Pop an item, if item is not (, write it to output
2. when you've read enough to evaluate two operands and an operator, you do the calculation and substitute the answer for these two operands an operator.
3 .both * and / have a high percedence than + and - unless parentheses dictate otherwise).
In a Linked list, each data item is embedded in a link, each link object contains a reference(usually called next) to the next link in the list. You can't access a data item directly and you must use relationships between the items to locate it.
Iterators: suppose you wanted to traverse a list, performing some operation on certain links. It's far more efficient to step from link to link, checking if each one meets certain criteria and performing the appropriate operation if it does.
ADT(Abstract Date Type) is a data-storage class considered without reference to its implementation. Stacks and Queues are ADTS. They can be implemented using either arrays or linked list.
Comments
Post a Comment