Introducing of Stacks

Stacks, queues, deques, and lists are statistics collections with items ordered in line with how they are added or removed. Once an item is added, it stays inside the equal function relative to its buddies. Because of this function, we name these collections linear data systems.

Linear structures may be the concept of as having ended, stated variously as “left” and “right”, “pinnacle” and “bottom”, or “front” and “rear”. What distinguishes one linear structure from any other is where additions and removals may additionally arise. As an example, a shape may only allow new objects to be added at one end and eliminated at some other; every other may also permit the addition or elimination from either cease.

Those variations give an upward push to some of the maximum beneficial records systems in pc technology. They appear in many algorithms and can be used to remedy a diffusion of essential troubles.

Data structures:-

Data structure where data elements are arranged sequentially or linearly is called a linear data structure. In a linear data structure, we can traverse all the data items in a single pass. Until now, all the data structures you have learned are linear only, whether it is Array, ArrayList, or String. Stack is also a linear data structure.

FILO (First In Last Out) or LIFO (Last In First Out) order:-

Let us try to get the meaning of FILO or LIFO using an example. Consider a pile of 3 books on a table.

If you want to take out the top blue book, then you need not do anything to the pile. Just pick it from the top.

But if you want to take out the bottom pink book, then first you need to remove the books on top (blue and yellow), and then only you can get access to the third (bottom-most) book.

Also, if you want to add a book, let's say, green in color, then you can add it above the blue book only. Otherwise, you will have to disturb the remaining 3 books' ordering.

The Stack Abstract Data Type:-

An abstract data type, sometimes abbreviated ADT, is a logical description of how we view the data and the allowed operations without regard to how they’ll be implemented. This means that we’re only concerned with what the data represents and not with how it’ll be constructed. This level of abstraction encapsulates the data and hides implementation details from the user's view, a technique called information hiding.

A data structure is an implementation of an abstract data type and requires a physical view of the data using some collection of primitive data types and other programming constructs.

The separation of these two perspectives allows us to define complex data models for our problems without giving any details about how the model will actually be built. This provides an implementation-independent view of the data. Since there are usually many ways to implement an abstract data type, this independence allows the programmer to change implementation details without changing how the user interacts with it. Instead, the user can remain focused on the process of problem-solving.

The stack abstract data type is an ordered collection of items where items are added to and removed from the top. The interface for a stack is:

• Stack() creates a new, empty stack
• push(item) adds the given item to the top of the stack and returns nothing
• pop() removes and returns the top item from the stack
• peek() returns the top item from the stack but doesn’t remove it (the stack isn’t modified)
• is_empty() returns a boolean representing whether the stack is empty
• size() returns the number of items on the stack as an integer

For example, if s is a newly-created, empty stack, then the table below shows the results of a sequence of stack operations. The top item is the one farthest to the right in “Stack contents”.

Basic Operations:-

Stack operations may involve initializing the stack, using it and then de-initializing it. Apart from these basic stuffs, a stack is used for the following two primary operations −

• push() − Pushing (storing) an element on the stack.
• pop() − Removing (accessing) an element from the stack.

When data is PUSHed onto stack.

To use a stack efficiently, we need to check the status of stack as well. For the same purpose, the following functionality is added to stacks −

• peek() − get the top data element of the stack, without removing it.
• isFull() − check if stack is full.
• isEmpty() − check if stack is empty.

At all times, we maintain a pointer to the last PUSHed data on the stack. As this pointer always represents the top of the stack, hence named top. The top pointer provides top value of the stack without actually removing it.

First we should learn about procedures to support stack functions −

peek()

Algorithm of peek() function −

begin procedure peek

   return stack[top]

end procedure

Implementation of peek() function in C programming language −

Example

int peek() {

   return stack[top];

}

isfull()

Algorithm of isfull() function −

begin procedure isfull

   if top equals to MAXSIZE

      return true

   else

      return false

   endif

end procedure

Implementation of isfull() function in C programming language −

Example

bool isfull() {

   if(top == MAXSIZE)

      return true;

   else

      return false;

}

isempty()

Algorithm of isempty() function −

begin procedure isempty

   if top less than 1

      return true

   else

      return false

   endif

end procedure

Implementation of isempty() function in C programming language is slightly different. We initialize top at -1, as the index in array starts from 0. So we check if the top is below zero or -1 to determine if the stack is empty. Here's the code −

Example

bool isempty() {

   if(top == -1)

      return true;

   else

      return false;

}

Push Operation

The process of putting a new data element onto stack is known as a Push Operation. Push operation involves a series of steps −

• Step 1 − Checks if the stack is full.
• Step 2 − If the stack is full, produces an error and exit.
• Step 3 − If the stack is not full, increments top to point next empty space.
• Step 4 − Adds data element to the stack location, where top is pointing.
• Step 5 − Returns success.

If the linked list is used to implement the stack, then in step 3, we need to allocate space dynamically.

Algorithm for PUSH Operation

A simple algorithm for Push operation can be derived as follows −

begin procedure push: stack, data

   if stack is full

      return null

   endif

   top ← top + 1

   stack[top] ← data

end procedure

Implementation of this algorithm in C, is very easy. See the following code −

Example

void push(int data) {

   if(!isFull()) {

      top = top + 1;   

      stack[top] = data;

   } else {

      printf("Could not insert data, Stack is full.\n");

   }

}

Pop Operation

Accessing the content while removing it from the stack, is known as a Pop Operation. In an array implementation of pop() operation, the data element is not actually removed, instead top is decremented to a lower position in the stack to point to the next value. But in linked-list implementation, pop() actually removes data element and deallocates memory space.

A Pop operation may involve the following steps −

• Step 1 − Checks if the stack is empty.
• Step 2 − If the stack is empty, produces an error and exit.
• Step 3 − If the stack is not empty, accesses the data element at which top is pointing.
• Step 4 − Decreases the value of top by 1.
• Step 5 − Returns success.

Algorithm for Pop Operation

A simple algorithm for Pop operation can be derived as follows −

begin procedure pop: stack

   if stack is empty

      return null

   endif

   data ← stack[top]

   top ← top - 1

   return data

end procedure

Implementation of this algorithm in C, is as follows −

Example

int pop(int data) {

   if(!isempty()) {

      data = stack[top];

      top = top - 1;   

      return data;

   } else {

      printf("Could not retrieve data, Stack is empty.\n");

   }

}