February 6, 2009

Stacks & Queues


Stacks
  • A stack is one of the methods used to insert and delete items from a linear list.
  • For example, pile of plates in a canteen. After washing up the plates, the last plate will be placed on to the top of the stack.
  • The next plate to be used will be taken from the top of the stack (i.e. LIFO stack)
  • We refer to the ‘top of the stack’ or the ‘buttom of the stack’, thus the number will be set out vertically, to reinforce this point visually.
  • We also have the phrase ‘pushed on the top of the stack’ to indicate that an item of data has been added to the stack.
  • Moreover, we have the phrase ‘popped off the stack’ to indicate that the ‘last number in’ is always the ‘first number out’ The system of storing this list of numbers is called LIFO stack (Last In First Out)
A Pointer System
  • In practice a stack would be built up in the computer’s memory using a pointer system.
  • This is a number used to pint to an item of interest, so it may be used to point to the memory location inside the computer that indicates the top of the stack. (called Stack Pointer)
Definitions
  1. Stack _pointer variable is used to indicate the current top of the stack.
  2. Maximum is used to determine when the stack is full.
  3. Minimum is used to determine if the stack is empty.
  4. Data is item in data to be pushed or popped.
  5. STACK generally is named for the stack contained in memory.
Pseudocode to POP a new item of data on to the top of the STACK

Note: here the stack cannot overflow from this operation. However, there might be no items of data on the stack, in which case cannot remove any more data.

POP (Stack_pointer, Maximum, Data) Calling the procedure

The actual Pseudocode for the POP procedure is as follows.....

PROCEDURE POP (Stack_pointer, Maximum, Data)
(*Check if the stack is already empty*)
IF (Stack_pointer=Minimum THEN)
PRINT the stack is already empt
EXIT PROCEDURE
ELSE
(*Pop data off of stack and adjust pointer*)
SET Data= STACK (Stack_pointer)
SET Stack_pointer= Stack_pointer - 1
END IF
END PROCEDURE

Queues
A queue is very similar in principle to the operation of a stack, a queue is often called a FIFO stack (First In First Out). E.g. normal queue, waiting to be served in a shop, where the first person in the queue is expected to get served first and thus will be first person out.

Note: in this operation the data does not move, it is just the pointers that have been altered. We have thstart pointer (indicating to the head of the queue) and stop pointer (indicating to the end of the queue).

1.Start _pointer refers to variable used to indicate the start of the queue.
2.Stop_pointer refers to variables used to indicate the end of the queue.
3.Size refers to variables that represents the size of the queue.
4.Data refers to item in data to be pushed or popped.
5.QUEUE refers to general name for the queue contained in memory.
6.QUEUE(pointer) refers to subscripted variable representing the data at the current pointer position, i.e. an identifier for the data on the queue.

Summary
Q. What does a stack mean?
Ans. A stack is an area of memory set up as a temporary storage for data. A stack has a logical top and bottom, which represent the places at which the beginning and end of the data can be found.

Q. How might a stack be implemented?
Ans. Stacks are implemented by pointers which point to specific areas of memory.

Q. What is a pointer?
Ans. A pointer is simply a data element that indicates the position of some other data element (e.g. the data element that points to the top of the stack).

Q. What does the term ‘push’ mean?
Ans. Push is the term used to indicate that data has been placed on the stack.

Q. What does the term ‘pop’ mean?
Ans. Pop is the term used to indicate that data has been removed from the stack.

Q. What is LIFO stack?
Ans. A LIFO stack is a Last-In-First-Out stack.

Q. What is FIFO stack?
Ans. A FIFO is a First-In-First-Out stack.

Q. What is an Overflow?
Ans. A queue or a stack may have a maximum size. An attempt to add a new element to a queue or stack which is already full will result in an overflow error.

Q. What is an Underflow?
Ans. An attempt to remove an item from an empty queue or stack will result in an underflow.

0 comments:

Post a Comment

Will you Refer This Site to your friends

How Do You Find This Site as a STUDENT

 

B.Sc.(IT) Notes Of Mumbai University. Copyright 2008 All Rights Reserved Revolution Two Church theme