What is meant by stack?

A stack is a linear data structure that follows certain order to perform the operation; the order will be LIFO (Last In First Out) data structure. In the stack data structure elements/items are removed and added only from the top. The topmost stack item/element is pointed by the top pointer and the element which is added to the stack first will get deleted at the last.

For example, consider a stack of books, the book that is placed at last is the first to be removed.

Stack implementation

The implementation of the stack is done by using an array and linked list. The stack can either be resized dynamically or can have a fixed size. Using array results in a fixed-size stack implementation. Two different ways of implementing the stack operations are,

Using array

The array is a container that can be accessed randomly, that is the item/element in the container has instant access.

Example

From the above diagram, 5 is the top element of the array initially. Pop is performed to remove 5 and the top element will become 4 after removing 5. To insert 5 again push operation need to be performed, so 5 will be added and it becomes the top element.

Using linked list

A linked list is a container that can be accessed sequentially, that is the item/element in the data structure has sequential access.

Example

From the above diagram, 4 is the top element of the linked list initially. Pop operation is performed to remove 4 and the top element will become 3. To insert 4 again in the list then push operation need to be performed, so 4 will be added to the liked list and 4 becomes the top element.

Stack principle – LILO

The full form of LILO will be Last-in, Last-out; whereas in programming, the term adding an item at the stack top is pushed, and removing some element from the stack is pop. The stack can be implemented at any of the programming languages like C, C++, Java, C#, or python.

Purpose of stack

• The behaviour of stack is similar to piles of book/plates.
• The order of performing the stack operations in data structure can be either LIFO or FIFO.
• Stack is an Abstract Data Type (ADT) with the pre-defined capacity that is it could store the element with limited size.

Working of stack

The stack operations are,

• “TOP” is a pointer which maintains the top element at the stack.
• During stack initialization the value is set as -1; so, it easy to verify whether the stack is empty or not by just comparing  “TOP = = -1”.
• The “TOP” value is increased by pushing the element/item to the stack and the new item/element is placed at the position which is pointed by the “TOP”.
• The “TOP” value is returned by popping the element from the stack.
• Before inserting(pushing) the elements, the stack should be checked whether it is already full or not.
• Before removing(popping) the elements, the stack should be checked whether it is empty or not.

Stack Operations

The following are the algorithms and functions of the stack.

• Stack initialization.
• Insert into stack.
• Delete from stack.
• Check for stack fullness.
• Check for stack emptiness.

These algorithms help the user to understand the stack operation. In stack, the algorithms will have “top” and its points to 0 initially; whereas, the index of the stack starts at 1 and max will be the last element.

Basic operations of stack

• Push: loads the element/item into the stack; overflow occurs whenever the stack is full and check the stack by using isFull() function.
• Pop: remove/extract the element/item from the stack; underflow occurs whenever the stack becomes empty and checks the stack by using isEmpty() function.

Push operation

Push operation is used to add/insert new elements into the stack. The operations of push are,

• Determines whether stack is full.
• When the stack is full, and an element is inserted then an error (overflow) is processed and it exits.
• When the stack is initialized, the top is set with -1 (check for stack empty).
• While inserting new element the top will get incremented (top = top + 1) and the new element will be placed at its new position.
• Till the stack reaches its max stack size, the element/item can be inserted.

Algorithm

begin procedure pushoperation: stack_1, data

If stack_1 is full

      return null

end if

top <- top +1

stack_1[top] <- data

end procedure

Example

void pushfun () //definition for push function

{

if (!isFull()) //checks the stack is full

{

   top =top + 1; //change the top values after increment

   stack_1 [top] = data; //stores the value in the stack

}

else

{

  printf(“ n stack is full!!! ”); //else works when stack is full

}

}

POP operation

POP operation removes the element/item from the stack; the items will be removed in reverse order (in which it is pushed). In the case of array implementation, it will not remove the data elements, but just decreases the top to its lower position; whereas, in the case of linked-list implementation it removes and memory space is deallocated. The operations of push are,

• POP operation determines whether stack is empty.
• When the stack is empty, and an element is deleted/removed then an error (underflow) is processed and it exits.
• The element that is pointed by top is accessed when the stack is empty.
• After performing POP, the top is reduced by 1 (top = top -1).

Algorithm

begin procedure popoperation: stack_1

If stack_1 is empty

     return null

end if

data <- stack_1[top]

top <- top -1

return data

end procedure

Example

void popfun () //definition for pop function

{

if (!isEmpty()) //checks the stack is full

{

  data =stack_1 [top]; //stores the value in the stack

  top =top - 1; //change the top values after decrement

   return data;

}

else

{

  printf(“ n stack is empty!!! ”); //else works when stack is full

}

}

Other common operations

• Peek: Get the element/item from the required position.
• IsEmpty: Verify whether the stack is empty.
• IsFull: Verify whether the stack is full or not.
• Count: Returns the total elements/items available in the stack.
• Change: Change the element/item available in the provided position.
• Display: Prints the elements/items at the stack.

Time complexity of stack

The stack implementation of array-based has the operation like push and pop, these operation takes a constant time that is O(1).

Stack application

• String reverse.
• Balance a symbol.
• Recursion.
• Redo/Undo.
• DFS (Depth First Search).
• Expression conversion.
• Backtracking.
• Memory management.

Advantages

• Implementation is quite easy.
• Stack operations are faster.
• Adding and removing of item/element happens in one place.
• Allows the user to deallocate and allocate the memory.

Disadvantages

• Limited Memory space.
• Creating more objects might leads to stack overflow.
• Stored variables can be overwritten and it might lead to the undefined program or function behaviour.
• Abnormal termination might happen when stack falls outside memory area.

Context and Applications

This topic is important for postgraduate and undergraduate courses, particularly for, Bachelors's in Computer Science Engineering and an Associate of Science in Computer Science.

Practice Problems

Question 1: Which algorithm use stack, as its principle data structure to organize the data?

a) Nearest-neighbor chain

b) Graham scan

c) SMAWK algorithm

d) All the above

Answer: Option d is correct.

Explanation: There are several efficient algorithms, which use the stack as its principle data structure and they are nearest-neighbor chain, graham scan, and SMAWK algorithm.

Question 2: ____ is used to insert elements in the stack.

a) Pop

b) Create

c) Push

d) Evaluate

Answer: Option c is correct.

Explanation: The purpose of push is to add/insert elements in the stack and with the help of the isFull() function it determines the stack is full or not.

Question 3: _____ is used to remove elements from the stack.

a) Pop

b) Delete

c) Push

d) Evaluate

Answer: Option a is correct

Explanation: The purpose of the pop is to remove/delete elements. The stack element is removed in reverse order and with the help of the isEmpty() function, it determines that stacks are empty or not.

Question 4: In stack, the elements gets inserted and deleted at________.

a) One end

b) Middle

c) Any position

d) Both the end

Answer: Option a is correct.

Explanation: The elements get inserted and deleted at one end. Whereas, the elements/items present in the stack data structure are removed or added from the top.

Question 5: _____ happens when the user tries to remove/delete an element from an empty stack.

a) Empty collection

b) Garbage collection

c) Underflow

d) Overflow

Answer: Option c is correct.

Explanation: When the stack becomes empty and the user tries to remove an element then underflow will occur. isEmpty() function helps to check the stack is empty or not.