Top List List

Array linked list stack queue

Stack Data Structures

In our day to day life, we see stacks of plates, coins, etc. All these stacks have one thing in common that a new item is added at the top of the stack and any item is also removed from the top i.e., the most recently added item is removed first.

In Computer Science also, a stack is a data structure which follows the same kind of rules i.e., the most recently added item is removed first. It works on LIFO [Last In First Out] policy. It means that the item which enters at last is removed first.

Since a stack just has to follow the LIFO policy, we can implement it using a linked list as well as with an array. However, we will restrict the linked list or the array being used to make the stack so that any element can be added at the top or can also be removed from the top only.

A stack supports few basic operations and we need to implement all these operations [either with a linked list or an array] to make a stack. These operations are:

Push The push operation adds a new element to the stack. As stated above, any element added to the stack goes at the top, so push adds an element at the top of a stack

Pop The pop operation removes and also returns the top-most [or most recent element] from the stack.

Top The Top operations only returns [doesnt remove] the top-most element of a stack.

isEmpty This operation checks whether a stack is empty or not i.e., if there is any element present in the stack or not.

We also handle two errors with a stack. They are stack underflow and stack overflow. When we try to pop an element from an empty stack, it is said that the stack underflowed. However, if the number of elements exceeds the stated size of a stack, the stack is said to be overflowed.

At many places, you might find out that a stack is referred to as an abstract data type which creates confusion in our mind about whether a stack is an abstract data type or a data structure? So, lets discuss.

Stack - Abstract Data Type or Data Structure?

In an Abstract Data Type [or ADT], there is a set of rules or description of the operations that are allowed on data. It is based on a user point of view i.e., how a user is interacting with the data. However, we can choose to implement those set of rules differently.

A stack is definitely an ADT because it works on LIFO policy which provides operations like push, pop, etc. for the users to interact with the data. A stack can be implemented in different ways and these implementations are hidden from the user. For example, as stated above, we can implement a stack using a linked list or an array. In both the implementations, a user will be able to use the operations like push, pop, etc. without knowing the data structure used to implement those operations.

However, when we choose to implement a stack in a particular way, it organizes our data for efficient management and retrieval. So, it can be seen as a data structure also.

Till now, we know about stacks and operations involved with a stack. Lets discuss the applications of a stack.

Applications of Stack

There are many applications of a stack. Some of them are:

Stacks are used in backtracking algorithms.
They are also used to implement undo/redo functionality in a software.
Stacks are also used in syntax parsing for many compilers.
Stacks are also used to check proper opening and closing of parenthesis.

We have already discussed a lot about stacks. So, lets code a stack using an array as well as a linked list.

Stack Using Array

We are going to use the element at the index 1 of the array as the bottom of the stack and the last element of the stack as the top of the stack as described in the picture given below.

Since we need to add and remove elements from the top of the stack, we are going to use a pointer which is always going to point the topmost element of the stack. It will point to the element at index 0 when the stack is empty.

So, lets first write a function to check whether a stack is empty or not.

IS_EMPTY[S] if S.top == 0 return TRUE return FALSE

We are going to consider only the elements from 1 to S.top as part of the stack. It might be possible that there are other elements also in the array but we are not going to consider them as stack.

To add an item to a stack [push], we just need to increment the top pointer by 1 and add the element there.

PUSH[S, x] Here, S is the stack and x is the item we are going to push to the stack.

Lets suppose that S.size is the maximum size of the stack. So, if S.top+1 exceeds S.size, then the stack is overflowed. So, we will first check for the overflowing of the stack and then accordingly add the element to it.

PUSH[S, x] S.top = S.top+1 if S.top > S.size Error "Stack Overflow" else S[S.top] = x

Similarly to remove an item from a stack [pop], we will first check if the stack is empty or not. If it is empty, then we will throw an error of "Stack Underflow", otherwise remove the element from the stack and return it.

POP[S] if IS_EMPTY[S] Error Stack Underflow else S.top = S.top-1 return S[S.top+1]

Lets see the use of the above code snippets to develop a stack in C, Java and Python.

C
Python
Java

#include #define SIZE 10 int S[SIZE+1]; int top = 0; int is_empty[] { if[top == 0] return 1; return 0; } void push[int x] { top = top+1; if[top > SIZE] { printf["Stack Overflow\n"]; } else { S[top] = x; } } int pop[] { if[is_empty[]] { printf["Stack Underflow\n"]; return -1000; } else { top = top-1; return S[top+1]; } } int main[] { pop[]; push[10]; push[20]; push[30]; push[40]; push[50]; push[60]; push[70]; push[80]; push[90]; push[100]; push[110]; int i; for[i=1; iSIZE: print["Stackoverflow"] else: S[top] = x def pop[]: global top if is_empty[]: print["Stackunderflow"] else: top = top-1 return S[top+1] if __name__ == '__main__': pop[] push[10] push[20] push[30] push[40] push[50] push[60] push[70] push[80] push[90] push[100] push[110] print[S[1:SIZE+1]]

class Stack { public static int SIZE = 10; public static int top = 0; public static int[] S = new int[SIZE+1]; public static boolean isEmpty[] { if[top == 0] return true; return false; } public static void push[int x] { top = top+1; if[top > SIZE] System.out.println["Stackoverflow"]; else S[top] = x; } public static int pop[] { if[isEmpty[]] { System.out.println["Stackunderflow"]; return -1000; } else { top = top-1; return S[top+1]; } } public static void main[String[] args] { pop[]; push[10]; push[20]; push[30]; push[40]; push[50]; push[60]; push[70]; push[80]; push[90]; push[100]; push[110]; for[int i=1; idata = data; z->next = NULL; return z; } //to make a new stack stack* new_stack[] { stack *s = malloc[sizeof[stack]]; s->head = NULL; s->top = NULL; return s; } void traversal[stack *s] { node *temp = s->head; //temporary pointer to point to head while[temp != NULL] { //iterating over stack printf["%d\t", temp->data]; temp = temp->next; } printf["\n"]; } int is_empty[stack *s] { if[s->top == NULL] return 1; return 0; } void push[stack *s, node *n] { if[is_empty[s]] { //empty s->head = n; s->top = n; } else { s->top->next = n; s->top = n; } } //function to delete int pop[stack *s] { if[is_empty[s]] { printf["Stack Underflow\n"]; return -1000; } else { int x = s->top->data; if[s->top == s->head] {// only one node free[s->top]; s->top = NULL; s->head = NULL; } else { node *temp = s->head; while[temp->next != s->top] // iterating to the last element temp = temp->next; temp->next = NULL; free[s->top]; s->top = temp; } return x; } } int main[] { stack *s = new_stack[]; node *a, *b, *c; a = new_node[10]; b = new_node[20]; c = new_node[30]; pop[s]; push[s, a]; push[s, b]; push[s, c]; traversal[s]; pop[s]; traversal[s]; return 0; }

class Node[]: def __init__[self, data]: self.data = data self.next = None class Stack[]: def __init__[self]: self.head = None self.top = None def traversal[s]: temp = s.head #temporary pointer to point to head a = '' while temp != None: #iterating over stack a = a+str[temp.data]+'\t' temp = temp.next print[a] def is_empty[s]: if s.top == None: return True return False def push[s, n]: if is_empty[s]: #empty s.head = n s.top = n else: s.top.next = n s.top = n def pop[s]: if is_empty[s]: print["Stack Underflow"] return -1000 else: x = s.top.data if s.top == s.head: # only one node s.top = None s.head = None else: temp = s.head while temp.next != s.top: #iterating to the last element temp = temp.next temp.next = None del s.top s.top = temp return x if __name__ == '__main__': s = Stack[] a = Node[10] b = Node[20] c = Node[30] pop[s] push[s, a] push[s, b] push[s, c] traversal[s] pop[s] traversal[s]

class Node { public int data; public Node next; public Node[int data] { this.data = data; next = null; } } class Stack { public Node head; public Node top; public Stack[] { head = null; top = null; } public void traversal[] { Node temp = this.head; //temporary pointer to point to head while[temp != null] { //iterating over stack System.out.print[temp.data+"\t"]; temp = temp.next; } System.out.println[""]; } public boolean isEmpty[] { if[this.top == null] return true; return false; } public void push[Node n] { if[this.isEmpty[]] { this.head = n; this.top = n; } else { this.top.next = n; this.top = n; } } public int pop[] { if[this.isEmpty[]] { System.out.println["Stack Underflow\n"]; return -1000; } else { int x = this.top.data; if[this.head == this.top] {// only one node this.top = null; this.head = null; } else { Node temp = this.head; while[temp.next != this.top] // iterating to the last element temp = temp.next; temp.next = null; this.top = temp; } return x; } } } class StackMain { public static void main[String[] args] { Stack s = new Stack[]; Node a, b, c; a = new Node[10]; b = new Node[20]; c = new Node[30]; s.pop[]; s.push[a]; s.push[b]; s.push[c]; s.traversal[]; s.pop[]; s.traversal[]; } }

In the next chapter, we are going to study about queues and implement it also using an array and a linked list.

Success is a science; if you have the conditions, you get the result.

- Oscar Wilde

PREV NEXT

# Further Readings

Stacks in C
Making a stack using linked list in C
Making a stack using an array in C

Stack Data Structures

Stack - Abstract Data Type or Data Structure?

Applications of Stack

Stack Using Array

Video liên quan

Bài Viết Liên Quan

Toplist mới

Bài mới nhất

Chủ Đề