Stack

What is a Stack?

A stack is a simple data structure used for storing data (similar to Linked Lists). In a stack, the order in
which the data arrives is important. A pile of plates in a cafeteria is a good example of a stack. The plates
are added to the stack as they are cleaned and they are placed on the top. When a plate, is required it is
taken from the top of the stack. The first plate placed on the stack is the last one to be used.

Definition: A stack is an ordered list in which insertion and deletion are done at one end, called top. The
last element inserted is the first one to be deleted. Hence, it is called the Last in First out (LIFO) or First
in Last out (FILO) list.

Special names are given to the two changes that can be made to a stack. When an element is inserted in
a stack, the concept is called push, and when an element is removed from the stack, the concept is
called pop. Trying to pop out an empty stack is called underflow and trying to push an element in a full
stack is called overflow. Generally, we treat them as exceptions. As an example, consider the snapshots
of the stack.

A stack is a container of objects that are inserted and removed according to the last in first-out (LIFO)
principle. Objects can be inserted into a stack at any time, but only the most-recently inserted (that is,
“last”) object can be removed at any time. The name “stack” is derived from the metaphor of a stack of
plates in a spring-loaded cafeteria plate dispenser. In this case, the fundamental operations involve the
“pushing” and “popping” of plates on the stack.
Example: Internet web browsers store the addresses of recently visited sites on a stack. Each time a user
visits a new site, that site’s address is “pushed” onto the stack of addresses. The browser then allows
the user to “pop” back to previously visited sites using the “back” button.

How Stacks are used

Consider a working day in the office. Let us assume a developer is working on a long-term project. The
manager then gives the developer a new task which is more important. The developer puts the long
term project aside and begins work on the new task. The phone rings, and this is the highest priority as it
must be answered immediately. The developer pushes the present task into the pending tray and
answers the phone.

When the call is complete the task that was abandoned to answer the phone is retrieved from the
pending tray and work progresses. To take another call, it may have to be handled in the same manner,
but eventually the new task will be finished, and the developer can draw the long-term project from the
pending tray and continue with that.

Stack ADT

The following operations make a stack an ADT. For simplicity, assume the data is an integer type. Main
stack operations
• void push(int data): Inserts data onto stack.
• int pop(): Removes and returns the last inserted element from the stack.

Auxiliary stack operations

• int Top(): Returns the last inserted element without removing it.
• int Size(): Returns the number of elements stored in the stack.
• int IsEmptyStack(): Indicates whether any elements are stored in the stack or not.
• int IsFullStack(): Indicates whether the stack is full or not.
4.4 Exceptions
Attempting the execution of an operation may sometimes cause an error condition, called an
exception. Exceptions are said to be “thrown” by an operation that cannot be executed. In the
Stack ADT, operations pop and top cannot be performed if the stack is empty. Attempting the
execution of pop (top) on an empty stack throws an exception. Trying to push an element in a full
stack throws an exception.
4.5 Applications
Following are some of the applications in which stacks play an important role.
Direct applications
• Balancing of symbols
• Infix-to-postfix conversion
• Evaluation of postfix expression
• Implementing function calls (including recursion)
• Finding of spans (finding spans in stock markets, refer to Problems section)
• Page-visited history in a Web browser [Back Buttons]
• Undo sequence in a text editor
• Matching Tags in HTML and XML

Implementation

There are many ways of implementing stack ADT; below are the commonly used methods.

1) Simple array based implementation

2) Linked lists implementation

1) A Simple Array-Based Implementation

A stack is easily implemented with an N-element array S, with elements stored from S[0]
to S[t], where t is an integer that gives the index of the top element in S. Note that one of
the important details of such an implementation is that we must specify some maximum
size N for our stack, say, N = 1, 000.

If we use the convention that arrays begin at index 0, then we would initialize t to -1 (for an initially
empty stack), and we can use this value to also test if a stack is empty. In addition, we can use this
variable to determine the number of elements in a stack (t+1). In this array-based implementation of
a stack, we also must signal an error condition that arises if we try to insert a new element and the
array S is full. Given this error condition, we can then implement the main methods of a stack
as described below

Algorithm push(o):

if t + 1 = N then

return that a stack-full error has occurred

t←t+1

S[t] ← o
Algorithm pop():

if t < 0 then

return that a stack-empty error has occurred

e ← S[t]

S[t] ← null

t←t−1

return e

Turning to the analysis of this array-based implementation of a stack, it should be clear that each of
the stack methods, push and pop, runs in a constant amount of time. This is because they only
involve a constant number of simple arithmetic operations, comparisons, and assignment
statements. That is, in this array-based implementation of the stack, each method runs in O(1) time.

The array implementation of a stack is both simple and efficient, and is widely used in a variety of
computing applications. Nevertheless, this implementation has one negative aspect; it must assume
a fixed upper bound N on the ultimate size of the stack. An application may actually need much less
space than this, in which case we would be wasting memory. Alternatively, an application may need
more space than this, in which case our stack implementation may “crash” the application with an
error as soon as it tries to push its (N + 1)st object on the stack. Thus, even with its simplicity and
efficiency, the array-based stack implementation is not always ideal.

Fortunately, there is another implementation, which is to use a linked list, discussed later. Such an
implementation would not have a size limitation (other than that imposed by the total amount of
memory on our computer) and it would use an amount of space proportional to the actual number
of elements stored in the stack.

Full java implementation code of array based stack

package arraystackdemo;

/*

* @author TEWODROS

*/

public interface Stack {

public void push(Object ob);

public Object pop();

public Object peek();

public boolean isEmpty();

public int size();

/*-------------------------------end of Stack
intergace-------------------------------------------------------------------------------------------------------------------------
-------------------------------------------------------------*/

package arraystackdemo;

/*

* @author TEWODROS

*/

public class ArrayStack implements Stack {

private Object a[];

private int top; // stack top

public ArrayStack(int n) // constructor

{ a = new Object[n]; // create stack array

top = -1; // no items in the stack

public void push(Object item) // add an item on top of stack

if(top == a.length-1)

{ System.out.println("Stack is full");

return;

}
top++; // increment top

a[top] = item; // insert an item

public Object pop() // remove an item from top of stack

if( isEmpty() )

{ System.out.println("Stack is empty");

return null;

Object item = a[top]; // access top item

top--; // decrement top

return item;

public Object peek() // get top item of stack

{ if( isEmpty() ) return null;

return a[top];

public boolean isEmpty() // true if stack is empty

{ return (top == -1); }

public int size() // returns number of items in the stack

{ return top+1; }

public void display(){

if( isEmpty() )

System.out.println("Stack is empty");

else
for(int i=0;i<=top;i++){

System.out.print(a[i]+" ");

System.out.println("");

/*-------------------------------end of ArrayStack
class-------------------------------------------------------------------------------------------------------------------------------
-------------------------------------------------------*/

package arraystackdemo;

/**

* @author TEWODROS

*/

public class ArrayStackDemo {

/*

* @param args the command line arguments

*/

public static void main(String[] args) {

ArrayStack stk = new ArrayStack(4); // create stack of size 4

Object item;

stk.push('A'); // push 3 items onto stack

stk.push('B');

stk.push('C');
System.out.println(" the stack elements are:");

stk.display();

System.out.println("size(): "+ stk.size());

item = stk.pop(); // delete item

System.out.println(item + " is deleted");

System.out.println(" the stack elements are:");

stk.display();

stk.push('D'); // add three more items to the stack

stk.push('E');

stk.push('F');

System.out.println(" the stack elements are:");

stk.display();

System.out.println(stk.pop() + " is deleted");

stk.push('G'); // push one item

System.out.println(" the stack elements are:");

stk.display();

item = stk.peek(); // get top item from the stack

System.out.println(item + " is on top of stack");

System.out.println(" the stack elements are:");

stk.display();

/*-------------------------------end of ArrayStackDemo class (main

class)------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------*/

Output:
the stack elements are:

ABC

size(): 3

C is deleted

the stack elements are:

AB

Stack is full

the stack elements are:

ABDE

E is deleted

the stack elements are:

ABDG

G is on top of stack

the stack elements are:

ABDG