08-STACKSQUEUES.pdf

Basic Stack Operations:  Push – adds an item at the top of the stack. After the push, the new item becomes the top. To perform a push, ensure that there is room for the new item. If there is not enough room, then the stack is in an overflow state and the item cannot be added.  Pop – removes...

Basic Stack Operations:  Push – adds an item at the top of the stack. After the push, the new item becomes the top. To perform a push, ensure that there is room for the new item. If there is not enough room, then the stack is in an overflow state and the item cannot be added.  Pop – removes the item at the top of the stack and return it to the user. Because the top item has been removed, the next older item in the stack becomes the top. When the last item in the stack is deleted, it must be set to its empty state. If pop is called when the stack is empty, then it is in an underflow state.  Stack top – copies the item at the top of the stack; that is, it returns the data in the top element to the user but does not delete it. You might think this operation as reading the stack top. Data To implement the linked-list stack, we need two different structures, a head and a Structure data node. The head structure contains metadata and a pointer to the top of the stack. The data structure contains data and a link pointer to the next node in the stack. Stack Head Generally the head for a stack requires only two attributes: a top pointer and a count of the number of elements in the stack. These two elements are placed in a structure. Stack Data The rest of the data structure is a typical linked list data node. While the Node application determines the data that are stored in the stack, the stack data node looks like any linked list node. In addition to the data, it contains a link pointer to other data nodes, making it a self-referential data structure. Stack We define eight operations for a stack, which should be sufficient to solve any algorithms basic stack problem. If an application requires additional stack operations, they can be easily added. For each operation we give its name, a brief description, and it’s calling sequence. 1. Create Stack 5. Empty Stack - allocates memory for the stack head node, initializes it, and then returns a pointer - provided to implement the structured programming concept of data to the stack node. hiding. Algorithm createStack algorithm emptyStack (val stack ) Allocates memory for a stack head node from dynamic memory and returns its Determines if stack is empty and return a Boolean address to the caller. Pre stack is a pointer to the stack head structure Pre Nothing Post returns stack status Post Head node or allocated or error returned Return Boolean, true; stack empty, false: stack contains data Return pointer to head node or null pointer if no memory 2. Push stack 6. Full Stack - inserts an element into the stack. - a structured programming implementation of data hiding. algorithm pushStack (val stack , val inData ) algorithm fullStack (val stack ) Insert (push) one item into the stack. Determines if stack is full and return a Boolean. Pre stack is a pointer to the stack head structure Pre stack is a pointer to the stack head structure Data contains data to be pushed into stack Post returns stack status Post data have been pushed in the stack Return Boolean, ture: stack full, false: memory available Return returns true if successful; false if memory overflow 3. Pop Stack – returns the data in the node at the top of the stack to the calling 7. Stack Count algorithm. It then deletes and recycles the node, that is returns it to memory. - returns the number of elements currently in the stack. Another algorithm popStack (val stack , ref dataOut ) implementation of data hiding in structured prog. This algorithm pops the item on the top of the stack and returns it to the user algorithm stackCount (val stack ) Pre stack is a pointer to the stack head structure Returns the number of elements currently in stack. dataOut is a reference variable to receive the data Pre stack is a pointer to the stack head structure Post Data have been returned to calling algorithm Post returns stack count Return true if successful; false if underflow Return integer count of number of elements in stack 4. Stack top 8. Destroy Stack - returns the data at the top of the stack without deleting the top node. - deletes all data in a stack and returns a null pointer. algorithm stackTop (val stack , ref dataOut ) algorithm destroyStack (val stack ) This algorithm retrieves the data from the top of the stack without changing the This algorithm released all nodes to dynamic memory. stack. Pre stack is a pointer to the stack head structure Pre stack is a pointer to the stack head structure Post stack is empty and all nodes recycled Post data have been returned to calling algorithm Return null stack pointer Return true if data returned; false if underflow Four Common Stack Applications: 1. Reversing Data - requires that a given set of data be ordered so that the first and last elements are exchanged, with all of the positions between the first and last being relatively exchanged also. For example {1 2 3 4} becomes {4 3 2 1}. There are two reversing applications: (1) reverse list and (2) convert decimal to binary. Reverse a Number Series program reverseNumber stack = createStack prompt (enter a number) read (number) //Fill Stack Loop (not end of data AND stack not full) pushStack (number) prompt (enter next number : to stop) read (number) //Now print numbers in reverse Loop (not emptyStack (stack)) popStack (stack, dataOut) print (dataOut) stack = destroyStack (stack) end reverseNumber Convert Decimal to binary program decimalToBinary stack = createStack prompt (enter a decimal to convert to binary) read (number) loop (number > 0) digit = number modulo 2 pushOK = push (stack, digit) if (pushOK false) print (Stack overflow creating digit) quit algorithm number = number / 2 //Binary number created in stack. Now print it. loop (not emptyStack (stack)) popStack (stack, digit) print (digit) //Binary number created. Destroy stack and return Destroy (stack) end decimalToBinary 2. Parsing - any logic that breaks data into independent pieces for further processing. For example, translate a source program to machine language, a compiler must parse the program into individual parts such as keywords, names, and tokens.  Ex2. checking if parenthesis is unmatched in an algebraic expression. Parse Parenthesis program parseParens loop (more data) read (character) If (character is an opening parenthesis) pushStack (stack, character) else if (character is closing parenthesis) if (emptyStack (stack)) print (Error: closing parenthesis not matched) else popstack (stack, token) if (not emptyStack (stack)) print (Error: opening parenthesis not matched) end parseParens Unmatched parentheses example ( ( A + B) / C (a) opening parenthesis not matched (A+B)/C) (b) closing parentheses not matched Ex. Given the following infix notation: A + B * C Step1: results in the following expression. (A + (B * C ) ) Step2: moves the multiply operator after C (A+(BC*)) And then moves the addition operator to between the last two closing parenthesis resulting to: ( A ( B C * ) + ) Step3: removes the parentheses. 3. Postponement - when using a stack to reverse a list, the entire list was read before we began outputting the results. A stack can be useful when the application requires that data’s use be postponed for awhile. There are two stack postponement applications which includes infix to postfix transformation and postfix expression. Prefix: + a b (the operator comes before the operands) Infix: a + b (the operator comes between the operands) Postfix: a b + (the operator comes after the operands) // process of converting infix to postfix expressions a. Fully parenthesize the expression using any explicitparenthesis and the arithmetic precedence, multiply and divide before add and subtract. b. Change all infix notations in each parenthesis to postfix notation starting from the innermost expressions. This is done by moving the operator to the location of the expression’s closing parenthesis. c. Remove all parentheses. //Evaluation of postfix expressions stack = createStack index = 1 loop (index rear = null pointer pWalker = pWalker->next newPtr->count = 0 recycle (deletePtr) return newPtr recycle (queue) else return null pointer return null pointer end destroyQueue end createQueue algorithm enqueue (val queue , val item algorithm dequeue (val queue , ) ref item ) This algorithm inserts data into a queue. This algorithm deleted a node from a queue. Pre queue has been created Pre queue has been created Post item data have been inserted Post data at front of queue returned to user return boolean, true if successful, false if overflow. through item and front element deleted and recycled if (queue full) Return Boolean true if successful, false if underflow. return false if (queue->count is 0 ) allocate (newPtr) return false newPtr ->data = item item = queue ->front->data newPtr->next = null pointer deleteLoc = queue->front if (queue->count zero) if (queue->count 1) Inserting into null queue Deleting only item in queue queue->front = newPtr queue ->rear = null pointer else queue->front = queue->front->next Insert data and adjust metadata queue->count = queue->count – 1 queue->rear->next = newPtr recycle (deleteLoc) queue->rear = newPtr return true queue->count = queue->count + 1 end dequeue return true end enqueue algorithm queueFront (val queue , algorithm emptyQueue (val queue ) Ref item ) This algorithm checks to see if a queue is empty This algorithm retrieves the data at the front of the queue without Pre queue is a pointer to a queue head node changing the queue contents. Return boolen true if empty, false if queue has data Pre queue is a pointer to an initialized queue. Post data passed back to caller return (queue->count equal 0) Return Boolean true if successful, false if underflow end emptyQueue if (queue -> count is 0 ) return false item = queue->front->data return true end queueFront algorithm fullQueue (val queue ) algorithm queueCount count allocate (tempPtr) end queueCount if (allocated successful) release (tempPtr) return false else return true end fullQueue