CS201: Elementary Data Structures

A stack is a linear data structure that follows a particular order of operations. The order may be LIFO(Last In First Out) or FILO(First In Last Out)

The following basic operations are performed in the stack:

• Push: Adds an item in the stack. If the stack is full, then it is said to be an overflow condition.
• Pop: Removes an item from the stack. The items are popped in the reverse order from when they are pushed. If the stack is empty, then it is said to be an underflow condition.
• Peek or Top: Returns top element of stack.
• isEmpty: Returns true if stack is empty, else fals.

How can you understand a stack in practical terms?

There are many real-life examples of stacks. Consider the simple example of plates stacked on top of one another in a restaurant. The plate at the top is the first one to be removed -- that is, the plate at the bottom remains in the stack for the longest period of time. Since the plate on top is removed first, we see that the plates follow the LIFO/FILO order.

Time Complexities of Stack Operations:

push(), pop(), esEmpty() and peek() all take O(1) time. We do not run loops in any of these operations.

Implementation:

There are two ways to implement a stack: using arrays, and using linked lists.

Implementing Stack using Arrays

/* C++ program to implement basic stack
   operations */
#include<bits/stdc++.h>
using namespace std;
 
#define MAX 1000
 
class Stack
{
    int top;
public:
    int a[MAX];    //Maximum size of Stack
 
    Stack()  { top = -1; }
    bool push(int x);
    int pop();
    bool isEmpty();
};
 
bool Stack::push(int x)
{
    if (top >= MAX)
    {
        cout << "Stack Overflow";
        return false;
    }
    else
    {
        a[++top] = x;
        return true;
    }
}
 
int Stack::pop()
{
    if (top < 0)
    {
        cout << "Stack Underflow";
        return 0;
    }
    else
    {
        int x = a[top--];
        return x;
    }
}
 
bool Stack::isEmpty()
{
    return (top < 0);
}
 
// Driver program to test above functions
int main()
{
    struct Stack s;
    s.push(10);
    s.push(20);
    s.push(30);
 
    cout << s.pop() << " Popped from stack\n";
 
    return 0;
}

Pros: This is easy to implement, and memory is saved since pointers are not involved.

Cons: This is not dynamic, meaning that it can't grow and shrink depending on needs at runtime.

10 pushed to stack
20 pushed to stack
30 pushed to stack
30 popped from stack
Top item is 20

Implementing Stack using Linked List

// C program for linked list implementation of stack
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
 
// A structure to represent a stack
struct StackNode
{
    int data;
    struct StackNode* next;
};
 
struct StackNode* newNode(int data)
{
    struct StackNode* stackNode =
              (struct StackNode*) malloc(sizeof(struct StackNode));
    stackNode->data = data;
    stackNode->next = NULL;
    return stackNode;
}
 
int isEmpty(struct StackNode *root)
{
    return !root;
}
 
void push(struct StackNode** root, int data)
{
    struct StackNode* stackNode = newNode(data);
    stackNode->next = *root;
    *root = stackNode;
    printf("%d pushed to stack\n", data);
}
 
int pop(struct StackNode** root)
{
    if (isEmpty(*root))
        return INT_MIN;
    struct StackNode* temp = *root;
    *root = (*root)->next;
    int popped = temp->data;
    free(temp);
 
    return popped;
}
 
int peek(struct StackNode* root)
{
    if (isEmpty(root))
        return INT_MIN;
    return root->data;
}
 
int main()
{
    struct StackNode* root = NULL;
 
    push(&root, 10);
    push(&root, 20);
    push(&root, 30);
 
    printf("%d popped from stack\n", pop(&root));
 
    printf("Top element is %d\n", peek(root));
 
    return 0;
}

Output:

10 pushed to stack
20 pushed to stack
30 pushed to stack
30 popped from stack
Top element is 20

Pros: The linked list implementation of stack can grow and shrink according to the needs at runtime.

Cons: This requires extra memory since it uses pointers.

Source: GeeksForGeeks, http://www.cdn.geeksforgeeks.org/stack-data-structure-introduction-program/
 This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 2.5 India License.