[Data Structures] Can stack be searched or traversed?

Nue said:

Thank you for the replies. Appreciate it

My understanding was that you can perform only push and pop operation on the stack but today we were asked to write a function that would search for a given element in the stack and return it if it exists. This left me confused

Wouldn't stack be usually implemented when the LIFO order must be strictly followed? Assuming that's the case, if I want to search the stack for a particular element, the best practice would be to pop the contents until the desired element is found and then push them back onto the stack in their original order, correct? And if I do that, wouldn't it be more convenient to store the popped elements in a separate array since having two stacks would get kind of redundant? Or am I missing something here?
Also, is there a data structure generally preferred for implementing stack or is it just a matter of one's preference?

Click to expand...

 //Mechanism of Stack data structure implemented in JAVA

public class newStack {
	
	private int[] testArr ;
	private int size;
	private int first ;
	
	public newStack(int s) {
		
		size = s;
		testArr = new int [size];
		first = -1;
	}
	
 public void push(int m) {
	 
	   testArr[++first] = m;
	 
 }
 
 public int pop (){
	 
	   return testArr[first--];
	 
 }
 
 public int peek() {
	
	   return testArr[first];
	 
 }
 
 public boolean isEmpty(){
	 
	   return (first == -1);
 }
 
 public boolean isFull(){
	 
       return (first == size - 1);
 
 }

}

// Test Code of stack implementation

import java.util.Scanner;

public class StackTest {

	public static void main (String args []){
		
		newStack stack = new newStack(10);
		Scanner in = new Scanner(System.in);
		
		System.out.println("Enter the desired values max upto arraysize:");
		while (!stack.isFull()){
			
	         stack.push(in.nextInt());
		     
		}
		while(!stack.isEmpty()){
			
		 int n = stack.pop();
		 
		 System.out.print(n);
		 System.out.print(" ");
		 
	    }
		System.out.println("");
		
	}
}

Nue said:

@vickybat:
Thank you for the reply.
I apologize if it looked like I was confused but I'm quite clear about the LIFO structure. That's the reason I asked if we can search the stack like a normal array.

This is what I've done so far. Not a complete program but mainly to show how the stack would be searched.

Code:

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

#define STACK_SIZE 10

int contents[STACK_SIZE];
int top;

void init( void ); // Initializes the stack.
bool isEmpty( void ); // Returns true if the stack is empty.
bool isFull( void ); // Returns true if the stack is full.
void Push( int i ); // Pushes an element onto the stack.
int Pop( void ); // Pops an element off the stack.
bool search( int ); // Searches the stack for a given element and returns true if it exists.

int main(int argc, char const *argv[])
{
    int i, key;
    
    // Create a stack
    init();
	
	// Populate the stack with a few elements
	for (i = 0; i < STACK_SIZE; i++)
        Push(i);
    
    printf("Enter element to search: \n");
    scanf("%d", &key);
	
	if (!search(key))
		printf("Element not found"); // search returned false.
	else
		printf("Element found"); // searched returned true.
	

	fflush(stdin);
	getchar();
	return 0;
}

void init( void )
{
    top = 0;
}

bool isEmpty( void )
{
	return top == 0;
}

bool isFull( void )
{
	return top == [B][SIZE=4]STACK_SIZE - 1[/SIZE][/B];
}

void Push( int val )
{
	if ( isFull() ) {
		printf("Stack Overflow\n");
		exit(1);
	}
	[B][SIZE=4]contents[++top] = val[/SIZE];[/B]
}

int Pop( void )
{
	if ( isEmpty() ) {
		printf("Stack underflow\n");
		exit(1);
	}
	[B][SIZE=4]return contents[top--][/SIZE];[/B]
}

bool search( int key )
{
    if ( isEmpty() ) {
		printf("Stack is Empty\n");
		exit (1);	
	}
	
	while ( !isEmpty() ) {
		if (Pop() == key)
			return true; 
    }

    return  false;
}

Click to expand...

vickybat said:

Slightly fixed the push and pop methods.

In push(), the top is incremented first and then a value is assigned.

In pop, the top is simply decremented. The underflow check condition is good.

Now coming to the main part, the search function is kind of unnecessary in a stack. I don't know why your teacher is encouraging you to even try it.
I mean what's the point really?

Suppose you have the required key at "n" index, you have to pop each and every element out of the stack upto "n" element, in order for a match.
So you are doing n pops basically. If the nth value is big i.e 100 or more, then you've to do 100 pops or more to find the key. Its simple linear search and is inefficient.

Stacks are never designed for any searching purpose.

If you want efficient search algorithm, try binary search. Also ask your teacher why they are encouraging to search a key from a stack.
You can use stacks for more practical purposes like reversing a string. Notice what happens when you pop elements out of a stack. Aren't the order reversed?

Click to expand...