Stack Implementation in C

 
A stack is a linear data structure that serves as a collection of elements, with three main operations:

  • Push operation, which adds an element to the stack.
     
  • Pop operation, which removes the most recently added element that was not yet removed, and
     
  • Peek operation, which returns the top element without modifying the stack.

 

The push and pop operations occur only at one end of the structure, referred to as the top of the stack. The order in which elements come off a stack gives rise to its alternative name, LIFO (for last in, first out).

Below is simple representation of a stack with push and pop operations –
 

Lifo stack

 
A stack may be implemented to have a bounded capacity. If the stack is full and does not contain enough space for push operation, the stack is then considered to be in an overflow state.

 

Stack Implementation using an array –

 

A (bounded) stack can be easily implemented using an array. The first element of the stack (i.e. bottom-most element), is stored at 0’th index in the array (assuming a zero-based indexing). The second element will be stored at index 1 and so on.. We also maintain a variable top to keep track of the size of the stack by recording the number of items pushed so far. It points to a location in the array where the next element is to be inserted. Thus, the stack itself can be effectively implemented as a three-element structure:


structure stack:
    maxsize : integer
    top : integer
    items : array of item

 
C implementation –
 

Download   Run Code

Output:

Inserting 1
Inserting 2
Inserting 3
Top element is 3
Stack size is 3
Removing 3
Removing 2
Removing 1
Stack is empty

 

The time complexity of push(), pop(), peek(), isEmpty(), isFull() and size() operations is O(1).

It is possible to implement a stack that can grow or shrink as much as needed using a dynamic array such as C++’s std::vector or ArrayList in Java. The size of the stack is simply the size of the dynamic array, which is a very efficient implementation of a stack since adding items to or removing items from the end of a dynamic array requires amortized O(1) time.
 

Applications of stack –

 

  1. Expression evaluation (conversions between prefix, postfix or infix notations)
     
  2. Syntax parsing by compilers
     
  3. Backtracking Algorithms (game playing, finding paths, exhaustive searching)
     
  4. Recursive functions calls i.e. call stack
     
  5. An “undo” operation in text editors
     
  6. Browser back button and many more…

 

 
References: https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂