Stack Operation

Stack operation

Stack is a linear data structure which allows access to only one data item: the last item inserted. If you remove this item, you can access the next-to-last item inserted, and so on. This is a useful capability in many programming situations.

The end from which items are inserted or deleted is called the Top of the Stack (TOS). The items in the stack are homogeneous. Since all the deletion and insertion is done from the TOS, the last added element will be the first to be removed from the stack – hence the stack follows the LIFO (Last—In—First—Out) structure.

Most microprocessors (like the one in your computer) use a stack-based architecture. When a member function is called, its return address and arguments are pushed onto a stack, and when the function returns they’re popped off. The stack operations are built into the microprocessor.

Some older pocket calculators used a stack-based paradigm. Instead of entering arithmetic expressions using parentheses, you pushed intermediate results onto a stack.

Stack Terminology:

1. Context: The environment in which a function executes: includes argument values, local variables and global variables. All the context except the global variables are stored in the stack frame.

2. Stack Frame: A data structure containing all the data(arguments, local variables, return address etc. ) needed each time a procedure or function is called.

3. MAXSIZE: The maximum size of the stack (not a standard notation, though.)

4. TOP: Refers to the top of the stack. Initially, it stores -1. Before inserting new item, it is increased, only then insertion is done.

5. Stack: It is an array of size MAXSIZE.

6. Stack Underflow: Stack is empty, so no more deletions are possible. In this situation, the TOS is present at the bottom of the stack.

7. Stack Overflow: Stack is full, so no more insertions are possible. In this situation, the TOS is present at the topmost location of the stack.

Stack as an ADT

/* value definition */

abstract typedef stack(itemtype);

/* check for empty */

abstract empty(s)

stack(item_type) s;

postcondition: empty == (len(s) == 0);

/* pop */

abstract (item_type) pop(s)

stack (item_type) s;

precondition: empty(s) == False;

postcondition: pop == first(s);

s = sub(s,1, len(s)-1 );

/* push */

abstract push(s,item)

stack(item_type) s;

item_type item;

postcondition: s == + s ;

Operations on Stack

- Creation of Stack

- Push

- Pop

- Display of Stack Items

Stack Implementation

Stack implementation can be done in one of the following two ways:

- TOS varying method

- TOS fixed method

Implementation of stack can also be “static” (where the size is fixed during program design) or “dynamic” (where linked lists are used, allowing change of size during program execution).

TOS Varying Method:

Algorithm:

Declare and initialize mecessary variables.

TOS (top) = -1

MAXSIZE

item

Stack[]

For PUSH Operation:

If TOS == MAXSIZE – 1

Stack Overflow

Else

TOS = TOS + 1

Read item from user

Stack[TOS] = item

For next push operation, repeat Step 2.

For POP operation:

If TOS == -1

Stack Underflow

Else

item = Stack[TOS]

TOS = TOS – 1

Display Item

For next pop operation, repeat step 3.

TOS Fixed Method:

Algorithm

Declare and initialiaze necessary variables

BOS = 0

MAXSIZE

item

Stack[]

For PUSH Operation:

If BOS == MAXSIZE

Stack Overflow

Else

Insert new element by making vacant space at Stack[0] location

for (i=BOS; i>0; i--)

Stack[i] = Stack[i-1]

Read item from user

Stack[0] = item

BOS = BOS + 1

For next push operation, repeat step 2.

For POP Operation:

If BOS == 0:

Stack Underflow

Else:

Extract item from Stack[0], decrease BOS and refill space by

lowering each step by 1:

item = Stack[0]

BOS = -1

for (i=0; i<=BOS; i++)

Stack[i] = Stack[i+1]

return item

For next pop operation, repeat this step 3.

* BOS = Bottom of Stack

References:

1. Y. Langsam, M. J. Augenstein and A. M Tenenbaum, “Data Structuresusing C and C++”

2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, “Introduction toAlgorithms”

3. G. Brassard and P. Bratley, “Fundamentals of Algorithms”