A stack is a dynamic data structure that can store records of data and that supports two primary functions usually called PUSH and POP. The operation PUSH is used to add elements to the stack, while the operation POP removes a prespecified element off the stack. A key property of a stack is that it implements a last in, first out (LIFO) policy; namely the last element pushed onto the stack must be the first element popped off the stack. One should compare this policy to that of another data structure, the queue, which implements a first in, first out (FIFO) policy.
An important way to visualize the operation of a stack is to think of it literally as a stack of cafeteria trays, with each tray corresponding to a record of data. The PUSH operation corresponds to pushing a tray, or new piece of data onto the top of the stack, while the POP operation corresponds to removing, or popping, the top tray off the stack. In this visual analogy, it is clear that the last tray pushed onto the stack is the first tray popped off and hence the LIFO policy is obeyed.
In actuality, in a computer a stack of at most n elements can be implemented simply by an n element array called STACK[0..n-1]. The top of the stack corresponds to the last nonempty spot in the array, whose index could be remembered by an auxiliary variable called TOP. Pushing an element on the stack simply involves placing that element in the array location STACK[TOP+1], and then incrementing TOP by 1, first checking of course that TOP does not exceed n-1. Popping an element off the stack similarly involves returning the data in STACK[TOP] and decrementing TOP. If TOP equals 0 then the stack is empty and the POP function should return some sort of error. If one does not know the maximum number of elements to be held by the stack in advance one could alternatively implement the stack using a linked list with PUSH and POP corresponding to appending and deleting the last element in the list.
In terms of their applications, stacks as data structures are ubiquitious in all modern computing tools. For example consider some of the early calculators which use postfix notation. In such a notation one would type in the number 4, then the number 5, and then some operation, say +, and the calculator would read out 9. In the hardware what is happening is that each time the user enters a number, it is pushed onto the top of the stack. Whenever a binary operation, such as +, -, *, or / is entered, the first two elements at the top of the stack are popped off and taken as input to the binary function, whose output is printed on the screen. This elegant implementation of a calculator obviates the need for using parentheses to specify the associativity structure of a calculation. Instead, the act of pushing and popping takes care of everything, albeit forcing the user to think in postfix.
As another elegant example of the use of a stack, consider the implementation of a parenthesis checker, a program that takes as input a mathematical statement and checks whether all the parentheses match up. Such a subroutine would be useful in a compiler for example. The checker could be implemented simply using a stack. First it starts off with an empty stack. Every time it encounters an open parenthesis "(" it pushes some symbol onto the stack. Also every time it encounters a closed parenthesis is pops the same symbol off the stack. If at any point the checker has to POP a symbol off an empty stack, the parentheses cannot be well matched. Assuming such an error does not occur, if the stack is empty after the the last symbol is read, it is guaranteed that the parentheses match up correctly. From these simple examples once can see the utility of stacks, which explains their presence in almost all hardware implementations of modern computing tools.
This is the complete article, containing 675 words
(approx. 2 pages at 300 words per page).
