Stack in Data Structure | Representation | Push and Pop operation

Prev Next

---

A stack is a linear Structure in which items may be added or removed only at one end, called the top of the stack. This means, in particular, the elements are removed from a stack in the reverse order of that which they are inserted in to the stack. The stacks are also called "Last-in First -Out (LIFO) " list.

"Stack is a collection of similar data items in which both insertion and deletion operations are performed based on LIFO principle".

Example

1. A stack of dinner plates on a kitchen.

2. "LAST HIRED, FIRST FIRED" which is typically utilized when a company wants to reduces its work force.

3. Remembering partially completed tasks. JVM uses a stack to remember all of a program's methods that have been called but are not yet finished.

4. undoing (backtracking from) an action. "undo" button on most text editors, which lets a person undo a typing error, or the "back" button on a web browser, which lets a user backtrack to a previous web page

5. In processing of subroutine calls and returns

Primary operations defined on a stack

Push: Insert an element at the top of the list.

Pop : Delete an element from the top of the list.

Peek : Return value of topmost element.

Implementation of Stack:

The stack data structure can be implemented in two different ways

1. Using array [ Static Implementation ]

2. Using Linked List [ Dynamic Implementation ]

Array representation of a stack

Let us consider a stack with 3 elements capacity. This is called as the MaxSize of the stack. The number of elements to be added should not exceed the maximum size of the stack. If we attempt to add new element beyond the maximum size, we will encounter a stack overflow condition. Similarly, you cannot remove elements beyond the base of the stack. If such is the case, we will reach a stack underflow condition.

Top is a variable , which points top most element of the stack.

Each time a new element is inserted in the stack , the top is incrementated by "one" before the element is placed on the stack.

Top=Top+1

The Top is decremented by "one" each time a deletion is made from the stack.

Top=Top-1

MaxSize is a variable , which gives the maximum number of elements that can be held by the stack.

Algorithm : To Insert an Element into a Stack

Step 1: Check whether the stack is full

if TOP == MaxSize-1

Write "Stack is full/overflow"

[ End of IF ]

Step 2: Increment Top pointer

Top = Top + 1

Step 3: Insert element at the Top of the stack

stack[Top] = Element;

Step 4: EXIT

Algorithm : To Delete an Element from a Stack

Step 1: Check whether the stack is empthy

if TOP == -1

Write "Stack is empthy/underflow"

Step 2: Store the topmost element from stack into a temporary variable K

K = stack[Top]

Step 3: Decrement Top pointer

Top = Top - 1

Step 4: Return K

Step 5: EXIT

Prev Next

Share this

yashcode