Web
Analytics Made Easy - StatCounter

Stacks (With Code in C, C++, Java, and Python)

Introduction

A stack is a linear data structure in which the insertion and deletion operations can be performed at one end called top of the stack. A stack is also called a Last In First Out (LIFO) data structure. Remember Array and Linked list where we can add or remove the data from both the end (front or back). Unlike these data structures, stack allows the user to access only one end. Figure 1 visualizes a stack with 5 items.

Fig 1: A visualization of a stack

As we can see in Figure 1, we can not access item 1. The bottom is closed. Top of the stack is the only place where we have access to. We can only access item 5 which is at the top of the stack. In order to get to the item 4, we need to remove 5, to get to item 3, we need to remove 4 and 5 and so on. In all the operations we do in the stack, we manipulate the top of the stack in some way. Based on how we use the top, there are three operations we can do on the stack.

  1. Push: We insert a new item at the top of the stack.
  2. Pop: We remove the item from the top of the stack.
  3. Top: We read the value of the item at the top of the stack.

Now I am going to explain all these operations in detail.

Operations on stack

Push

A new item can be pushed into a stack using the following steps.

  1. Check if the stack is full. If it is, then you can not insert the item. Raise “Stack Overflow” error.
  2. If the stack is not full, insert the item at the top of the stack.
  3. Make this item a new top of the stack.

Fig 2: Push operation

Pop

An item on the top of the stack can be removed (popped) using following steps.

  1. Check if the stack is empty. If it is, then you can not remove the item. Raise “Stack Underflow” error.
  2. If the stack is not empty, remove the item at the top of the stack.
  3. Update the top of the stack.

Fig 3: Pop operation

Top (or peek)

The top operation returns the item at the top of the stack. Don’t be confused this operation with the pop operation. The pop operation removes the top item whereas the top operation only reads the value of the top item. As in the pop operation, we need to check if the stack is empty before reading the value.

Complexities

The complexities of all the operations are tabulated below.

OperationComplexity
PushO(1)
PopO(1)
Top (Peek)O(1)

Applications of a stack

A stack is widely used in many areas of computer science. Some of the applications are listed below.

  1. Many algorithms like Depth First Search, Graham Scan, Monotone Triangulation, etc.
  2. Expressions evaluation and syntax parsing.
  3. Series of functions are stored in a stack by a compiler.
  4. Backtracking
  5. Undo features, back and forth features etc.

Implementation

A stack can be implemented using arrays as well as linked lists.

Implementation using array

Implementation of the stack using an array in C, C++, and Java is given below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
// C implementation of stack using arrays

#include <stdio.h>
#define MAX_SIZE 10

// global variables
int stack[MAX_SIZE];
int top = -1;

// inserts item at the top of the stack
void push(int item) {
// check for overflow
if (top >= MAX_SIZE - 1) {
printf("%s\n", "Error: Can not push item. Stack Overflow");
return;
}

// insert the item and update the top
stack[top + 1] = item;
top = top + 1;
}


// removes an item from the top of the stack
int pop() {
// check for underflow
if (top <= -1) {
printf("%s\n", "Error: Can not pop item. Stack Underflow");
return -999999;
}

top = top - 1;
return stack[top + 1];
}

// returns the item at the top
int peek() {
// check for underflow
if (top <= -1) {
printf("%s\n", "Error: Can not read item. Stack Underflow");
return - 999999;
}

return stack[top];
}

int main() {
push(12);
push(45);
push(33);
push(35);
push(39);
push(53);
push(30);
push(98);
push(34);
push(78);
push(3100);
printf("%d\n", pop());
printf("%d\n", pop());
printf("%d\n", pop());
printf("%d\n", pop());
printf("%d\n", pop());
printf("%d\n", peek());
printf("%d\n", peek());
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// C++ implementation of Stack using array

#include<iostream>

using namespace std;

class MyStack {
private:
const static int MAX_SIZE = 10;
int stack[MAX_SIZE];
int top;
public:
MyStack() {
top = -1;
}

// inserts item at the top of the stack
void push(int item) {
// check for overflow
if (top >= MAX_SIZE - 1) {
cout<<"Error: Can not push item. Stack Overflow"<<endl;
return;
}

// insert the item and update the top
stack[top + 1] = item;
top = top + 1;
}

// removes item from the top of the stack
int pop() {
// check for underflow
if (top <= -1) {
cout<<"Error: Can not pop item. Stack Underflow"<<endl;
return -999999;
}

top = top - 1;
return stack[top + 1];
}

// returns the item at the top
int peek() {
// check for underflow
if (top <= -1) {
cout<<"Error: Can not read item. Stack Underflow"<<endl;
return - 999999;
}

return stack[top];
}
};

int main() {
MyStack stack;
stack.push(33);
stack.push(34);
stack.push(35);
cout<<stack.peek()<<endl;
cout<<stack.pop()<<endl;
cout<<stack.peek()<<endl;
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// Java implementation of Stack using array

public class MyStack {
private static final int MAX_SIZE = 10;
private int[] stack;
private int top;

public MyStack() {
stack = new int[MAX_SIZE];
top = -1;
}

// inserts item at the top of the stack
public void push(int item) {
// check for overflow
if (top >= MAX_SIZE - 1) {
System.out.println("Error: Can not push item. Stack Overflow");
return;
}

// insert the item and update the top
stack[top + 1] = item;
top = top + 1;
}

// removes an item from the top of the stack
public int pop() {
// check for underflow
if (top <= -1) {
System.out.println("Error: Can not pop item. Stack Underflow");
return -999999;
}

top = top - 1;
return stack[top + 1];
}

// returns the item at the top
public int peek() {
// check for underflow
if (top <= -1) {
System.out.println("Error: Can not read item. Stack Underflow");
return - 999999;
}

return stack[top];
}

public static void main(String [] args) {
MyStack stack = new MyStack();
stack.push(22);
stack.push(44);
System.out.println(stack.peek());
System.out.println(stack.pop());
System.out.println(stack.peek());
}
}

Implementation using linked list

Implementation of the stack using a linked list in C, C++, Java, and Python is given below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// C implementation of stack using linked list

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node *next;
struct Node *prev;
};

typedef struct Node *NodePtr;

// globally define tail
NodePtr tail = NULL;

// Push operation
void push(int item) {
NodePtr node = malloc(sizeof(NodePtr));
node->data = item;
node->next = NULL;
node->prev = NULL;

if (tail == NULL) {
tail = node;
} else {
tail->next = node;
node->prev = tail;
tail = node;
}
}

// pop operation
int pop() {
int item;
if (tail == NULL){
printf("%s\n", "ERROR: Stack is empty");
return -999999;
}

item = tail->data;
NodePtr prev = tail->prev;
if (prev != NULL) {
prev->next = NULL;
}
tail->prev = NULL;
free(tail);
tail = prev;
return item;

}

// top (peek) operation
int peek() {
if (tail == NULL){
printf("%s\n", "ERROR: Stack is empty");
return -999999;
}

return tail->data;
}

int main() {
push(33);
push(22);
push(44);
printf("%d\n", pop());
printf("%d\n", peek());
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
// C++ implementation of stack using linked list
#include <iostream>
using namespace std;

struct Node {
int data;
Node *next;
Node *prev;
};

typedef Node *NodePtr;

class MyStackLinkedList {
private:
NodePtr tail;
public:
MyStackLinkedList() {
tail = nullptr;
}

// push operation
void push(int item) {
NodePtr node = new Node;
node->data = item;
node->next = nullptr;
node->prev = nullptr;

if (tail == nullptr) {
tail = node;
} else {
tail->next = node;
node->prev = tail;
tail = node;
}
}

// pop operation
int pop() {
if (tail == nullptr) {
cout<<"ERROR: stack is empty"<<endl;
return -999999;
}

int item = tail->data;
NodePtr prev = tail->prev;
if (prev != nullptr) {
prev->next = nullptr;
}
tail->prev = nullptr;
delete tail;
tail = prev;
return item;
}


// peek (top) operation
int peek() {
if (tail == nullptr) {
cout<<"ERROR: stack is empty"<<endl;
return -999999;
}

return tail->data;
}

};

int main() {
MyStackLinkedList stack;
stack.push(44);
stack.push(33);
cout<<stack.pop()<<endl;
cout<<stack.pop()<<endl;
cout<<stack.pop()<<endl;
stack.push(45);
cout<<stack.peek()<<endl;
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// Java implementation of stack using linked list

class Node {
int data;
Node prev;
Node next;

public Node(int item) {
data = item;
prev = null;
next = null;
}
}

public class MyStackLinkedList {
private Node tail;

public MyStackLinkedList() {
tail = null;
}

public void push(int item) {
Node node = new Node(item);

if (tail == null) {
tail = node;
} else {
node.prev = tail;
tail.next = node;
tail = node;
}
}

public int pop() {
if (tail == null) {
System.out.println("ERROR: Stack is empty");
return -999999;
}
int item = tail.data;
Node prev = tail.prev;
if (prev != null) {
prev.next = null;
}

tail.prev = null;
tail = prev;
return item;
}

public int peek() {
if (tail == null) {
System.out.println("ERROR: Stack is empty");
return -999999;
}

return tail.data;
}

public static void main(String [] args) {
MyStackLinkedList stack = new MyStackLinkedList();
stack.push(45);
stack.push(66);
System.out.println(stack.pop());
System.out.println(stack.peek());
System.out.println(stack.pop());
System.out.println(stack.pop());
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
# Python implementation of stack using linked list

class Node:
def __init__(self, item):
self.data = item
self.prev = None
self.next = None

class MyStack:
def __init__(self):
self.tail = None

def push(self, item):
node = Node(item)

if self.tail == None:
self.tail = node
else:
node.prev = self.tail
self.tail.next = node
self.tail = node

def pop(self):
if self.tail == None:
print "ERROR: Stack is empty"
return

item = self.tail.data
prev = self.tail.prev
if prev != None:
prev.next = None
self.tail.prev = None
self.tail = prev
return item

def peek(self):
if self.tail == None:
print "ERROR: Stack is empty"
return
return self.tail.data

if __name__ == '__main__':
stack = MyStack()
stack.push(44)
stack.push(34)
stack.push(22)
print stack.pop()
print stack.pop()
print stack.peek()