Stack introduction and its operations

STACK

A stack is a simple linear data structure used for storing data (similar to Linked Lists) in a particular manner. In stack, the procedure in which the data-elements arrive is most important. A stack (also known as “push-down stack”) is an organized compilation of items where the addition(push) of new values and the elimination of the existing items takes place at the same end. This end is generally referred to as the “top” and the end(of the stack) opposite the top is known as the “base”.

The pile of plates at a cafeteria or restaurant is a good example of a stack of real-life implementation. When they are cleaned then the plates are added to the stack. Subsequently, They are placed on the top one by one. When at an instance plate is required then it is retrieved from the top of the stack. The first plate placed in the stack at the end is the last one to be used.

We know that a Stack is an ordered list in which insertion and deletion are done at one end, called the top. The last element inserted is the first one to be deleted. The base of the stack is significant since items stored in the stack that are closer to the base represent those elements that have been in the stack for the longest duration. The most newly added element is the one that is in condition to be retrieved first. This type of ordering principle is sometimes called LIFO, last-in-first-out. It generally provides an ordering based on the length of time in the collection. Newer items are situated near the top place, while older items are near the base. Hence, it is called Last In First Out (LIFO) or First In Last Out (FILO) list.

Stack Operations

 AUXILIARY STACK OPERATIONS :

- void push(int data): Inserts data onto a stack.

- int pop(int data): Removes and returns the last inserted element from the stack.

- int Is_empty(): Checks if the stack is empty or not.

- int Is_full(): Checks if the stack is full or not.

 

Despite its relations with different data structures such as arrays and linked lists. Stack’s different use means the primitive operations for stacks are usually given different names.

The two constructors are:

EmptyStack displays true if the stack is empty, and

push(element; stack), which takes an element and pushes it on top place of an existing stack, and the two selectors are: 

top(stack), which gives back the topmost element of a stack, 

pop(stack), which gives back the stack without the topmost element.

The selectors will work only for non-empty stacks, hence we need a condition which tells whether a stack is empty: isEmpty(stack)

We have equivalent automatically-true relationships to those we had for the lists:

isEmpty(EmptyStack)

if-not isEmpty(push(x; s)) //(for any x and s)

top(push(x; s)) = x

pop(push(x; s)) = s

Time Complexities of operations on stack: push(), pop(), and isEmpty() all take O(1) time. We do not run any loop in any of these operations.

Algorithm 1:

PUSH (STACK, TOP, MAXSTK, ITEM)

//This procedure pushes an item on to a stack.

1. [Stack already filled]?

If TOP = MAXSTK, then: Print: OVERFLOW, and Return.

2. Set TOP: = TOP + 1. [Increase TOP by 1].

3. Set STACK [TOP]: = ITEM. [Inserts ITEM in new TOP position].

4. Return.

Algorithm 2: 

POP (STACK, TOP, ITEM)

//This procedure deletes the TOP element of STACK and assigns it to the variable ITEM.

1. [Stack has an item to be removed]

If TOP = 0, then: Print: UNDERFLOW and Return.

2. Set ITEM: =STACK [TOP]. [Assign TOP element to ITEM].

3. Set TOP: = TOP – 1 [Decrease TOP by 1].

4. Return.

 

If we use a dynamic array, then we can implement a stack that can grow or shrink as much as needed. The size of the stack is simply the size of the dynamic array. A dynamic array is a very efficient implementation of a stack, since adding items to or removing items from the end of a dynamic array is dynamical with respect to time. 

The general idea for the Implementation of Stacks:

There are two different ways by which we can consider implementing stacks. Now, so far we have implied a functional approach to this. That is, push does not lay an impact on the original stack but constructs a new stack out of the original stack with a new element. That is, there are at least two stacks around, the original one and the newly created one. This functional view is quite convenient. If we apply top to a particular stack, we will always get the same element. However, from a practical point of view, we may not want to create lots of new stacks in a program, because of the obvious memory management implications. Instead, it might be better to think of a single stack that is destructively changed, so that after applying push the original stack no longer exits, but has been changed into a new stack with an extra element. This is conceptually more difficult, since now applying a top to a given stack may give different answers, depending on how the state of the system has changed. However, as long as we keep this difference in mind, ignoring such implementational details should not cause any problems.