Stacks and Queues
ADT |
Mathematical Model |
Operations |
|||||||||||
Stack |
|
Push(S,Data) Pop(S) Makenull(S) Empty(S) Top(S) |
|||||||||||
|
ADT |
Mathematical Model |
Operations |
|||||||||||
Queue |
|
Enqueue(Q) |
|||||||||||
The standard operation on a queue are as follows:
|
Applications1. Polynomial ADT:A polynomial can be represented with primitive data structures. For example, a polynomial represented as akxk ak-1xk-1 + ... + a0 can be represented as a linked list. Each node is a structure with two values: ai and i. Thus, the length of the list will be k. The first node will have (ak, k), the second node will have (ak-1, k-1) etc. The last node will be (a0, 0). The polynomial 3x9 + 7x3 + 5 can be represented in a list as follows: (3,9) --> (7,3) --> (5,0) where each pair of integers represent a node, and the arrow represents a link to its neighbouring node. Derivatives of polynomials can be easily computed by proceeding node by node. In our previous example the list after computing the derivative would represented as follows: (27,8) --> (21,2). The specific polynomial ADT will define various operations, such as multiplication, addition, subtraction, derivative, integration etc. A polynomial ADT can be useful for symbolic computation as well. 2. Large Integer ADT:Large integers can also be implemented with primitive data structures.
To conform to our previous example, consider a large integer represented
as a linked list. If we represent the integer as successive powers of 10,
where the power of 10 increments by 3 and the coefficent is a three digit
number, we can make computations on such numbers easier. For example, we
can represent a very large number as follows: 3. Window Manager ADT:A window interface can be represented by lists. Consider an environment
with many windows. The fist node in the list could represent the current
active window. Subsequent windows are further along the list. In other
words, the nth window corresponds to the nth node
in the list.
4. Management of free space:When memory is requested, a list of available blocks of memory might
be useful. Again, a list could represent blocks in memory available to
the user, with nodes containing pointers to these available blocks. The
list can be used like a stack (LIFO). The last freed memory becomes the
next available to the user. Such lists are called 'free space lists' or
'available space lists'. Since addition and deletion of nodes is at one
end, these lists behave like stacks. All operations on free space lists
can be done in O(1) time.
Stacks1. Stack based languages:Expressions can be evaluated using a stack. Given an expression in a
high-level language (for example, (a + b) * c) the compiler will transform
this expression to postfix form. The postfix form of the above example
is ab + c *, where a and b are operands, + and * are operators, and the
expression is scanned left to right. The expression is pushed on the stack
and evaluated as it is popped. The following algorithm illustrates the
process: 2. Text Editor:A text editor can be implemented with a stack. Characters are pushed on a stack as the user enters text. Commands to delete one character or a command to delete a series of characters (for example, a sentence or a word) would also push a character on a stack. However, the character would be a unique identifier to know how many characters to delete. For example, an identifier to delete one character would pop the stack once. An identifier to delete a sentence would pop all characters until the stack is empty or a period is encountered. 3. Postscript:Postscript is a full-fledged interpreted computer language in which
all operations are done by accessing a stack. It is the language of choice
for laser printers. For example, the Postscript section of code 4. Scratch pad:Stacks are used to write down instructions that you can not act on immediately. For example, future work to be done by the program, information that may be useful later, and so forth (just as with a scratch pad). An example of this is the rat-in-maze problem (see below). A stack can be used to solve the problem of traversing a maze. One must keep track of previously explored routes, or else an infinite loop could occur. For example, with no previous knowledge of exploring a specific route unsuccessfully, one can enter a path, find no solution to the maze, exit the path through the same route as entrance, then enter the same unsuccessful path all over again. This problem can be solved with the help of a stack. 5. Recursion:Stacks are used in recursions. Every recursive program can be rewritten
iteratively using a stack. One related problem is the knapsack problem: else return knapsack(target, candidate + 1) A knapsack of size 26 can be filled with items of size 15 and 11.
... JAVA APPLET
This applet demonstrates an excellent application of the Stack ADT. In order to find its way out of the maze, the algorithm pushes its moves onto a stack until it either reaches the end, or becomes blocked. If it becomes blocked, the algorithm will backtrack its moves by popping them from the stack until it reaches a square with at least one free neighbor. It will then follow this new path until it again becomes blocked or it finishes. This process is repeated until the end of the maze is reached. To see this algorithm in action, press the "Next ->" button and watch the green line advance one move. Press "<- Back" to go back one iteration. When the green line has to backtrack, it leaves behind a grey line to indicate the squares it has already visited. ReferencesFor More Information on Data Structures, consider these books: This Web Page was Created by:The text is based on class notes taken by Daniel Taranovsky. Web Page text was authored by Damian Orfamoudakis and Daniel Taranovsky. Daniel Levin created the Java applet and accompanying text. Graphics designed and drawn by Danny Wong.
|