[go: up one dir, main page]

0% found this document useful (0 votes)
130 views48 pages

Stack

The document discusses different implementations of a stack data structure, including: 1. An array implementation where the stack is formed using an array and operations like push, pop, and peek are performed using array indexes and manipulation of the top variable. 2. A linked list implementation where each node contains a data field and pointer to the next node, allowing dynamic memory allocation. Push and pop involve adding/removing nodes from the front of the list. 3. Applications of stacks like infix to postfix conversion, evaluation, and bracket grouping. Pseudocode and Java code are provided for stack operations in both array and linked list implementations.
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
130 views48 pages

Stack

The document discusses different implementations of a stack data structure, including: 1. An array implementation where the stack is formed using an array and operations like push, pop, and peek are performed using array indexes and manipulation of the top variable. 2. A linked list implementation where each node contains a data field and pointer to the next node, allowing dynamic memory allocation. Push and pop involve adding/removing nodes from the front of the list. 3. Applications of stacks like infix to postfix conversion, evaluation, and bracket grouping. Pseudocode and Java code are provided for stack operations in both array and linked list implementations.
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 48

STACK

Page 1 of 48
Page 2 of 48
Topic cover:

• Array implementation

• LinkedList implementation

• Applications of stack

o Infix to postfix conversion

o evaluation

• Brackets grouping

Array implementation of Stack

In array implementation, the stack is formed by using the array. All the operations regarding the stack
are performed using arrays. Lets see how each operation can be implemented on the stack using array
data structure.

Adding an element onto the stack (push operation)

Adding an element into the top of the stack is referred to as push operation. Push operation involves
following two steps.

1. Increment the variable Top so that it can now refere to the next memory location.
2. Add element at the position of incremented top. This is referred to as adding new element at
the top of the stack.

Page 3 of 48
Stack is overflown when we try to insert an element into a completely filled stack therefore, our main
function must always avoid stack overflow condition.

Algorithm:

begin

if top = n then stack full

top = top + 1

stack (top) : = item;

end
Time Complexity : o(1)

implementation of push algorithm in Java

Deletion of an element from a stack (Pop operation)


Deletion of an element from the top of the stack is called pop operation. The value of the variable top
will be incremented by 1 whenever an item is deleted from the stack. The top most element of the
stack is stored in an another variable and then the top is decremented by 1. the operation returns the
deleted value that was stored in another variable as the result.

Page 4 of 48
The underflow condition occurs when we try to delete an element from an already empty stack.

Algorithm :

begin
if top = 0 then stack empty;
item := stack(top);
top = top - 1;
end;

Time Complexity : o(1)

Implementation of POP algorithm using Java

Visiting each element of the stack (Peek operation)

Peek operation involves returning the element which is present at the top of the stack without deleting
it. Underflow condition can occur if we try to return the top element in an already empty stack.

Algorithm :

PEEK (STACK, TOP)

Begin
if top = -1 then stack empty
item = stack[top]
return item
End

Page 5 of 48
Time complexity: o(n)

Implementation of Peek algorithm in Java

Full java program:

import java.util.Scanner;

class Stack

int top;

int maxsize = 10;

int[] arr = new int[maxsize];

boolean isEmpty()

return (top < 0);

Stack()

top = -1;

Page 6 of 48
}

boolean push (Scanner sc)

if(top == maxsize-1)

System.out.println("Overflow !!");

return false;

else

System.out.print("Enter Value: ");

int val = sc.nextInt();

top++;

arr[top]=val;

System.out.println("Item pushed");

return true;

boolean pop ()

if (top == -1)

System.out.println("Underflow !!");

return false;

Page 7 of 48
else

top --;

System.out.println("Item popped");

return true;

void display ()

System.out.println("Printing stack elements .....");

for(int i = top; i>=0;i--)

System.out.println(arr[i]);

class Main {

public static void main(String[] args) {

int choice=0;

Scanner sc = new Scanner(System.in);

Stack s = new Stack();

//System.out.println("*********Stack operations using array*********\n");

//System.out.println("\n------------------------------------------------\n");

while(choice != 4)

Page 8 of 48
// System.out.println("\nChose one from the below options...\n");

System.out.println("\n1.Push\t2.Pop\t3.Show\t4.Exit");

System.out.print("Enter your choice: ");

choice = sc.nextInt();

switch(choice)

case 1:

s.push(sc);

break;

case 2:

s.pop();

break;

case 3:

s.display();

break; 8/

case 4:

System.out.println("Exiting....");

System.exit(0);

Page 9 of 48
break;

default:

System.out.println("Please Enter valid choice ");

};

Linked list implementation of stack


Instead of using array, we can also use linked list to implement stack. Linked list allocates the memory
dynamically. However, time complexity in both the scenario is same for all the operations i.e. push,
pop and peek.

In linked list implementation of stack, the nodes are maintained non-contiguously in the memory. Each
node contains a pointer to its immediate successor node in the stack. Stack is said to be overflown if
the space left in the memory heap is not enough to create a node.

Page 10 of 48
The top most node in the stack always contains null in its address field. Lets discuss the way in which,
each operation is performed in linked list implementation of stack.

Adding a node to the stack (Push operation)

Adding a node to the stack is referred to as push operation. Pushing an element to a stack in linked list
implementation is different from that of an array implementation. In order to push an element onto
the stack, the following steps are involved.

1. Create a node first and allocate memory to it.


2. If the list is empty then the item is to be pushed as the start node of the list. This includes
assigning value to the data part of the node and assign null to the address part of the node.
3. If there are some nodes in the list already, then we have to add the new element in the
beginning of the list (to not violate the property of the stack). For this purpose, assign the
address of the starting element to the address field of the new node and make the new node,
the starting node of the list.

Page 11 of 48
Code:

Page 12 of 48
Deleting a node from the stack (POP operation)

Deleting a node from the top of stack is referred to as pop operation. Deleting a node from the linked
list implementation of stack is different from that in the array implementation. In order to pop an
element from the stack, we need to follow the following steps :

1. Check for the underflow condition: The underflow condition occurs when we try to pop from an
already empty stack. The stack will be empty if the head pointer of the list points to null.
2. Adjust the head pointer accordingly: In stack, the elements are popped only from one end,
therefore, the value stored in the head pointer must be deleted and the node must be freed.
The next node of the head node now becomes the head node.
Time Complexity : o(n)

Code:

Page 13 of 48
Display the nodes (Traversing)

Displaying all the nodes of a stack needs traversing all the nodes of the linked list organized in the form
of stack. For this purpose, we need to follow the following steps.

1. Copy the head pointer into a temporary pointer.


2. Move the temporary pointer through all the nodes of the list and print the value field attached
to every node.
Time Complexity : o(n)

Code:

Java implementation:

import static java.lang.System.exit;

Page 14 of 48
class StackUsingLinkedlist {

// A linked list node

private class Node

int data; // integer data

Node link; // reference variable Node type

// create global top reference variable global

Node top;

// Constructor

StackUsingLinkedlist()

this.top = null;

// Utility function to add an element x in the stack

public void push(int x) // insert at the beginning

// create new node temp and allocate memory

Node temp = new Node();

// check if stack (heap) is full. Then inserting an element would lead to stack overflow

if (temp == null) {

System.out.print("\nHeap Overflow");

Page 15 of 48
return;

// initialize data into temp data field

temp.data = x;

// put top reference into temp link

temp.link = top;

// update top reference

top = temp;

// Utility function to check if the stack is empty or not

public boolean isEmpty()

return top == null;

// Utility function to return top element in a stack

public int peek()

// check for empty stack

if (!isEmpty()) {

return top.data;

Page 16 of 48
}

else {

System.out.println("Stack is empty");

return -1;

// Utility function to pop top element from the stack

public void pop() // remove at the beginning

// check for stack underflow

if (top == null) {

System.out.print("\nStack Underflow");

return;

// update the top pointer to point to the next node

top = (top).link;

public void display()

// check for stack underflow

if (top == null) {

System.out.printf("\nStack Underflow");

Page 17 of 48
exit(1);

else {

Node temp = top;

while (temp != null) {

// print node data

System.out.printf("%d->", temp.data);

// assign temp link to temp

temp = temp.link;

// main class

class Main {

public static void main(String[] args)

// create Object of Implementing class

StackUsingLinkedlist obj = new StackUsingLinkedlist();

// insert Stack value

obj.push(11);

obj.push(22);

obj.push(33);

Page 18 of 48
obj.push(44);

// print Stack elements

obj.display();

// print Top element of Stack

System.out.printf("\nTop element is %d\n", obj.peek());

// Delete top element of Stack

obj.pop();

obj.pop();

// print Stack elements

obj.display();

// print Top element of Stack

System.out.printf("\nTop element is %d\n", obj.peek());

Applications of Stack
1. Recursion
2. Expression evaluations and conversions
3. Parsing
4. Browsers
5. Editors
6. Tree Traversals

Page 19 of 48
Infix to Postfix conversion:

Infix expression:The expression of the form a op b. When an operator is in-between every pair of
operands.

Postfix expression:The expression of the form a b op. When an operator is followed for every pair of
operands.

Example:

Input: Infix expression - A + B


Output: Postfix expression- AB+

Input: Infix expression - A+B*(C^D-E)


Output: Postfix expression- ABCD^E-*+

Approach: Use Stacks

• Operator stack: This stack will be used to keep operations (+, -, *, /, ^)


Order of precedence of operations:

• ^ (Exponential)
• /*
• +–
Note: brackets ( ) are used to override these rules.

Algorithm:

1. Scan the infix expression from left to right.


2. If the scanned character is an operand, output it.
3. Else,
a. If the precedence of the scanned operator is greater than the precedence of the
operator in the stack(or the stack is empty or the stack contains a ‘(‘ ), push it.
b. Else, Pop all the operators from the stack which are greater than or equal to in
precedence than that of the scanned operator. After doing that Push the scanned
operator to the stack. (If you encounter parenthesis while popping then stop there
and push the scanned operator in the stack.)
4. If the scanned character is an ‘(‘, push it to the stack.
5. If the scanned character is an ‘)’, pop the stack and and output it until a ‘(‘ is encountered,
and discard both the parenthesis.

Page 20 of 48
6. Repeat steps 2-6 until infix expression is scanned.
7. Print the output
8. Pop and output from the stack until it is not empty.

Java Implementation:

/* Java implementation to convert infix expression to postfix*/

// Note that here we use Stack class for Stack operations

import java.util.Stack;

class Main

// A utility function to return precedence of a given operator

// Higher returned value means higher precedence

Page 21 of 48
static int Prec(char ch)

switch (ch)

case '+':

case '-':

return 1;

case '*':

case '/':

return 2;

case '^':

return 3;

return -1;

// The main method that converts given infix expression

// to postfix expression.

static String infixToPostfix(String exp)

// initializing empty String for result

String result = new String("");

Page 22 of 48
// initializing empty stack

Stack<Character> stack = new Stack<>();

for (int i = 0; i<exp.length(); ++i)

char c = exp.charAt(i);

// If the scanned character is an operand, add it to output.

if (Character.isLetterOrDigit(c))

result += c;

// If the scanned character is an '(', push it to the stack.

else if (c == '(')

stack.push(c);

// If the scanned character is an ')', pop and output from the stack

// until an '(' is encountered.

else if (c == ')')

while (!stack.isEmpty() && stack.peek() != '(')

result += stack.pop();

if (!stack.isEmpty() && stack.peek() != '(')

return "Invalid Expression"; // invalid expression

Page 23 of 48
else

stack.pop();

else // an operator is encountered

while (!stack.isEmpty() && Prec(c) <= Prec(stack.peek())){

if(stack.peek() == '(')

return "Invalid Expression";

result += stack.pop();

stack.push(c);

// pop all the operators from the stack

while (!stack.isEmpty()){

if(stack.peek() == '(')

return "Invalid Expression";

result += stack.pop();

return result;

// Driver method

Page 24 of 48
public static void main(String[] args)

String exp = "a+b*(c^d-e)^(f+g*h)-i";

System.out.println(infixToPostfix(exp));

Brackets Grouping

Check for balanced parentheses in an expression

Given an expression string exp , write a program to examine whether the pairs and the orders of
“{“,”}”,”(“,”)”,”[“,”]” are correct in exp.

Input: exp = “[()]{}{[()()]()}”

Output: Balanced

Input: exp = “[(])”

Output: Not Balanced

Algorithm:

1. Declare a character stack S.


2. Now traverse the expression string exp.
a. If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[‘) then push it to stack.
b. If the current character is a closing bracket (‘)’ or ‘}’ or ‘]’) then pop from stack and if the
popped character is the matching starting bracket then fine else parenthesis are not
balanced.
3. After complete traversal, if there is some starting bracket left in stack then “not balanced”

Page 25 of 48
Page 26 of 48
Code:

// Java program for checking

// balanced Parenthesis

class Main

static class stack

int top=-1;

char items[] = new char[100];

Page 27 of 48
void push(char x)

if (top == 99)

System.out.println("Stack full");

else

items[++top] = x;

char pop()

if (top == -1)

System.out.println("Underflow error");

return '\0';

else

char element = items[top];

top--;

return element;

Page 28 of 48
}

boolean isEmpty()

return (top == -1) ? true : false;

/* Returns true if character1 and character2

are matching left and right Parenthesis */

static boolean isMatchingPair(char character1, char character2)

if (character1 == '(' && character2 == ')')

return true;

else if (character1 == '{' && character2 == '}')

return true;

else if (character1 == '[' && character2 == ']')

return true;

else

return false;

/* Return true if expression has balanced

Parenthesis */

static boolean areParenthesisBalanced(char exp[])

Page 29 of 48
{

/* Declare an empty character stack */

stack st=new stack();

/* Traverse the given expression to check matching parenthesis */

for(int i=0;i<exp.length;i++)

/*If the exp[i] is a starting parenthesis then push it*/

if (exp[i] == '{' || exp[i] == '(' || exp[i] == '[')

st.push(exp[i]);

/* If exp[i] is an ending parenthesis then pop from stack and check if the popped
parenthesis is a matching pair*/

if (exp[i] == '}' || exp[i] == ')' || exp[i] == ']')

/* If we see an ending parenthesis without a pair then return false*/

if (st.isEmpty())

return false;

/* Pop the top element from stack, if it is not a pair parenthesis of character then
there is a mismatch. This happens for expressions like {(}) */

else if ( !isMatchingPair(st.pop(), exp[i]) )

return false;

Page 30 of 48
}

/* If there is something left in expression then there is a starting parenthesis without a closing
parenthesis */

if (st.isEmpty())

return true; /*balanced*/

else

{ /*not balanced*/

return false;

/* UTILITY FUNCTIONS */

/*driver program to test above functions*/

public static void main(String[] args)

char exp[] = {'{','(',')','}','[',']'};

if (areParenthesisBalanced(exp))

System.out.println("Balanced ");

else

System.out.println("Not Balanced ");

Page 31 of 48
QUEUE

Like Stack, Queue is a linear structure which follows a particular order in which the operations are
performed. The order is First In First Out (FIFO). A good example of queue is any queue of consumers
for a resource where the consumer that came first is served first.

The difference between stacks and queues is in removing. In a stack we remove the item the most
recently added; in a queue, we remove the item the least recently added.

Operations on Queue:

Mainly the following four basic operations are performed on queue:

Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition.

Dequeue: Removes an item from the queue. The items are popped in the same order in which they are
pushed. If the queue is empty, then it is said to be an Underflow condition.

Front: Get the front item from queue.

Rear: Get the last item from queue.

Page 32 of 48
Topics to be covered:

1. Array implementation
2. Constructing stack using queue
3. applications

Array Implementation for in Java

We can easily represent queue by using linear arrays. There are two variables i.e. front and rear, that
are implemented in the case of every queue. Front and rear variables point to the position from where
insertions and deletions are performed in a queue. Initially, the value of front and queue is -1 which
represents an empty queue. Array representation of a queue containing 5 elements along with the
respective values of front and rear, is shown in the following figure.

Page 33 of 48
The above figure shows the queue of characters forming the English word "HELLO". Since, No deletion
is performed in the queue till now, therefore the value of front remains -1 . However, the value of rear
increases by one every time an insertion is performed in the queue. After inserting an element into the
queue shown in the above figure, the queue will look something like following. The value of rear will
become 5 while the value of front remains same.

After deleting an element, the value of front will increase from -1 to 0. however, the queue will look
something like following.

Algorithm to insert any element in a queue

Check if the queue is already full by comparing rear to max - 1. if so, then return an overflow error.

If the item is to be inserted as the first element in the list, in that case set the value of front and rear to
0 and insert the element at the rear end.

Page 34 of 48
Otherwise keep increasing the value of rear and insert each element one by one having rear as the
index.

• Step 1: IF REAR = MAX - 1


Write OVERFLOW
Go to step
[END OF IF]
• Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE
SET REAR = REAR + 1
[END OF IF]
• Step 3: Set QUEUE[REAR] = NUM
• Step 4: EXIT
Code:

Algorithm to delete an element from the queue

If, the value of front is -1 or value of front is greater than rear , write an underflow message and exit.

Otherwise, keep increasing the value of front and return the item stored at the front end of the queue
at each time.

• Step 1: IF FRONT = -1 or FRONT > REAR


Write UNDERFLOW
ELSE
SET VAL = QUEUE[FRONT]
SET FRONT = FRONT + 1
[END OF IF]
• Step 2: EXIT

Page 35 of 48
Code

Array Implementation in Java

// Java program for array implementation of queue

// A class to represent a queue

class Queue

int front, rear, size;

int capacity;

int array[];

public Queue(int capacity) {

this.capacity = capacity;

front = this.size = 0;

rear = capacity - 1;

array = new int[this.capacity];

Page 36 of 48
}

// Queue is full when size becomes equal to the capacity

boolean isFull(Queue queue)

{ return (queue.size == queue.capacity);

// Queue is empty when size is 0

boolean isEmpty(Queue queue)

{ return (queue.size == 0); }

// Method to add an item to the queue. It changes rear and size

void enqueue( int item)

if (isFull(this))

return;

this.rear = (this.rear + 1)%this.capacity;

this.array[this.rear] = item;

this.size = this.size + 1;

System.out.println(item+ " enqueued to queue");

// Method to remove an item from queue. It changes front and size

int dequeue()

Page 37 of 48
if (isEmpty(this))

return Integer.MIN_VALUE;

int item = this.array[this.front];

this.front = (this.front + 1)%this.capacity;

this.size = this.size - 1;

return item;

// Method to get front of queue

int front()

if (isEmpty(this))

return Integer.MIN_VALUE;

return this.array[this.front];

// Method to get rear of queue

int rear()

if (isEmpty(this))

return Integer.MIN_VALUE;

return this.array[this.rear];

Page 38 of 48
}

// Driver class

public class Test

public static void main(String[] args)

Queue queue = new Queue(1000);

queue.enqueue(10);

queue.enqueue(20);

queue.enqueue(30);

queue.enqueue(40);

System.out.println(queue.dequeue() + " dequeued from queue\n");

System.out.println("Front item is " + queue.front());

System.out.println("Rear item is " + queue.rear());

Drawback of array implementation

Page 39 of 48
Although, the technique of creating a queue is easy, but there are some drawbacks of using this
technique to implement a queue.

Memory wastage : The space of the array, which is used to store queue elements, can never be reused
to store the elements of that queue because the elements can only be inserted at front end and the
value of front might be so high so that, all the space before that, can never be filled.

The above figure shows how the memory space is wasted in the array representation of queue. In the
above figure, a queue of size 10 having 3 elements, is shown. The value of the front variable is 5,
therefore, we can not reinsert the values in the place of already deleted element before the position of
front. That much space of the array is wasted and can not be used in the future (for this queue).

Deciding the array size

On of the most common problem with array implementation is the size of the array which requires to
be declared in advance. Due to the fact that, the queue can be extended at runtime depending upon
the problem, the extension in the array size is a time taking process and almost impossible to be
performed at runtime since a lot of reallocations take place. Due to this reason, we can declare the
array large enough so that we can store queue elements as enough as possible but the main problem
with this declaration is that, most of the array slots (nearly half) can never be reused. It will again lead
to memory wastage.

Constructing Stack using Queue

The problem is opposite of this post. We are given a Queue data structure that supports standard
operations like enqueue() and dequeue(). We need to implement a Stack data structure using only
instances of Queue and queue operations allowed on the instances.

Page 40 of 48
A stack can be implemented using two queues. Let stack to be implemented be ‘s’ and queues used to
implement be ‘q1’ and ‘q2’. Stack ‘s’ can be implemented in two ways:

Algorithm:

Push

The new element is always added to the rear of queue q1 and it is kept as top stack element

Page 41 of 48
s

Java

private Queue<Integer> q1 = new LinkedList<>();

private Queue<Integer> q2 = new LinkedList<>();

private int top;

// Push element x onto stack.

public void push(int x) {

q1.add(x);

top = x;

Pop:

We need to remove the element from the top of the stack. This is the last inserted element in q1.
Because queue is FIFO (first in - first out) data structure, the last inserted element could be removed
only after all elements, except it, have been removed. For this reason we need to maintain additional
queue q2, which will serve as a temporary storage to enqueue the removed elements from q1. The last
inserted element in q2 is kept as top. Then the algorithm removes the last element in q1. We swap q1
with q2 to avoid copying all elements from q2 to q1.

Page 42 of 48
Java:

// Removes the element on top of the stack.

public void pop() {

while (q1.size() > 1) {

top = q1.remove();

q2.add(top);

q1.remove();

Queue<Integer> temp = q1;

q1 = q2;

Page 43 of 48
q2 = temp;

Java Implementation:

/* Java Program to implement a stack using

two queue */

import java.util.*;

class Main {

static class Stack {

// Two inbuilt queues

static Queue<Integer> q1 = new LinkedList<Integer>();

static Queue<Integer> q2 = new LinkedList<Integer>();

// To maintain current number of

// elements

static int curr_size;

Stack()

curr_size = 0;

static void push(int x)

Page 44 of 48
curr_size++;

// Push x first in empty q2

q2.add(x);

// Push all the remaining

// elements in q1 to q2.

while (!q1.isEmpty()) {

q2.add(q1.peek());

q1.remove();

// swap the names of two queues

Queue<Integer> q = q1;

q1 = q2;

q2 = q;

static void pop()

// if no elements are there in q1

if (q1.isEmpty())

return;

q1.remove();

Page 45 of 48
curr_size--;

static int top()

if (q1.isEmpty())

return -1;

return q1.peek();

static int size()

return curr_size;

// driver code

public static void main(String[] args)

Stack s = new Stack();

s.push(1);

s.push(2);

s.push(3);

System.out.println("current size: " + s.size());

Page 46 of 48
System.out.println(s.top());

s.pop();

System.out.println(s.top());

s.pop();

System.out.println(s.top());

System.out.println("current size: " + s.size());

Queue Application:

Queue is used when things don’t have to be processed immediately, but have to be processed in First
In First Out order like Breadth First Search. This property of Queue makes it also useful in following
kind of scenarios.

1) When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk
Scheduling.

2) When data is transferred asynchronously (data not necessarily received at same rate as sent)
between two processes. Examples include IO Buffers, pipes, file IO, etc.

Page 47 of 48
Page 48 of 48

You might also like