Stacks
Table of Contents
1. The Idea of A Stack
1.1) What is a Stack?
1.2) The Stack Implemented as an Array
1.3) The Stack Implemented With Pointers
2. Operations on Stacks
2.1) Push
2.2) Pop
2.3) Top
2.4) Is_Empty, Is_Full
2.5) Size
2.6) Pictorial Overview
3. The Stack Applet
4. Related Links 1.1. What is a Stack?
DEFINITION: A stack is a homogeneous collection of items of any one type, arranged linearly with access at one end only, called the top. This means that data can be added or removed from only the top. Formally this type of stack is called a Last In, First Out (LIFO) stack. Data is added to the stack using the Push operation, and removed using the Pop operation. These will be covered in sections 2.1 and 2.2 respectively.
DESCRIPTION: In order to clarify the idea of a stack let's look at a "real life" example of a stack. Think of a stack of plates in a high school cafeteria. When the plates are being stacked, they are added one on top of each other. It doesn't make much sense to put each plate on the bottom of the pile, as that would be far more work, and would accomplish nothing over stacking them on top of each other. Similarily when a plate is taken, it is usually taken from the top of the stack.
1.2 The Stack Implemented as an Array
One of two ways to implement a stack is by using a one dimensional array (also known as a vector). When implemented this way, the data is simply stored in the array. Top is an integer value, which contains the array index for the top of the stack. Each time data is added or removed, top is incremented or decremented accordingly, to keep track of the current top of the stack. By convention, an empty stack is indicated by setting top to be equal to -1.
Stacks implemented as arrays are useful if a fixed amount of data is to be used. However, if the amount of data is not a fixed size or the amount of the data fluctuates widely during the stack's life time, then an array is a poor choice for implementing a stack. For example, consider a call stack for a recursive procedure. First, it can be difficult to know how many times a recursive procedure will be called, making it difficult to decide upon array bounds. Second, it is possible for the recursive procedure to sometimes be called a small number of times, called a large number of times at other times. An array would be a poor choice, as you would have to declare it to be large enough that there is no danger of it running out of storage space when the procedure recurses many times. This can waste a significant amount of memory if the procedure normally only recurses a few times. A much more elegant solution to this problem will be covered in the next section.
1.3 The Stack Implemented with Pointers
To solve the problems discussed in the last section, a stack can be implemented using pointers, as a form of a linked list. When a stack is implemented this way, each node contains a data field for the information, and a pointer to the next node on the list. Top is a pointer to the top of the list. When top is NULL (or NIL, depending on the programming language), the stack is empty.
Implementing stacks as linked lists provides a solution to the problem of dynamically growing stacks, as a linked list is a dynamic data structure. The stack can grow or shrink as the program demands it to. However, if a small and/or fixed amount of data is being dealt with, it is often simpler to implement the stack as an array.
2.0 Operations on a Stack
Now that you know what a stack is we will now discuss some operation that can be performed on a stack. Remember, a stack has a maximum size of n.
Operation Description Requirement Push This operation adds or pushes another item onto the stack. The number of items on the stack is less than n. Pop: This operation removes an item from the stack. The number of items on the stack must be greater than 0. Top: This operation returns the value of the item at the top of the stack. Note: It does not remove that item. Is Empty: This operation returns true if the stack is empty and false if it is not. Is Full: This operation returns true if the stack is full and false if it is not.
These are the basic operations that can be performed on a stack. Let us now go on and look at them in detail.
2.1 Push
Push is the functionused to add data items to the stack.
In order to understand how the Push function operates, we need to look at the algorithm in more detail.
procedure Push(item : items);
{add item to the global stack stack; top is the current top of stack and n is its maximum size}
begin
if top = n then stackfull;
top := top+1;
stack(top) := item;
end: {of Push}
In order to understand the algorithm, let's break it apart line by line.
procedure Push(item : items);
First, Push accepts a parameter - item. This parameter is of the same type as the rest of the stack. Item is the data to be added to the stack.
if top = n then stackfull;
This line performs a check to see whether or not the stack is full. If it is, then some error condition, such as an error handling routine, is triggered. If it is not, the procedure continues.
If the stack is implemented as linked list, you simply can not compare top to n to see if the stack is full. Top is a pointer, and will not be equal n when the stack is full. The easiest solution to this problem is to keep a counter, and increment or decrement it accordingly each time you push or pop. This counter will contain the number of items on the stack, and can be used for condition testing.
top := top+1;
If the stack is not full, top is increased by a value equal to the size of another item. This allocates room for the insertion.
If implementing the stack as a linked list, allocation must be handled differently. Allocation of space for the item to be inserted is dependent on the language you are using. What you need to do is create/declare/initialize a new pointer, which can be used to reference the new node. This node must then be linked to the stack, by referencing it from the previous node.
stack(top) := item;
After the room for another item has been added, the data is then inserted. This is done by setting the new value of top to be equal to the item to be inserted.
2.2 Pop
Data is removed from a stack by using Pop. From a procedural perspective, pop is called with the line Pop(item), where item is the variable to store the popped item in. Pop returns the item at the top of the stack (and only that item).
Once again, we will begin by looking at the algorithm.
procedure Pop(var item : items);
{remove top element from the stack and put it in the item}
begin
if top = -1 then stackempty;
item := stack(top);
top := top-1;
end; {of Pop}
procedure Pop(var item : items);
Pop is called with the parameter item. This variable is where the item popped off the top of the stack is stored for later access.
if top = -1 then stackempty;
If top is equal to -1, the stack is empty - there is no item to pop off the stack. Control can then be passed to an error handling routine.
If the stack is implemented as a linked list, the stack will be empty if top = NULL/NIL.
item := stack(top);
Set item to be equal to the data in the top node.
top := top-1;
This statement removes the top item from the stack. Decrement top by 1 so that it now accesses the new top of the stack.
If implementing the stack as a linked list, this step is done by setting top to point to the next item on the stack, which will become the current top.
In addition, if implementing the stack as a linked list, it is necessary to add a statement that will decrement the count variable that keeps track of the number of items on the stack.
2.3 Top
What if you want to access the data field at the top of the stack, but you do not want to remove the item? It seems like a hassle (not to mention that it is inefficient) to pop the top item, use it, and push it back onto the stack. The solution to this problem is the function Top (do not confuse this function with the variable top). Top will return the data segment of the top item without removing it from the stack. It is called with Top(item), where item is a variable that will hold the data item.
As usual, we will start by looking at the algorithm.
procedure Top(var item : items);
{return top element from the stack stack and put it in the item}
begin
if top = -1 then stackempty;
item := stack(top);
end; {of Top}
Once again, we will look at the code line by line. If you are familiar with the Pop algorithm, you may wish to skip the remainder of this section, as Top is the same as Pop, without the statement that sets top to reference the next item. There is also no need to touch the item counter variable, as no items are being added or removed from the stack.
procedure Pop(var item : items);
Pop is called with the parameter item, which is the variable in which the popped item is to be stored.
if top = -1 then stackempty;
If top is equal to -1, the stack is empty. Control can then be passed to an error handling routine.
If the stack is implemented as a linked list, the stack will be empty if top = NULL/NIL.
item := stack(top);
Set item to be equal to the data in the top node.
2.4 Is_Empty and Is_Full
2.4.1 Is_Empty
Is_Empty is a function that will tell you if the stack is empty. Is_Empty is implemented as follows:
If the stack is implemented as an array,
if top = -1 => Stack is Empty;
If the stack is implemented as a linked list,
if top = NULL/NIL => Stack is empty;
In both cases, is empty will return a value (normally a boolean value) that will tell you if the stack is empty or not.
2.4.2 Is_Full
Is_Full is a function that will tell you if a stack is full. First, there must be number n defined, which is the maximum number of elements allowed in the stack. For array implementation's, it is simpler if n is defined as (Maximum size - 1), due to the fact that the array indexing starts at -1 for an empty stack. Is_Full is implemented as follows:
If the stack is implemented as an array:
if top = n then stack is full;
If the stack is implemented as a linked list:
The easiest way to do this is to keep a counter that contains the number of items in the stack. This concept was covered in section 2.1. With this solution, checking to see if the stack is full is accomplished with the statement:
if counter = n then stack is full;
2.5 Size
Checking the size of the stack is a fairly simple task. If you are implementing the stack as an array, the size of the stack will be
(top + 1)
The 1 is added because top is initially -1, when the stack is empty, or size equals 0.
If you are implementing the stack as a linked list, you must keep a counter that will keep track of the number of items in the stack. This counter is initially set to zero, when the stack is empty. Each time an item is added, the counter is incremented, and each time an item is popped, the counter is decremented. At any given time, the size of the stack will be the value of this counter.
2.6 Pictorial Overview
The following is a detailed example of the procedures we have discussed on an array implementation of a stack.