The stack

Stack

A stack is an ordered collection of items into which new items may be inserted and from which items may be deleted at one end, called the top of the stack (Langsam, Augenstein, & Tenenbaum, 2013). A stack is a data structure that permits adding and removing elements in a specific order. Each time an element is added, it goes on the top of the stack; the only element that can be removed is the element at the top of the stack. It follows the Last-In-First-Out (LIFO) principle. The first element added to a stack will be the last element removed from a stack.

Primitive Operations

The primitive operations on stack are as follows:

• PUSH operation
• POP operation
• Empty operation
• Full operation
• Stacktop operation

Push Operation

It is used to add or insert a new element in a stack. When an element is added to a stack, it is said that the element is pushed onto the stack and the operation is called a push operation. The new elements are always pushed to the top of the stack. The syntax for PUSH operation is

PUSH(stack, element)

POP Operation

It is used to remove an item from the stack. When we remove an item from the stack, it is said that an item is popped from the stack and this operation is called the pop operation. The element is popped from the top of the stack. The syntax for POP operation is

POP(stack)

Empty Operation

It determines whether the stack is empty or not. Its syntax is

empty(stack)

If empty(stack) returns the value TRUE, then the stack is empty, else it is not empty.

Full Operation

It determines whether the stack is full or not. Its syntax is

full(stack)

If full(stack) returns the value TRUE, then the stack is full, else it is not full.

Stacktop Operation

This operation allows the user to know what the top item of the stack is without having to pop it. Its syntax is

stacktop(stack)

This operation can be decomposed into PUSH and POP operation as

i=POP(stack);

PUSH(stack, i);

Stack as an ADT

Consider a stack ‘‘s’’ of data type T with finite number of elements, then we can perform the following operations:

• CreateEmptyStack(s): creates an empty stack.
• PUSH(s, x): insert x at the top of s.
• POP(s): removes the top element of s.
• IsFull(s): if 1 then s is full, else not full.
• IsEmpty(s): if 1 then empty, else not empty.

Since all these operations can be performed in a stack, we can consider stack as an ADT.

Implementing the POP Operation

When performing the POP operation, there may be the chance of stack underflow i.e. the stack is empty. In this case, the user must be informed about the underflow condition. The POP operation performs the following actions:

• If the stack is empty, print a warning message and halt execution.
• Remove the top element from the stack.
• Return this element into the calling program.

Algorithm for POP operation

• Check whether the stack is empty. If (TOP=-1), stack is empty and operation is not possible else

Data= stack[top];

Set top=top=1;

• Display the popped item.
• Exit.

int pop (struct *ps)

{

if (empty(ps))

{

printf(“Stack underflow”);

exit(1)

}/*end if*/

return (ps->items[ps->top--];

}/*end pop*/

Testing for Exceptional Conditions

With the detection of underflow, it may not be necessary to halt the execution immediately, Instead, the pop routine could signal the occurrence of an underflow and take the corrective action. Let ’popandrest’ be a procedure that pops the stack and returns a signal whether the underflow has occurred or not.

Void popandtest (struct stack *ps, int *px, int*pund)

{

If (empty(ps))

{

*pund = TRUE;

return;

} /*end if*/

*pund = FALSE;

*px = ps->items[ps->top--];

return;

}/*end popandtest */

In the calling program, a programmer would write

popandtest (&s, &x, &und)

if (und)

/*take corrective action*/

Else

/*use value of x*/

Implementing the PUSH Operation

A first attempt at a PUSH procedure will be

void push (struct stact *ps, int x)

{

ps->items[++(ps->top)] = x;

return;

}/*end push*/

Suppose the stack is full and we attempt to push an item onto the stack. This results in a condition called the overflow. When an overflow condition occurs, we cannot add any more items and an error message needs to be produced to inform the user.

The push procedure therefore will be revised as follows:

void push (struct stack *ps, int x)

{

if (ps->top==STACKSIZE-1)

{

printf (“Stack overflow”);

exit(1);

}

else

ps->items[++(ps->top)] = x;

return;

}/*end push*/

When an overflow is detected in push, an error message is printed and the execution halts immediately. In some cases, it might make more sense for the calling routine to invoke the push operation with the instructions.

pushandtest (&s, x, &overflow);

if (overflow)

/*overflow has been detected, x was not pushed to stack, take remedial action */

else

/* x was successfully pushed onto the stack, continue processing */

References

Langsam, Y., Augenstein, M. j., & Tenenbaum, A. M. (2013). Data Structures Using C and C++. Delhi: PHI Learning Private Limited.